第1页 / 共267页
第2页 / 共267页
第3页 / 共267页
第4页 / 共267页
第5页 / 共267页
第6页 / 共267页
第7页 / 共267页
第8页 / 共267页
kuangbin的ACM模板（2018.7更新）.pdf
字符串处理
KMP
e-KMP
Manacher
AC自动机
后缀数组
DA
DC3
后缀自动机
基本函数
例题
字符串hash
数学
素数
素数筛选（判断
素数筛选（筛选出小于等于MAXN的素数）
大区间素数筛选（POJ 2689）
素数筛选和合数分解
扩展欧几里得算法（求ax+by=gcd的解以及逆元）
求逆元
扩展欧几里德法
简洁写法
利用欧拉函数
模线性方程组
随机素数测试和大数分解(POJ 1811)
欧拉函数
分解质因素求欧拉函数
筛法欧拉函数
求单个数的欧拉函数
线性筛（同时得到欧拉函数和素数表）
高斯消元（浮点数）
FFT
高斯消元法求方程组的解
一类开关问题，对2取模的01方程组
解同余方程组
整数拆分
求AB的约数之和对MOD取模
莫比乌斯反演
莫比乌斯函数
例题：BZOJ2301
Baby-Step Giant-Step
自适应simpson积分
斐波那契数列取模循环节
原根
快速数论变换
HDU4656 卷积取模
其它公式
Polya
数据结构
划分树
RMQ
一维
二维
树链剖分
点权
边权
伸展树（splay tree）
例题：HDU1890
例题：HDU3726
动态树
SPOJQTREE
SPOJQTREE2
SPOJQTREE4
SPOJQTREE5
SPOJQTREE6
SPOJQTREE7
HDU4010
主席树
查询区间多少个不同的数
静态区间第k大
树上路径点权第k大
动态第k大
Treap
KD树
HDU4347 K近邻
CF44G
HDU4742
替罪羊树(ScapeGoat Tree)
CF455D
动态KD树
树套树
替罪羊树套splay
图论
最短路
Dijkstra单源最短路
Dijkstra算法+堆优化
单源最短路bellman_ford算法
单源最短路SPFA
最小生成树
Prim算法
Kruskal算法
次小生成树
有向图的强连通分量
Tarjan
Kosaraju
图的割点、桥和双连通分支的基本概念
割点与桥
模板
调用
边双连通分支
点双连通分支
最小树形图
二分图匹配
邻接矩阵（匈牙利算法）
邻接表（匈牙利算法）
Hopcroft-Karp算法
二分图多重匹配
二分图最大权匹配（KM算法）
一般图匹配带花树
一般图最大加权匹配
生成树计数
最大流
SAP邻接矩阵形式
SAP邻接矩阵形式2
ISAP邻接表形式
ISAP+bfs初始化+栈优化
dinic
最大流判断多解
最小费用最大流
SPFA版费用流
zkw费用流
2-SAT
染色法（可以得到字典序最小的解）
强连通缩点法（拓扑排序只能得到任意解）
曼哈顿最小生成树
LCA
dfs+ST在线算法
离线Tarjan算法
LCA倍增法
欧拉路
有向图
无向图
混合图
树分治
点分治-HDU5016
*点分治-HDU4918
链分治-HDU5039
搜索
Dancing Links
精确覆盖
可重复覆盖
八数码
HDU1043反向搜索
动态规划
最长上升子序列O(nlogn)
背包
插头DP
HDU 4285
计算几何
二维几何
三维几何
平面最近点对
三维凸包
HDU4273
其他
高精度
完全高精度
strtok和sscanf结合输入
解决爆栈，手动加栈
STL
优先队列priority_queue
set和multiset
输入输出外挂
莫队算法
分块
Manhattan MST的dfs顺序求解
VIM配置
ACM 常用算法模板
kuangbin
http://www.cnblogs.com/kuangbin/
Email:kuangbin2009@126.com
Last build at July 8, 2018
Contents
1 字符串处理
ACM Template of kuangbin
5
1.1 KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2
e-KMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.3 Manacher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.4 AC 自动机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.5 后缀数组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 DA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2 DC3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 后缀自动机 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6.1 基本函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6.2 例题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.7 字符串 hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2 数学
25
2.1 素数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.1 素数筛选（判断
3 数据结构
ACM Template of kuangbin
56
3.1 划分树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2 RMQ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.1 一维 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.2 二维 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3 树链剖分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.1 点权 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.2 边权 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4 伸展树（splay tree） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4.1 例题：HDU1890 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4.2 例题：HDU3726 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.5 动态树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
SPOJQTREE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.5.1
SPOJQTREE2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
3.5.2
SPOJQTREE4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.5.3
SPOJQTREE5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.5.4
SPOJQTREE6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.5.5
3.5.6
SPOJQTREE7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.5.7 HDU4010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.6 主席树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.6.1 查询区间多少个不同的数 . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.6.2 静态区间第 k 大 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.6.3 树上路径点权第 k 大 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.6.4 动态第 k 大 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.7 Treap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.8 KD 树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.8.1 HDU4347 K 近邻 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.8.2 CF44G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.8.3 HDU4742 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.9.1 CF455D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
3.10 动态 KD 树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
3.11 树套树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.11.1 替罪羊树套 splay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.9 替罪羊树 (ScapeGoat Tree)
4 图论
130
4.1 最短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.1 Dijkstra 单源最短路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.2 Dijkstra 算法 + 堆优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.1.3 单源最短路 bellman_ford 算法 . . . . . . . . . . . . . . . . . . . . . . . 131
4.1.4 单源最短路 SPFA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.2 最小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.2.1 Prim 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.2.2 Kruskal 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.3 次小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.4 有向图的强连通分量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.4.1 Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.4.2 Kosaraju . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.5 图的割点、桥和双连通分支的基本概念 . . . . . . . . . . . . . . . . . . . . . . . 138
4.6 割点与桥 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
4.6.1 模板 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
kuangbin
2
ACM Template of kuangbin
4.6.2 调用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
4.7 边双连通分支 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
4.8 点双连通分支 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
4.9 最小树形图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
4.10 二分图匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.10.1 邻接矩阵（匈牙利算法） . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4.10.2 邻接表（匈牙利算法） . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
4.10.3 Hopcroft-Karp 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.11 二分图多重匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4.12 二分图最大权匹配（KM 算法） . . . . . . . . . . . . . . . . . . . . . . . . . . 153
4.13 一般图匹配带花树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
4.14 一般图最大加权匹配 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
4.15 生成树计数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.16 最大流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.16.1 SAP 邻接矩阵形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
4.16.2 SAP 邻接矩阵形式 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.16.3 ISAP 邻接表形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
4.16.4 ISAP+bfs 初始化 + 栈优化 . . . . . . . . . . . . . . . . . . . . . . . . . 165
4.16.5 dinic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.16.6 最大流判断多解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
4.17 最小费用最大流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
4.17.1 SPFA 版费用流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
4.17.2 zkw 费用流 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
4.18 2-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.18.1 染色法（可以得到字典序最小的解） . . . . . . . . . . . . . . . . . . . . 172
4.18.2 强连通缩点法（拓扑排序只能得到任意解） . . . . . . . . . . . . . . . . 173
4.19 曼哈顿最小生成树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
4.20 LCA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
4.20.1 dfs+ST 在线算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
4.20.2 离线 Tarjan 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
4.20.3 LCA 倍增法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
4.21 欧拉路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
4.21.1 有向图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
4.21.2 无向图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
4.21.3 混合图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
4.22 树分治 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.22.1 点分治 -HDU5016 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.22.2 * 点分治 -HDU4918 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
4.22.3 链分治 -HDU5039 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
5 搜索
205
5.1 Dancing Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.1.1 精确覆盖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.1.2 可重复覆盖 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
5.2 八数码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
5.2.1 HDU1043 反向搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
6 动态规划
212
6.1 最长上升子序列 O(nlogn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
6.2 背包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
6.3 插头 DP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
kuangbin
3
ACM Template of kuangbin
6.3.1 HDU 4285 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7 计算几何
218
7.1 二维几何 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
7.2 三维几何 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
7.3 平面最近点对 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
7.4 三维凸包 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
7.4.1 HDU4273 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
8 其他
249
8.1 高精度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
8.2 完全高精度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
8.3
strtok 和 sscanf 结合输入 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
8.4 解决爆栈，手动加栈 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
8.5 STL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
8.5.1 优先队列 priority_queue . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
8.5.2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
8.6 输入输出外挂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
8.7 莫队算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
8.7.1 分块 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
8.7.2 Manhattan MST 的 dfs 顺序求解 . . . . . . . . . . . . . . . . . . . . . . 260
8.8 VIM 配置 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
set 和 multiset
kuangbin
4
1 字符串处理
1.1 KMP
ACM Template of kuangbin
* next[] 的含义：x[i-next[i]...i-1]=x[0...next[i]-1]
* next[i] 为满足 x[i-z...i-1]=x[0...z-1] 的最大 z 值（就是 x 的自身匹配）
*/
1 /*
2
3
4
5 void kmp_pre(char x[],int m,int next[]){
6
7
8
9
10
11
12
13 }
14 /*
15
int i,j;
j=next[0]=−1;
i=0;
while(i=m){
ans++;
j=next[j];
int i,j;
int ans=0;
//preKMP(x,m,next);
kmp_pre(x,m,next);
i=j=0;
while(i
}
else{
47 }
48 //经典题目：POJ 3167
49 /*
50
51
52
53
54
55
56
57
58 const int MAXN=100010;
59 const int MAXM=25010;
60 int a[MAXN];
61 int b[MAXN];
62 int n,m,s;
63 int as[MAXN][30];
64 int bs[MAXM][30];
65 void init(){
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84 }
85 int next[MAXM];
86 void kmp_pre(){
87
88
89
90
91
92
93
94
95
96
97
int i,j;
j=next[0]=−1;
i=0;
while(i0)t11+=bs[i][k]−bs[i−j−1][k];
else t11+=bs[i][k];
}
if(i−j>0)t12=bs[i][b[i]]−bs[i−j−1][b[i]];
else t12=bs[i][b[i]];
kuangbin
6
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
最新资料
2022-2023学年河北省唐山市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末数学试题及答案.doc
2022-2023学年河北省衡水市高三上学期期末语文试题及答案.doc
2022-2023学年河北省保定市高三上学期期末数学试题及答案.doc
2022-2023学年河北省张家口市高三上学期期末语文试题及答案.doc
2022-2023学年河北省石家庄市高三上学期期末语文试题及答案.doc
2020-2021年四川省凉山州西昌市高一物理上学期期中试卷及答案.doc
2020-2021年四川省遂宁市安居区高一英语上学期期中试卷及答案.doc
2020-2021年四川省西昌市高一英语上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一地理上学期期中试卷及答案.doc
2021-2022年四川省成都市郫都区高一物理上学期期中试卷及答案.doc
2021-2022年四川省广安市岳池县高一物理上学期期中试卷及答案.doc