inlineintread(){ int x = 0, f = 0; char c = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = x * 10 + (c & 15), c = getchar(); return f ? -x : x; }
如果前面有负号，隔着一段是数字的话这个板子会出错。
对拍
遇到那种能看出来很容易挂分的题，或是时间充裕一定要对拍！！！
1 2 3 4 5 6 7 8
while(true) { // make data system("t1 < in > out1"); system("t2 < in > out2"); if (system("fc a.out b.out /W")) { system("pause"); exit(0); } }
STL
枚举全排列
1 2 3 4
for (int i = 1; i <= n; i ++) a[i] = i; do {
} while (next_permutation(a + 1, a + n + 1));
字符串
string 转 char[] ：成员函数 c_str()
char[] 转 string：重载了 = 运算符
重载运算符
1 2
intoperator+(const node &b) const { }
Lambda
Lambda 写全局似乎会莫名 CE。
尽量少用。
二分
1 2 3 4 5 6
int l = 0, r = INF; while (l <= r) { int mid = l + r >> 1; check(mid) ? res = mid, l = mid - 1 : r = mid + 1; } // res 就是答案
lower_bound 大于等于。
upper_bound大于。
背包
01 完全多重 现推。
二维费用就开两维的状态。
混合判断一下物品类型用各自的转移。
分组对组做 01，要先枚举组再枚举背包大小再枚举 组内物品。
方案数记录转移就行。
枚举二进制子集
1 2
for (int j = i; j; j = (j - 1) & i) { }
DDP
乘变加，加变 max。
概率期望
期望等于值乘概率
期望的线性性质
四边形不等式
相交大于包含。
分治，类似莫队。
字符串
字符串下标从 1 开始。
1 2 3 4
for (int i = 2, j = 0; i <= n; i ++) { while (j && s[j + 1] != s[i]) j = nex[i]; if (s[j + 1] == s[i]) j ++; nex[i] = j; }
如果真的遇到了 Z 函数马拉车直接二分哈希。有时间的话尽量写双哈希。
快速幂
先把底数取个模。
exgcd
1 2 3 4 5 6
intExgcd(int a, int b, int &x, int &y){ if (!b) { x = 1; y = 0; return a; } int d = Exgcd(b, a % b, x, y); int t = x; x = y; y = t - (a / b) * y; return d; }
数论分块
1 2 3
for (int l = 1, r = 0; l <= n; l = r + 1) { r = n / (n / l); }
欧拉函数
1 2 3 4 5 6 7 8 9 10
for (int i = 2; i < N; i ++) { if (!vis[i]) phi[i] = i - 1; for (j is prime) { if (i % j == 0) { phi[i * j] = phi[i] * j; } else { phi[i * j] = phi[i] * (j - 1); } } }
求单个欧拉函数
扩欧
gcd 不是 1 并且大于 就模完加 。
数论其余部分暂时放一下罢。
卡特兰数
反射原理。
线性基
1 2 3 4 5 6 7
voidadd(int x){ for (int i = 32; i >= 0; i --) { if (!(x >> i & 1)) continue; if (a[x]) x ^= a[x]; else { a[x] = x; break; } } }
图论
非严格次小生成树
在最小生成树的路径上找最大值替换。
严格次小生成树
倍增时维护最大值和严格次大值。
瓶颈生成树
边权最大值最小的生成树。
最小生成树一定是瓶颈生成树。但不必要。
Kruskal 重构树
原图两点路径最大边权的最小值 = 重构树上 LCA 的点权。
Prim
每次选距离当前树点最近的点加入生成树。
使用堆优化复杂度 。
dij
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
voiddij(){ memset(vis, 0, sizeof vis); memset(dis, 0x3f, sizeof dis); priority_queue<pii> p; p.emplace(0, 1), vis[1] = 1, dis[1] = 0; while (!p.empty()) { int x = p.top().second; p.pop(); if (vis[x]) continue; vis[x] = 1; for (auto [y, v] : e[x]) { if (dis[x] + v < dis[y]) { dis[y] = dis[x] + v; p.emplace(-dis[y], y); } } } }
spfa
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
voidspfa(){ memset(vis, 0, sizeof vis); memset(dis, 0x3f, sizeof dis); queue<int> p; p.push_back(1), vis[1] = 1, dis[1] = 0; while (!p.empty()) { int x = p.top(); p.pop(); vis[x] = 0; for (auto [y, v] : e[x]) { if (dis[x] + v < dis[y]) { dis[y] = dis[x] + v; if (!vis[y]) p.push_back(y), vis[y] = 1; } } } }