CSP 普及 & 提高 考点
零、杂项
加速 cin/cout：ios::sync_with_stdio(false);。注：放在 main 函数的第一行，但使用它之后不能使用 scanf/printf。
快读：
inline int rd(){
int x = 1, s = 0; char ch = getchar();
while(ch < '0' or ch > '9'){if(ch == '-') x = -1; ch = getchar();}
while(ch >= '0' and ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return x * s;
}
快写：
inline void wr(int x){
if(x < 0) putchar('-'), x *= -1;
if(x > 9) wr(x / 10);
putchar(x % 10 + '0');
}
一、博弈论
Bash/Wythoff/Nimm Game
二、字符串
KMP
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
int kmp[maxn];
int lena, lenb;
char a[maxn], b[maxn];
int main ()
{
scanf ("%s %s", a + 1, b + 1);
lena = strlen (a + 1), lenb = strlen (b + 1);
for (int i = 2, j = 0; i <= lenb; i++)
{
while (j and b[i] != b[j + 1]) j = kmp[j];
if (b[i] == b[j + 1]) j++;
kmp[i] = j;
}
int j = 0;
for (int i = 1; i <= lena; i++)
{
while (j and b[j + 1] != a[i]) j = kmp[j];
if (b[j + 1] == a[i]) j++;
if (j == lenb)
{
printf ("%d\n", i - lenb + 1);
j = kmp[j];
}
}
for (int i = 1; i <= lenb; i++) printf ("%d ", kmp[i]);
return 0;
}
AC自动机
字符串哈希
Trie树（图）
manacher
最小表示法
图
最短路
spfa （判负环）
dijkstra （堆优化 & 线段树优化）
倍增 floyd
差分约束
Tarjan
强连通分量/缩点
点双边双
割点割边、桥
2-sat
拓扑排序
- 二分图（最大匹配-匈牙利 & 最大权匹配-KM）
- 网络流（大概不考，熟悉板子即可）
- 分数规划（提高考）
- 欧拉图
树
- 最小生成树
- Kruskal（生成树） & Prim 堆优化
- （严格）次小生成树
- 最大生成树
- 【选】最优比率、最小瓶颈生成树
- LCA
- 基环树
- 树链剖分
- 括号序列
- dfs序
- 树上倍增
- 树的直径、树的重心
数论
- 埃氏筛、线性筛
- 欧拉函数
- 欧拉定理
- 线性筛欧拉函数
- sqrt(n)求单个值的欧拉函数
- exgcd
- 求逆元
- 求同余方程
- 求 \(ax + by = c\)
- 中国剩余定理-互质版
- 矩阵快速幂
- 容斥原理-Ramsey定理
- 费马小定理
- 逆元（线性求、exgcd求、费马小定理求）
- 高斯消元
- 线性基
- 排列组合-杨辉三角
- 斐波那契数列-\(\gcd(f_n, f_m)=f[\gcd(n,m)]\)
- 卡特兰数
- 【选】斯特林数、贝尔数
- 概率 & 期望
动态规划
- 简单 dp
- 背包 dp
- 01 背包
- 完全背包
- 多重背包
- 区间 dp
- 状压 dp （普通状压 & 枚举子集 dp）
- 数位 dp
- 树形 dp （基环树 dp）
- 环形 dp
- 环 + 外向树上的 dp
- 期望 dp
- dp 套 dp
- 优化
- 【选】四边形不等式
- 单调队列、线段树
数据结构
- 带权并查集
- 哈希表
- 双向列表
- st 表
- 树状数组 （求逆序对 & 多维）
- 线段树
- 动态开点 & 线段树的合并
- 权值线段树
- 【选】zkw 线段树
- 二维线段树
- 主席树 （静态 & 动态 第 \(k\) 大）
- 扫描线
- 平衡树 （splay、treap、无旋 treap）
- trie 树
- STL（(multi)set）
搜索
- bfs/dfs
- 双向 bfs
其他算法思想
- 二分、三分
- 倍增
- 贪心
- 分治
- 离散化
- 模拟
- 排序（重载运算符）
- 分块
- （二维）前缀和
- （压位）高精度
- 矩阵加速递推
- 打表