Summary1 基础用法模版
[TOC]
算法模版
常用
表示无穷大（int的上限）：
// int的最大值就是2的31次方-1
#define INF (1<<31)-1
// 用库中定义的INT_MAX
#include <climits>
#define INF INT_MAX
double 四舍五入的变式：永远舍和永远入：
double a = 0.656, b = 0.651;
printf("%.2lf %2lf", a-0.05, b-0.05); // 都会往下舍，变为0.65 0.65
printf("%.2lf %2lf", a+0.05, b+0.05); // 都会往上入，变为0.66 0.66
字符 & 字符串的scanf读入
char ch
scanf(" %c", &ch); // 前面要加空格
char s[10];
scanf("%s", s);
scanf字符串读入(对于流输入输出进行优化)
// 数据：2007-06-23-11:59 2007-06-23-12:00
int by, ey, bm, em, bd, ed, bh, eh, bmin, emin;
scanf("%d-%d-%d-%d:%d", &by, &bm, &bd, &bh, &bmin);
scanf("%d-%d-%d-%d:%d", &ey, &em, &ed, &eh, &emin); // 即可获取
char a;
cin>>by>>a>>bm>>a>>bd>>a>>bh>>a>>bmin;
cin>>by>>a>>bm>>a>>ed>>a>>eh>>a>>emin; // 也可以获取
判断字符是大写字母还是小写字母还是数字
string str;
char ch;
// 判断
if (isupper(str[i])) // 判断大写字母
if (isupper(ch)) // 判断大写字母
if (islower(ch)) // 判断小写字母
if (isalnum(str[i])) // 判断数字
// 转换
cout<<(char)toupper('a'); // A
cout<<(char)tolower('D'); // d
int num = stoi("123"); // 123
字符串常用操作：插入、删除、替换、拷贝
string str1="We can insert a string";
string str2="a str into ";
// insert 插入
cout <<str1.insert(14,str2)<<endl; //在字符串指定位置index=14前面插入指定字符串 //We can insert a str into a string
cout <<str1.insert(14,str2,2,9)<<endl;//在字符串指定位置前面插入指定字符串的子串（从指定索引开始的指定个数的字符） //2后面的9个数字 //We can insert str into a str into a string
cout <<str1.insert(14,"test hello",5)<<endl;//插入指定字符串的前n个字符 //插入了5个元素 //We can insert test str into a str into a string
cout <<str1.insert(14,6,'*')<<endl; //插入n个同样字符到字符串中 //We can insert ******test str into a str into a string
// replace 插入
cout <<str1.replace(3,3,"may")<<endl;//替换指定索引开始的指定长度的子串 //We may insert ******test str into a str into a string
cout <<str1.replace(3,3,"can could",4,5)<<endl; //用给定字符串的指定子串来进行替换//例如以下。实际上使用的是could来进行替换 //We could insert ******test str into a str into a string
cout <<str1.replace(3,5,"can could",3)<<endl; //使用给定字符串的前n个字符来进行替换：can //We can insert ******test str into a str into a string
cout <<str1.replace(3,3,5,'*')<<endl; //使用指定个数的反复字符来进行替换 //We ***** insert ******test str into a str into a string
string word="We";
size_t index=str1.find(word);
if(index!=string::npos)
//删除指定索引开始的指定长度的字符
cout <<str1.erase(index,word.length())<<endl; // ***** insert ******test str into a str into a string
// erase 移除
string str3("1234567890");
str3.erase(2,3); //把脚标为2开始的字符，连同其之后的3个字符全部删除 //1267890
str3.erase(2); //把脚标为2及其之后的所有字符全部删除 //12
str3.erase(); //清空所有字符 //
// find 查找
//关于npos，找不到都会返回这个 // Value returned by various member functions when they fail. //static const size_type npos = static_cast<size_type>(-1);
std::string str4 ("There are two needles in this haystack with needles."); std::string str5 ("needle");
// different member versions of find in the same order as above:
std::size_t found = str4.find(str5);
if (found!=std::string::npos)
cout << "first 'needle' found at: " << found << '\n'; //输出14
found=str4.find("needles are small",found+1,6); //在str中的第(found+1)位开始搜索，搜索"needles are small"字符串中的前6位，找到索引位置。
if (found!=std::string::npos)
cout << "second 'needle' found at: " << found << '\n'; //输出44
found=str4.find("haystack");
if (found!=std::string::npos)
cout << "'haystack' also found at: " << found << '\n'; //输出30
found=str4.find('.');
if (found!=std::string::npos)
cout << "Period found at: " << found << '\n'; //输出51
// let's replace the first needle:
str4.replace(str4.find(str5),str5.length(),"preposition"); //replace 用法
cout << str4 << '\n';
// find_first_of(), find_last_of(), //find_first_not_of(), find_last_not_of()
string temp6 = "cag sdme"; string temp7 = "na me";
size_t where = temp6.find_first_of(temp7); //也可以直接写 temp1.find_first_of("name");
cout<<"find_first_of: "<<where<<endl; //输出索引 1 这里是temp6的索引 1 temp7中的字母第一次在temp6出现的相同字母为 a
size_t where2 = temp6.find_last_of(temp7);
cout<<"find_first_of: "<<where2<<endl; //输出索引 7 这里是temp6的索引 7 temp7中的字母最后一次在temp6出现的相同字母为 e
size_t where3 = temp6.find_last_not_of(temp7);
cout<<"find_last_not_of: "<<where3<<endl; //输出索引 5 这里是temp6的索引 5 temp7中的字母最后一次在temp6中的不同是 d
size_t where4 = temp6.find_first_not_of(temp7);
cout<<"find_first_not_of: "<<where4<<endl; //输出索引 0 这里是temp6的索引 0 temp7中的字母第一次在temp6中的不同是
cin读入提速
ios::sync_with_stdio(false);
scanf // getline+cin读入一整行：
// scanf
char s[maxn];
scanf("%[^\n]", &s); // 注意，此时传入的变量名就类似于读入数字，不可以类似于数组或者字符串数组的那种直接传地址了
// getline+cin
string str1, str2;
getline(cin, str1); // 注意，出现了getline之后，单独使用cin会失效
getline(cin, str2);
// 解决方案
cin>>a;
getchar(); // 中间添加getchar将多余的读了进去就好了
getline(cin, b);
字符串不告诉有多少，读着读着就消失了 scanf
char s[maxn];
while(~scanf("%s", s)) {
// 对s字符数组进行操作
}
// cin + eof
string str;
while (!cin.eof()) {
cin>>str;
// 对str字符串进行操作
}
字符串当作数字使用，通过数字排序来代表字典序
#include <algorithm>
string strs[maxn];
// 直接将字符串字典序排序
sort(strs+1, strs+1+n); // 按照字典序排序
// 将字符串进行拼接然后保证拼接出来的字串字典序最大 => 拼接直接求和，重载一下求和所比较的内容即可
bool cmp(string a, string b) {return a+b > b+a;}
sort(strs+1, strs+1+n, cmp);
声明一段地址空间：c用malloc，c++用new
node nw = (node)malloc(sizeof(node)); // c写法，声明一个结构体
node nw = new node();
node * point_node = new node(); // c++写法，声明一个指向结构体的指针（point to struct）
node * point_node_2 = new node {param1, param2};
// 注意如果用malloc(c)来new一个的话，强制转换要为(node*)的类型，但是size不是指针的size，而是结构体的size
// 如果用typedef 来进行声明的简化 => 然后就可以用point_node 来代替node*
typedef struct node * pnode;
node * point_node3 = (node*)malloc(sizeof(node)); // C写法，利用malloc
pnode point_node4 = (pnode)malloc(sizeof(node)); // C写法，利用malloc然后利用typedef来进行简化
pnode point_node5 = new node {param1, param2};
其他写法：（对于之前声明的，可以先判断是否为NULL，如果为NULL的话，直接给他赋一个值就好）
if (nw == NULL) {
nw = new node(); // 在为NULL的情况下，直接new一个新的节点
nw.l = nw.r = NULL;nw.val = val;
}
io
快速读入
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
结构体
构造函数
struct node{
int a, b;
string str;
}
p.push(node(aa, bb)); // 第一种
p.push({aa, bb, str}); // 第二种
结构体中-重载运算符
让结构体在排序的时候可以以重载后的<进行排序，此时来比较的重载后的比较结构体的方式【所以重载之后要返回bool】
struct node{
int a, b;
// 方法1
bool operator < (const node n) const {return a*b < n.a*n.b;}
// 方法2
bool operator < (const node& n) {return a*b < n.a*n.b;}
}
类中-重载运算符
类里边重载，目的是为了让两个类可以进行四则运算所以对他进行重载，最终肯定返回的是一个类【所以重载之后要返回类testClass】
（两个对象进行比较得到 => 是/否， 两个对象做四则运算 => 得到一个新的对象）
class testClass{
public:
int a, b;
testClass(){}
testClass(const testClass& tc) {this->a=tc.a;this->b=tc.b;}
testClass(int a, int b) {this->a = a;this->b = b;}
// 下边在类里边重载的话，用类返回 -- 两种写法
testClass operator + (const testClass& tc) {return testClass(a+tc.a, b+tc.b);}
testClass operator - (const testClass tc) const {return testClass(a-tc.a, b-tc.b);}
testClass operator * (const testClass& tc) {return testClass(a*tc.a, b*tc.b);}
testClass operator / (const testClass tc) const {return testClass(a/tc.a, b/tc.b);}
// 注意 > < 的重载，这个重载之后的结果返回的是bool
bool operator < (const testClass tc) const {return a < tc.a;}
bool operator > (const testClass& tc) {return a < tc.a;}
// 重载输入输出，返回的应该是输入输出流这个对象（然后处理的这个实体对象应该是要被处理的对象）=> 注意都没有const，需要修改这个参数的话就不能加const
istream& operator >> (istream& input, testClass& tc) {input>>tc.a>>tc.b;return input;}
ostream& operator << (ostream& output, testClass& tc) {output<<tc.a<<tc.b;return output;}
};
// 类测试代码
int main() {
testClass t1, t2;
cin>>t1>>t2;
testClass t3, t4, t5;
t3 = t1+t2;t4 = t1-t2;t5 = t1*t2;
cout<<t3<<endl; cout<<t4<<endl; cout<<t5<<endl; // 注意不可以直接cout<<t1+t2<<endl;这样是报错的
return 0;
}
数据结构
ST表-区间最大最小gcd(RMQ)
// 初始化
scanf("%d", &minn[i][0]);maxx[i][0] = minn[i][0];
for(int j = 1; j <= 21; j++)
for(int i = 1; i+(1<<j)-1 <= n; i++)
minn[i][j] = min(minn[i][j-1], minn[i+(1<<(j-1))][j-1]);
// 查询-解析倍率k并返回区间最值
int query(int l, int r) {
int k = log2(r-l+1);
return min(minn[l][k], minn[r-(1<<k)+1][k]);
}
数学
最大公约数
int gcd(int a, int b) {return b>0:gcd(a%b, b):a;}
最小公倍数
gcd(a, b)*gld(a, b) = a*b
快速幂
int quickPower(int a, int k) {
int ans=1, base=a;
while(k > 0) {
if (k & 1) ans*=base;
base*=base;
k >>= 1;
}
return ans;
}
快速幂取余数
int quickPowerWithMod(int a, int k, int mod) {
int ans=1, base=a;
while(k > 0) {
if (k & 1) {ans*=base; ans%=mod;}
base*=base; base%=mode;
k >>= 1;
}
}
约数打表初始化
vector<int> b[maxn]; // maxn为要找到约数的界限
for (int i = 1; i < maxn; ++i)
for (int j = 2*i; j < maxn; j+=i)
b[j].push_back(i);
for (int i:b[8]) {} // 1 2 4 => 得到了8的所有约数，不包括自己本身
排列组合数
ll factorial(ll n) {
ll fc = 1;
for (ll i = 1; i <= n; ++i) fc *= i;
return fc;
}
// Cnm
ll combo(ll n, ll m) {return factorial(n) / (factorial(m) * factorial(n - m));}
// Anm
ll permutation(ll n, ll m) {return factorial(n) / factorial(n - m);}
高精度
/* 组成部分 (5)：全局变量N；结构体的变量=>用来描述高精度数；重载的加减乘除以及其他运算符号；重载的输入输出流*/
// 全局变量N 最大的精度
const int N = 2005;
struct BigInt {
// 结构体变量
int len, s[N];
// 构造函数
BigInt() {memset(s, 0, sizeof(s));len = 1;}
BigInt(int num) { *this = num; }
BigInt(char *num) { *this = num; }
// 重载的各种运算符号
BigInt operator=(int num) {
char c[N];
sprintf(c, "%d", num);
*this = c;
return *this;
}
BigInt operator=(const char *num) {
len = strlen(num);
for (int i = 0; i < len; i++) s[i] = num[len - 1 - i] - '0';
return *this;
}
string str() {
string res = "";
for (int i = 0; i < len; i++) res = (char) (s[i] + '0') + res;
return res;
}
void clean() {while (len > 1 && !s[len - 1]) len--;}
BigInt operator + (const BigInt &b) {
BigInt c;
c.len = 0;
for (int i = 0, g = 0; g || i < len || i < b.len; i++) {
int x = g;
if (i < len) x += s[i];
if (i < b.len) x += b.s[i];
c.s[c.len++] = x % 10;
g = x / 10;
}
return c;
}
BigInt operator - (const BigInt &b) {
BigInt c;
c.len = 0;
int x;
for (int i = 0, g = 0; i < len; i++) {
x = s[i] - g;
if (i < b.len) x -= b.s[i];
if (x >= 0) g = 0;
else {
x += 10;
g = 1;
};
c.s[c.len++] = x;
}
c.clean();
return c;
}
BigInt operator * (const BigInt &b) {
BigInt c;
c.len = len + b.len;
for (int i = 0; i < len; i++) for (int j = 0; j < b.len; j++) c.s[i + j] += s[i] * b.s[j];
for (int i = 0; i < c.len - 1; i++) {
c.s[i + 1] += c.s[i] / 10;
c.s[i] %= 10;
}
c.clean();
return c;
}
bool operator < (const BigInt &b) {
if (len != b.len) return len < b.len;
for (int i = len - 1; i >= 0; i--)
if (s[i] != b.s[i]) return s[i] < b.s[i];
return false;
}
BigInt operator += (const BigInt &b) {
*this = *this + b;
return *this;
}
BigInt operator -= (const BigInt &b) {
*this = *this - b;
return *this;
}
};
// 重载的输入输出流
istream &operator>>(istream &in, BigInt &x) {
string s;
in >> s;
x = s.c_str();
return in;
}
ostream &operator<<(ostream &out, BigInt &x) {
out << x.str();
return out;
}
时间
// 判断闰年
bool isRun(int y) {
if (y%4 == 0)
if (y%100 == 0)
if (y%400 == 0) return true;
else return false;
else return true;
else return false;
}
// 计算到0000年1月1日00:00的总时间（得分钟数）
ull calTime(int y, int m, int d, int h, int min) {
ull ans, days = 0;
for (int i = 0; i < y; ++i)
if (isRun(i)) days += 366;
else days += 365;
if (isRun(y)) month[2] = 29;
else month[2] = 28;
for (int i = 1; i < m; ++i) days += month[i];
ans = (days+d-1)*1440+h*60+min;
return ans;
}
// 得区间段的总时间
ull period_time = calTime(ed_time)-calTime(bg_time);
基础算法
二分-整数
bool check(int tg) {
if() return true;
return false;
}
// 初始化二分的左右边界以及中间索引和值 l, r, mid, ans
int l = 0, r = maxx, mid, ans;
while (l<=r) {
mid = (l+r)>>1;
int tm = 0;
if (check(mid)) l = (ans=mid)+1;
else r = mid-1;
}