代码有时间再补。先把大致框架建出来。
大模拟
果断先打部分分然后换题，求稳。除非很一眼。
数论
这方面补的很少。希望不要考，毕竟我数学很差。
组合数
补药背错公式啊。
当 $n,m$ 很小的时候要用杨辉三角，致敬三倍大常数选手 Conan15。
Lucas 定理
不想学怎么证了，就记结论吧。
对于质数 $p$，有
$C_n^m \bmod p = C_{ \lfloor \frac{n}{p} \rfloor }^{ \lfloor \frac{m}{p} \rfloor } \times C_{n \bmod p}^{m \bmod p} \bmod p$。
卡特兰数
$Cat(n) = \frac{ C_{2n}^n }{ n+1 }$。
博弈论
要求会推 SG 函数，会猜结论，有耐心打表找规律。
当前问题的 SG 是子问题的 mex 值。
若干问题当 SG 异或为 $0$ 必败否则必胜。
快速幂
有手就行。
int qmi(int a, int k) {
int res = 1 % mod;
while (k) {
if (k & 1) res = res * 1ll * a % mod;
a = a * 1ll * a % mod;
k >>= 1;
}
return res;
}
高精度
NOIP 要是考高精除以高精，就等着被骂吧。
高精度有手就行，实在不行现推先写。
筛质数
埃氏筛法
void getprime(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) p[++tot] = i;
for (int j = i + i; j <= n; j += i) st[j] = 1;
}
}
线性筛
事实证明比埃氏筛法快了很多。
void getprime(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) p[++tot] = i;
for (int j = 1; j <= tot && i * p[j] <= n; j++) { //只筛 <= n 的合数
st[i * p[j]] = 1;
if (i % p[j] == 0) break;
/*
若 i % p[j] == 0，则后面的 i * p[k]（k > j） 由于 i 这一项包含 p[j]，一定被筛过了
要保证每个数只被最小质因子筛掉，才能保证时间复杂度是线性的。
*/
}
}
}
最大公约数
不清楚 __gcd 能不能用啊，手写不是更好？
最小公倍数是 a / g * b。建议先除后乘以免溢出。
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
矩阵乘法相关
不要把式子推错了。
我觉得这玩意儿还是有必要打一遍的。注意矩阵不满足交换律所以有左乘和右乘的问题。
以及矩阵快速幂。
Matrix mul(Matrix a, Matrix b) {
Matrix res; res.init();
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++) (res.a[i][j] += a.a[i][k] * 1ll * b.a[k][j] % mod) %= mod;
return res;
}
Matrix qmi(Matrix a, long long k) {
Matrix res; res.init();
for (int i = 0; i < 2; i++) res.a[i][i] = 1;
while (k) {
if (k & 1) res = mul(res, a);
a = mul(a, a);
k >>= 1;
}
return res;
}
高斯消元
魔怔了。考了算我倒霉。
动态规划
这东西纯靠积累吧。从多个角度思考一下要怎么设状态、处理转移以及优化。
背包
板。推。
区间 DP
补药小看区间 DP。每次分析问题都没想过它是不是区间 DP。
序列 DP
硬干。
树形 DP
摆。猜转移方程，然后一直不断地修改自己的转移方程。
斜率优化
希望能考一道斜率优化练练手（要是考了没做出来那对不起对不起对不起）。
数据结构优化
致敬 CSP-S 2024 T3。第一次接触数据结构优化 DP，没切红温了。
数据结构
STL
最近才知道 set 真的很好用。
合理利用 STL 可以节约时间，精简代码。
考前看一看 STL 函数列表 免得忘了。（在最底下）
链表
我觉得纯靠现推吧，背了又有什么用？
栈、队列、堆
这不纯硬干就完了。
单调栈和单调队列加个特判。记得别符号写错。
应该没人手写堆吧，浪费时间。
并查集
冰茶寄？并查集。
路径压缩？按秩合并。按秩压缩？路径合并。
感觉没什么好写的吧，注意初始化 p[i]=i，特别是按秩合并记得 sz[i]=1。
还有为什么会有人真的去写秩这个东西啊。直接 siz 就好了。
树状数组
线段树大常数害死 Conan15！！！
线段树
Conan15 喜欢线段树，但不喜欢要维护四五个懒标记以及神秘操作的线段树。
线段树是简单的，没必要再敲一遍。
ST 表
$O(1)$ 查询利器。原来 $O(1)$ LCA 是这么做的。
很久没写了，补药写挂啊。
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), Max[i][0] = a[i];
for (int i = 1; i <= 18; i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
Max[j][i] = max(Max[j][i - 1], Max[j + (1 << i - 1)][i - 1]);
while (m--) {
int l, r; scanf("%d%d", &l, &r);
int p = lg[r - l + 1];
printf("%d\n", max(Max[l][p], Max[r - (1 << p) + 1][p]));
}
树链剖分
幽默。你要是出树链剖分板子题我当场狂喜。
这个就不写了，板子挺好敲的。
图论
拓扑
记得把入度 -1。
if (--in[v] == 0)
最近公共祖先
倍增、树剖以及欧拉序 LCA。
求 LCA 下面一个点的时候建议用倍增，比较好写。
另外固定 $k$ 求树上每个点的 $k$ 级祖先不要再写 LCA 了，明明可以 dfs 用一个栈维护的。
二分图
考了算我倒霉。
复习：判定以及最大匹配。
这些东西我完全不理解。那就死记硬背吧。
- 最小点覆盖 = 最大匹配。
- 最大独立集 = 顶点总数 - 最大匹配。
- 最小边覆盖 = 顶点总数 - 最大匹配。
- 最小路径覆盖 = 顶点总数 - 最大匹配。
bool st[N];
int match[N], ans = 0;
int dfs(int u) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (st[v]) continue;
st[v] = 1;
if (!match[v] || dfs(match[v])) {
match[v] = u;
return 1;
}
}
return 0;
}
单源最短路
dijkstra
我是不是应该先复习一下 $O(n^2)$ 的朴素做法？不然稠密图就爆了。
我是不是要复习一下 $O(m \log m)$ 的优化做法？不然写成大根堆就爆了。
spfa
最短路
单向边加成双向边。遂 RP++。
queue< int > q;
bool st[N];
int d[N];
void spfa() {
q.push(1);
for (int i = 1; i <= n; i++) d[i] = INF;
d[1] = 0;
while (q.size()) {
int u = q.front(); q.pop();
st[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (d[v] > d[u] + w[i]) {
d[v] = d[u] + w[i];
if (!st[v]) q.push(v), st[v] = 1;
}
}
}
}
判负环
图不连通，遂 RP++。
queue< int > q;
bool st[N];
int d[N], cnt[N];
bool spfa() {
for (int i = 1; i <= n; i++) q.push(i), st[i] = 1; //图不联通！！！
for (int i = 1; i <= n; i++) d[i] = INF;
d[1] = 0;
while (q.size()) {
int u = q.front(); q.pop();
st[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (d[v] > d[u] + w[i]) {
d[v] = d[u] + w[i];
cnt[v] = cnt[u] + 1;
if (cnt[v] >= n) return 1;
if (!st[v]) q.push(v), st[v] = 1;
}
}
}
return 0;
}
Bellman-Ford
神金。这是什么东西！？！？
不学了！！！没见过有人用这东西。
多源最短路
Floyd
秒了。
可以处理传递闭包。但我已经忘了这是什么了。
树的直径
记住和端点有关！记住和端点有关！！记住和端点有关！！！
最小生成树
kruskal
以及 Kruskal 重构树。如果比较闲的话去了解一下点权多叉重构树（是这么称呼的吗？）
Prim
致敬模拟赛出了一道题，大致意思是模拟 Prim 的算法流程，但我没看出来。
int prim() {
for (int i = 1; i <= n; i++) d[i] = 0x3f3f3f3f; d[1] = 0;
int res = 0;
for (int i = 1; i <= n; i++) {
int id = 0, Min = 0x3f3f3f3f;
for (int j = 1; j <= n; j++) {
if (st[j]) continue;
if (Min > d[j]) Min = d[j], id = j;
}
if (Min == 0x3f3f3f3f) return 0x3f3f3f3f; //No solution
st[id] = 1, res += d[id];
for (int j = 1; j <= n; j++)
if (!st[j]) d[j] = min(d[j], w[id][j]); //不是 d[j] + w……
}
return res;
}
还有堆优化。
priority_queue< pair<int, int> > q;
int prim() {
for (int i = 1; i <= n; i++) d[i] = 0x3f3f3f3f;
q.push(make_pair(0, 1));
int res = 0, cnt = 0;
while (q.size() && cnt <= n) {
int u = q.top().second, dis = -q.top().first; q.pop();
if (st[u]) continue;
st[u] = 1, res += dis, cnt++;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (st[v]) continue;
q.push(make_pair(-w[i], v));
}
}
if (cnt != n) return 0x3f3f3f3f;
return res;
}
Tarjan 算法
玩牛魔的割点割边点双边双圆方树。给我分清楚！！！重点！！！
割点
特判根，而且是 father == 0 而不是 u==1。
int dfn[N], low[N], tot = 0, cnt = 0;
bool cut[N];
void tarjan(int u, int father) {
dfn[u] = low[u] = ++tot;
int child = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == father) continue;
if (!dfn[v]) {
tarjan(v, u), child++;
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u] && !cut[u] && father != 0) cut[u] = 1, cnt++;
} else low[u] = min(low[u], dfn[v]);
}
if (father == 0 && child >= 2 && !cut[u]) cut[u] = 1, cnt++;
}
割边
注意起点要特判。
int dfn[N], low[N], tot = 0;
vector< pair<int, int> > cut;
void tarjan(int u, int pre) {
dfn[u] = low[u] = ++tot;
for (int i = h[u]; ~i; i = ne[i]) {
if ((pre != -1) && i == pre || i == (pre ^ 1)) continue;
int v = e[i];
if (!dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
if (dfn[u] < low[v]) {
cut.push_back({min(u, v), max(u, v)});
}
} else low[u] = min(low[u], dfn[v]);
}
}
点双
根节点判 child == 0 而不是 >=2。
int dfn[N], low[N], tot = 0;
vector<int> vcc[N]; int cnt = 0;
int stk[N], top = 0;
void tarjan(int u, int father) {
dfn[u] = low[u] = ++tot;
stk[++top] = u;
int child = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == father) continue;
if (!dfn[v]) {
tarjan(v, u), child++;
low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v]) {
cnt++;
while (stk[top] != v) {
vcc[cnt].push_back(stk[top]);
top--;
}
vcc[cnt].push_back(v), top--;
vcc[cnt].push_back(u);
}
} else low[u] = min(low[u], dfn[v]);
}
if (father == 0 && !child) vcc[++cnt].push_back(u);
}
边双
int dfn[N], low[N], tot = 0;
void tarjan(int u, int pre) {
dfn[u] = low[u] = ++tot;
for (int i = h[u]; ~i; i = ne[i]) {
if ((pre != -1) && i == pre || i == (pre ^ 1)) continue;
int v = e[i];
if (!dfn[v]) {
tarjan(v, i);
low[u] = min(low[u], low[v]);
if (dfn[u] < low[v]) cut[i] = cut[i ^ 1] = 1;
} else low[u] = min(low[u], dfn[v]);
}
}
bool st[N];
vector<int> scc[N]; int cnt = 0;
void dfs(int u) {
st[u] = 1;
scc[cnt].push_back(u);
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (cut[i] || st[v]) continue;
dfs(v);
}
}
圆方树
void tarjan(int u) {
dfn[u] = low[u] = ++tot;
stk[++top] = u;
for (int v : edge[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u]) { //以 u 为根的点双
n2++; //新建一个方点
vcc[n2].push_back(u);
while (stk[top] != v) {
add(n2, stk[top]), add(stk[top], n2);
vcc[n2].push_back(stk[top]);
top--;
}
add(n2, stk[top]), add(stk[top], n2);
vcc[n2].push_back(stk[top]), top--; //stk[top] == v
add(u, n2), add(n2, u); //u 也要连边，但不弹栈
}
} else low[u] = min(low[u], dfn[v]);
}
}
字符串
玩牛魔的。只会 Trie 树和字符串哈希。
遇到字符串就等死吧。就像 2024.11.28 模拟赛 T3。少想了一个二分直接被送进工厂拧螺丝。
KMP 背不下来。KMP 背不下来。KMP 背不下来。KMP 背不下来。KMP 背不下来。
那就死磕吧。
for (int i = 2, j = 0; i <= n; i++) {
while (j && p[i] != p[j + 1]) j = nxt[j];
if (p[i] == p[j + 1]) j++;
nxt[i] = j;
}
for (int i = 1, j = 0; i <= m; i++) {
while (j && s[i] != p[j + 1]) j = nxt[j];
if (s[i] == p[j + 1]) j++;
if (j == n) {
cout<<i - n << ' ';
j = nxt[j];
}
}
其他
快读
开场打个快读促进血液循环。毕竟 FZ 还是挺冷的。
一维、二维 的 前缀和、差分
无。
离散化
无。
区间合并 & 区间选点
贪。
双指针
无。
位运算
给我狠狠地卡常！！！
二分
补药写错了。r=mid-1 的时候是 l+r+1>>1。
ama
ama