简介面向ACM竞赛与算法学习者的基础算法模板PDF集中收录竞赛高频且易错的基础模块。内容覆盖快速读入、高精度加减乘除、快速幂、组合数与排列数模运算、质数判定、分解质因数、欧拉筛等同时包含最大公约数、最小公倍数及整数二分与浮点数二分模板适合备赛时快速查阅与反复背诵。资源为单个PDF文件体积仅513KB便于移动端离线查看资源包清爽无冗余。目前已有224人浏览学习适合考前快速查阅。借助这些模板读者可以省去重复推导底层数学过程直接套用经优化的实现每个函数均给出参数含义与边界处理说明尤其在高精度运算和整数二分边界处理上能有效规避常见RE/TLE风险适合竞赛选手、考研机试及算法入门者按需取用。1. 模板不是拿来查的是拿来默写的先弄清这份模板库解决什么问题《ACM基础算法模板2》这个标题重点不在“模板”在“默写”。我见过太多人开源模板库收藏了几百个文件样例也都能跑真上了赛场板子没带或者带了也翻不到最后还是用最原始的循环硬写。模板解决的是“有思路但代码写不快、写不对”的问题树状数组的下标关系、线段树的懒标记、KMP 的 next 回退这些靠临时推导一定出错靠肌肉记忆才能稳。这个标题里的“2”也不是第二遍抄代码而是把模板按使用频率分层第二层正是数据结构、字符串和剪枝这些“基础中的进阶”。适合 ACM 新人自建模板库也适合准备机试的算法工程师候选人和蓝桥杯选手。2. 先把手速练上去快读快写、类型配置与对拍脚本ACM 竞赛和机试的输入输出格式有个共同点数据量动辄十万、百万级别输入输出本身就可能成为瓶颈。很多人在本地用 cin 测试感觉不到问题交上去才发现 IO 占了大部分运行时间。所谓 ACM 模式就是所有输入输出都得自己控制没有现成的评测函数帮你读好数据所以模板库的第一页应该是 IO 工具而不是算法。2.1 快读快写模板一份能处理负数和 EOF 的 C 实现我一般会把快读封装成这样适合 int 和 long long负数、文件结束都能正确处理#include bits/stdc.h using namespace std; // 快读模板支持 long long 和 int能处理负号与 EOF inline long long readLong() { long long x 0, f 1; char c getchar(); while (c ! - (c 0 || c 9)) { // 跳过空白与非法字符 if (c EOF) return -1; // 读到文件末尾由外层判断 c getchar(); } if (c -) { f -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; } int main() { long long n, x; while ((n readLong()) ! -1) { // 多组数据场景 x readLong(); printf(%lld\n, x); } return 0; }这段代码的关键在两个地方。一是跳过非数字字符时把 EOF 单独拎出来返回 -1这样多组数据读到文件末尾时循环能正常退出不会死循环二是先判断负号再累加数字避免把负号当成数字处理。参数上f 是符号位x 是累加结果返回 x * f 就是真实值。要注意的是这里用 getchar 而不是 cin因为 getchar 在大量整数输入时比 scanf 还要快一截。快读不是万能的浮点数快读写起来容易出错我通常直接用 scanf 处理 double字符串按行读取用 gets 或 getline 都行不需要套快读。如果你用的评测平台不支持 bits/stdc.h把头文件换成 vector、queue、cstdio 这些具体项即可。2.2 对拍脚本把“样例过了但提交 WA”变成十分钟定位模板库能不能在你的机器上放心用效率最高的验证方式不是手造样例而是对拍。对拍的意思是用数据生成器随机造输入分别跑你的模板实现和一个确定正确的“暴力/标准”程序对比输出。#!/bin/bash # 对拍脚本随机生成数据同时跑两份程序并比较输出 for i in $(seq 1 10000); do python3 gen.py input.txt # 生成一组随机测试数据 ./std input.txt ans.txt # 标准程序或暴力程序 ./my input.txt out.txt # 待验证的模板程序 if ! diff -q ans.txt out.txt /dev/null; then echo 第 $i 组数据不一致 break fi done使用时std 和 my 分别是两个编译好的可执行文件gen.py 是数据生成器。这里 gen.py 就是你的“测试用例模板”里面故意混入边界数据比纯随机更有价值import random, sys # 生成器默认随机 n边界模式下输出最小规模 if len(sys.argv) 1 and sys.argv[1] edge: print(1) # n 1 else: n random.randint(1, 100000) print(n) for _ in range(n): print(random.randint(-10**9, 10**9))对拍脚本里最容易被忽略的是 std 程序本身。它不要求高效但必须逻辑简单到不可能错通常用暴力枚举实现。比如验证树状数组std 就写一个普通数组直接累加不做任何优化。对拍一万组数据发现不了问题就把数据量加大到十万组同时把 gen.py 的输出范围缩小让冲突更密集。2.3 默认配置表一进考场先敲这三行我的模板库每个文件顶部都有一段固定配置避免每道题都临时想类型和常量配置项推荐写法为什么这样写整数类型typedef long long ll;多数题目答案超过 int 范围统一用 long long 省心无穷大const ll INF 0x3f3f3f3f3f3f3f3f;两个 INF 相加不会溢出且 memset 按字节填充后仍是这个值数组大小const int MAXN 100010;题目给的范围加 10避免下标越界输入同步ios::sync_with_stdio(false); cin.tie(0);要在用 cin 时减少开销但注意别和 scanf 混用两个 INF 相加不会溢出这一条在最短路径里特别重要后面避坑章节会展开讲。不管用不用快读类型名统一成 ll 能让所有模板之间直接互相调用不会出现 int 和 long long 混着传参的告警。3. 数据结构三件套的默认写法树状数组、线段树与并查集ACM 基础算法模板里数据结构部分是出镜率最高的。树状数组、线段树、并查集这三样覆盖了大多数“维护序列信息”的题目也是模板最容易写错的地方。它们的共同特点是代码短、逻辑固定、边界条件苛刻特别适合背成模板。3.1 树状数组模板单点更新与区间查询的最小实现树状数组的核心就两个函数约十行代码但下标关系非常容易记反const int MAXN 100010; int c[MAXN], n; // 单点加i 从当前点向后更新直到越界 inline void add(int i, int v) { while (i n) { c[i] v; i i (-i); } } // 前缀和i 向前累加直到 0 inline long long sum(int i) { long long s 0; while (i 0) { s c[i]; i - i (-i); } return s; }记忆口诀就一句更新往右上走查询往左上走。这里 i (-i) 取的是 i 二进制最低位的 1也就是 lowbit。add 里 i lowbit(i) 覆盖所有包含 c[i] 的祖先节点sum 里 i - lowbit(i) 累加所有前缀块。注意树状数组下标必须从 1 开始如果数据本身从 0 开始读入时先加 1否则 i0 时 i i (-i) 永远等于 0直接死循环。这段模板只支持单点更新、区间查询。如果题目要求区间加、区间求和需要把差分思想套进来用树状数组维护差分数组前缀和公式拆成两部分分别查询。那个模板比这个多一个公式但底层还是这两个函数。3.2 线段树模板带懒标记的区间修改与查询树状数组能解决的问题有限涉及区间加、区间赋值、区间最大值的时候就得线段树出场。线段树模板里最容易写错的是懒标记所以我给的版本把 pushdown 单独拆出来统一在每个递归函数里最先调用const int MAXN 100010; long long tree[MAXN 2], lazy[MAXN 2]; // 下传懒标记只下传一层左儿子右儿子分别累加 void pushdown(int p, int l, int r) { if (lazy[p] 0) return; int m (l r) 1; int lc p 1, rc p 1 | 1; tree[lc] lazy[p] * (m - l 1); tree[rc] lazy[p] * (r - m); lazy[lc] lazy[p]; lazy[rc] lazy[p]; lazy[p] 0; } // 建树从数组 a 初始化线段树 void build(int p, int l, int r, long long a[]) { if (l r) { tree[p] a[l]; return; } int m (l r) 1; build(p 1, l, m, a); build(p 1 | 1, m 1, r, a); tree[p] tree[p 1] tree[p 1 | 1]; } // 区间加完全覆盖时只更新当前节点并打标记 void add(int p, int l, int r, int L, int R, long long v) { if (L l r R) { tree[p] v * (r - l 1); lazy[p] v; return; } pushdown(p, l, r); int m (l r) 1; if (L m) add(p 1, l, m, L, R, v); if (R m) add(p 1 | 1, m 1, r, L, R, v); tree[p] tree[p 1] tree[p 1 | 1]; } // 区间查询同样先下传懒标记再递归 long long query(int p, int l, int r, int L, int R) { if (L l r R) return tree[p]; pushdown(p, l, r); int m (l r) 1; long long res 0; if (L m) res query(p 1, l, m, L, R); if (R m) res query(p 1 | 1, m 1, r, L, R); return res; }参数 p 是当前节点编号l、r 是当前节点管辖区间L、R 是操作区间。完全覆盖的判断条件是 L l r R此时不需要往下递归只改当前树节点并给 lazy 打标部分覆盖时先 pushdown 再递归两边子树最后 tree[p] 由两个儿子合并。注意数组一定要开四倍空间MAXN 2 是底线有些题目要五倍才保险。3.3 并查集模板路径压缩到底够不够用并查集是竞赛里最简单的数据结构但很多人只写路径压缩不写按秩合并。大部分题目确实只靠路径压缩就够了但反复 merge 成一条链的卡时间数据存在模板里带上按秩合并几乎不增加代码量int fa[MAXN], sz[MAXN]; // 初始化每个节点单独成集合集合大小为 1 void init(int n) { for (int i 1; i n; i) { fa[i] i; sz[i] 1; } } // 查找路径压缩递归版代码短 int find(int x) { return fa[x] x ? x : (fa[x] find(fa[x])); } // 合并把小的集合合并到大的集合里 void merge(int a, int b) { a find(a); b find(b); if (a b) return; if (sz[a] sz[b]) swap(a, b); fa[b] a; sz[a] sz[b]; }find 的递归版在联赛环境下一般不会爆栈如果你实在担心深度改成迭代版也不难。merge 里先 find 再比较 size能保证树高维持在 O(log n) 级别。并查集在 Kruskal 最小生成树里配合边排序用是图论模板里的标准前置工具。4. 图论与字符串最短路径模板、KMP 与暴力枚举的剪枝框架基础算法模板的第二层通常集中在图论和字符串上外加一个经常被忽视的“暴力枚举”类。枚举算法看起来不需要模板但剪枝方向写不完整复杂度就是 2 的 n 次方和 n 的平方的差距。这一章把三类高频场景一次讲清楚。4.1 单源最短路模板优先队列 Dijkstra 和它的两个边界不带负权的最短路我用优先队列 Dijkstra 当默认模板因为它对稀疏图友好且代码不容易写错const int MAXN 100010; struct Edge { int to, w; }; vectorEdge g[MAXN]; long long dis[MAXN]; bool vis[MAXN]; // 从起点 s 跑单源最短路结果存在 dis 里 void dijkstra(int s) { memset(dis, 0x3f, sizeof(dis)); dis[s] 0; priority_queuepairlong long, int, vectorpairlong long, int, greater pq; pq.push({0, s}); while (!pq.empty()) { auto now pq.top(); pq.pop(); long long d now.first; int u now.second; if (vis[u]) continue; // 已经出过队的节点跳过 vis[u] true; for (auto e : g[u]) { if (dis[e.to] d e.w) { dis[e.to] d e.w; pq.push({dis[e.to], e.to}); } } } }优先队列里 pair 的 first 是当前距离second 是节点编号greater 让队列按距离从小到大出队。vis 标记不能在建堆时打要在出队时打否则同一个节点可能被多个松弛操作反复入队。模板有两个边界要记得稠密图比如 n1000、m50 万直接用 O(n^2) 的朴素写法反而更快堆优化的 log 常数在这种图上不划算遇到负权边不能用 Dijkstra要么 SPFA 要么 Bellman-Ford把模板切换条件写进注释里比赛时少踩很多坑。4.2 字符串匹配模板KMP 的 next 数组与字典树的静态写法字符串匹配在基础模板里占两席单模式串匹配用 KMP多模式串前缀匹配用字典树。KMP 的难点是 next 数组的定义和回退逻辑// 构建 next 数组nxt[i] 表示 p[0..i] 的最长相等前后缀长度 vectorint build_next(const string p) { int m p.size(); vectorint nxt(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) j nxt[j - 1]; // 回退到上一个前缀 if (p[i] p[j]) j; nxt[i] j; } return nxt; } // KMP 匹配返回 p 在 s 中首次出现的下标没有则返回 -1 int kmp(const string s, const string p) { vectorint nxt build_next(p); for (int i 0, j 0; i (int)s.size(); i) { while (j 0 s[i] ! p[j]) j nxt[j - 1]; if (s[i] p[j]) j; if (j (int)p.size()) return i - j 1; } return -1; }这里 nxt[i] 存的是“p[0..i] 子串的最长相等前后缀长度”而不是传统教材里的“失配时跳到哪”。两种定义在实现上差一个下标偏移建议固定住一种写法每次默写都按同一个逻辑来。匹配过程中j 回退到 nxt[j-1] 而不是 nxt[j]就是因为数组存的是长度。KMP 的时间复杂度是 O(nm)模板本身没什么可调的容易被坑的是 p 为空串、s 和 p 长度相等这类边界。字典树我推荐静态数组版本节点用 int 数组模拟避免 new/delete 的开销和内存泄漏const int MAXN 100010; struct TrieNode { int nxt[26]; int cnt; } trie[MAXN]; int tot 0; // 插入一个字符串每经过一个节点计数加一 void insert(const string s) { int u 0; for (char c : s) { int id c - a; if (!trie[u].nxt[id]) trie[u].nxt[id] tot; u trie[u].nxt[id]; } trie[u].cnt; }nxt 数组的大小是节点数乘以字符集大小如果只含小写字母就是 26 个分支。tot 相当于内存池指针插入新分支时分配。这个模板用来做前缀统计、单词是否存在、异或最大值都很顺手。需要提醒的是字符集是数字或大写字母时把 26 改成对应大小别让下标越界。4.3 暴力枚举模板剪枝算法不是玄学是三个固定方向很多选手不把暴力枚举当模板认为就是 for 循环嵌套。实际遇到搜索题能不能把复杂度砍下来取决于你心里有没有一张剪枝清单。我的模板里会固定写这样一个框架// 子集枚举的 DFS 剪枝框架选或不选 可行性剪枝 int a[MAXN], n, limit, ans 0; void dfs(int step, int cur_sum) { if (cur_sum limit) return; // 可行性剪枝已经超限不必继续 if (step n) { ans max(ans, cur_sum); return; } dfs(step 1, cur_sum); // 不选当前元素 dfs(step 1, cur_sum a[step]); // 选当前元素 }剪枝算法就三个方向可行性剪枝当前状态已经非法直接 return、最优性剪枝当前结果不可能比已知更优直接 return、对称性剪枝通过排序或标记避免重复组合。上面对应的是可行性剪枝最优性剪枝要加一个 cur_sum 上界判断对称性剪枝则通常用在组合枚举里。这个框架看着简单但当你把每个 dfs 入口都问一遍“这三个剪枝是否缺失”时很多搜索题就从超时变成能过。5. 避坑记录模板翻车的五个高频现场与排查思路模板写多了翻车现场其实非常集中。这一章把最常见的五个问题按“现象-原因-解决”拆开你能直接对照排查。5.1 树状数组死循环下标从 0 开始直接卡死现象程序本地跑样例正常提交后 TLE 或程序无响应单步调试发现 add 函数停不下来。原因数据某个值为 0传入 add 后 i i (-i)当 i0 时 lowbit 也是 0循环条件永远满足死循环。解决所有树状数组相关下标强制从 1 开始读入数据后先执行x或idx。这个习惯要写进模板注释里不能靠每次临时提醒。5.2 线段树查询错误懒标记没在递归之前下传现象做区间加之后马上查询单点结果比预期小而且差的数值刚好是之前区间加的值。原因区间加时完全覆盖的节点只更新了 tree 和 lazy子节点没有同步变化。下一次查询如果只落到子节点自然读不到刚才的增量。解决在 add 和 query 里凡是需要进入子树递归的路径统一在递归前调用 pushdown。我的习惯是 pushdown 只写一次放在递归调用之前那个位置保证每个进入子树的路径都先下传当前节点的懒标记。如果查询和修改交叉进行别省这一步。5.3 INF 设置错误0x7fffffff 在最短路径里溢出成负数现象最短路模板在数据量稍微大一点时dis 数组出现负数路径全乱。原因初始化用了const int INF 0x7fffffff当dis[u] e.w超过 int 最大值时溢出变成负值Dijkstra 把负数当成更短路径继续松弛。解决统一用0x3f3f3f3f作为 int 的 INF两个 0x3f3f3f3f 相加接近 21 亿不超过 int 上限用 long long 时用0x3f3f3f3f3f3f3f3f。同时用memset(dis, 0x3f, sizeof(dis))初始化memset 按字节填充结果正好是 INF 本身。5.4 堆优化 Dijkstra 在稠密图上反而更慢现象n1000、m50 万的图堆优化 Dijkstra 跑了 O(n^2) 两倍以上的时间。原因堆优化的瓶颈在堆操作上每条边都有可能入堆出堆m 达到几十万时log 级别的堆操作常数被放大而 n1000 时 O(n^2) 只有一百万次扫描反而更快。解决模板里同时保留两份最短路实现稠密图用朴素for找最小点稀疏图用优先队列。判断条件就是m n * (n - 1) / 2的一半时切朴素写法比赛时把这个注释写在函数名旁边换题不换模板。5.5 对拍脚本在 Windows 环境跑不起来现象在 Windows 下写完对拍脚本bash 执行报错command not found或者 diff 结果永远不一致。原因两个常见问题脚本文件保存成了 CRLF 换行符bash 把行尾的\r当成命令的一部分二是python3命令在 Windows 下可能是python。解决用dos2unix 对拍.sh转换一次换行符或者在 Git Bash 里重新保存为 LF脚本开头用#!/bin/bash命令名写成兼容变量PYpython3Windows 下改成PYpython。对拍脚本本身也是模板存进模板库时要保证跨平台能跑。6. 给新模板做冒烟测试一份边界数据构造清单模板写进库里不等于能用我习惯在每份模板旁边放一个边界数据生成器把最容易触发 bug 的输入写死先跑一遍再上对拍。这份清单比随机数据可靠得多边界类型测试意图n 1最小规模检查初始值和单元素路径是否正确n 最大值检查数组大小、递归深度、时间是否可接受全部相同压测懒标记、树状数组重复更新、排序稳定性逆序输入检查排序/最短路对前驱顺序的依赖最小值混合负数验证快读负号、INF 溢出、前缀和符号对应的生成器可以做成一个带参数的小脚本mode 控制输出哪种边界import random, sys mode sys.argv[1] if len(sys.argv) 1 else random n random.randint(1, 100000) if mode min: n 1 elif mode same: n 100000 elif mode reverse: n 100000 print(n) for i in range(n): if mode same: print(7) elif mode reverse: print(n - i) elif mode negative: print(random.randint(-10**9, -1)) else: print(random.randint(-10**9, 10**9))跑法很简单先python3 gen.py min | ./my再依次换 same、reverse、negative每份模板改一次生成器参数几十秒就能确认基本盘没问题。这个动作不算复杂但真的能拦住大部分翻车事故。我之前最短路的 INF 就调过一整晚最后发现是两个 0x7fffffff 相加溢出成负数从那以后每份模板进库先跑边界数据再交给对拍脚本做十万组随机验证。模板的价值不在数量在于它能让你在赛场上少想十秒钟、少错一个下标。希望这份清单对你也有用。本文还有配套的精品资源点击获取