ACM算法模板实用指南：从分类抄写到赛场避坑

简介在算法竞赛和编程考试中算法模板是提升编码效率的关键工具。所谓算法模板是将常用数据结构、图论、动态规划等算法代码按固定结构整理形成可直接复用的代码骨架。其核心价值在于减少重复劳动让选手将精力集中在问题建模与调试上。合理组织模板库、区分背诵与查阅范围并熟悉快读、并查集、堆优化Dijkstra、背包DP等高频写法的边界条件能够显著降低赛场翻车概率。无论是备战ACM、考研机试还是日常刷题进阶一套经过实战验证的算法模板都能成为可靠的即时武器。本文基于《ACM基础算法模板2》的实践用法讲解如何分类、抄写、验证并迭代自己的模板库助你在赛场上更快更稳地写出AC代码。1. 《ACM基础算法模板2》到底是什么值得不值得背竞赛圈里流传最广的算法资料往往是那种写满模板的册子《ACM基础算法模板2》就是这类整理里比较新的一份。它解决的问题很直接当你拿到一个有难度的算法题心里已经知道该用哪种算法却总是卡在邻接表初始化、边界判断或状态转移的细节上写不下去。这份模板把常用数据结构、图论、动态规划等代码按固定写法整理出来让人在考场上少做重复劳动把时间留给建模和调试。看到“模板”两个字新手第一反应是背下来。我个人的看法恰恰相反模板不是拿来背的是拿来“抄”的。真正有效的用法是先把每个模板每一行的作用搞清楚再在比赛时按题目条件做少量修改。适合看这份整理的人主要有三类准备各类算法竞赛的在校学生、备战考研机试的考生以及刷题量不小但总是因为基础算法写得慢而翻车的从业者。如果翻开这本《ACM基础算法模板2》觉得内容很晕不用慌这是正常的。第一遍不建议从头读到尾而是当成字典用遇到对应题型再去翻对应章节。下面这篇笔记就按我自己的使用习惯讲一讲怎么把这份模板用出最大价值以及哪些地方最容易踩坑。2. 先把模板的体系立起来分类、骨架与背诵范围要用好一份模板集第一件事是理解它的归档结构。像《ACM基础算法模板2》这种第二版整理通常会把算法按主题归类常见的大类是数据结构、图论、动态规划、字符串、数论、计算几何。我自己的习惯是每个算法拆成一个独立文件文件名直接写算法名头部注释写好复杂度和适用边界。不建议把所有代码堆进一个长文件比赛时在一千行里翻函数光是滚动鼠标就浪费时间。2.1 按算法体系给模板分类数据结构/图论/DP/字符串/数论/几何我一般把模板组织成这样的目录template2/ ├── 00_fast_io/ ├── 01_basic_algo/ │ ├── binary_search.cpp │ ├── ternary_search.cpp │ └── merge_sort.cpp ├── 02_data_structure/ │ ├── union_find.cpp │ ├── fenwick_tree.cpp │ └── segment_tree.cpp ├── 03_graph/ │ ├── dijkstra_heap.cpp │ ├── floyd.cpp │ ├── kruskal.cpp │ └── bellman_ford.cpp ├── 04_dp/ │ ├── knapsack.cpp │ ├── lis.cpp │ └── lcs.cpp ├── 05_string/ │ ├── kmp.cpp │ ├── trie.cpp │ └── rolling_hash.cpp ├── 06_math/ │ ├── pow_mod.cpp │ ├── gcd_extend.cpp │ └── sieve_prime.cpp └── 07_geometry/ └── convex_hull.cpp这种分类最大的价值是“先归大类再找小类”。比赛时读完题先判断它是数据结构题还是图论题再进对应目录找具体算法比翻一本几百页的纸质资料要快得多。另外算法之间有依赖关系比如Kruskal要用并查集、扩欧经常和快速幂组合我习惯在文件头注释里标注依赖避免比赛时复制了主模板却漏掉配套函数。每个模板文件头我会写成统一格式这部分可以直接照抄/** * 文件名: dijkstra_heap.cpp * 适用: 非负权图单源最短路 * 复杂度: O((n m) log n) * 依赖: 无 * 注意: n、m 上限较大时请关闭同步IO改用快读 */注释里最该写的是“注意”那一行记录自己上次用这个模板翻车的原因。比如Dijkstra里数组距离要用long long、多组数据要清空vis这些坑写在注释里比赛时一眼就能看见。2.2 模板文件统一骨架与调试开关每个文件开头的固定写法一个模板文件开头我会固定写这样一段可以复制到所有文件里#include bits/stdc.h using namespace std; #define int long long // 数据范围可能超过1e9时打开 #define endl \n // 换行不要用endl避免强制刷行 const int INF 0x3f3f3f3f; #ifdef LOCAL #define dbg(x) cerr #x x \n #else #define dbg(x) #endif signed main() { ios::sync_with_stdio(false); cin.tie(0); // 具体题目逻辑 return 0; }这里的#define int long long是竞赛圈常用写法最大缺点是main函数会被替换成long long main()所以主函数必须写成signed main()否则部分编译器会警告。这个宏能避免大部分int溢出问题代价是常数略大但如果评测机时间余量充足建议直接开。dbg这个宏只在本地编译时输出调试信息评测系统只检查标准输出所以提交前不用删代码这是最方便的地方。如果你的评测环境不支持bits/stdc.h就把它替换成具体头文件比如cstdio、vector、queue、algorithm。提交之前注意这个环境差异很多学校的在线评测系统支持但少数企业笔试平台不支持提前踩过坑的人都知道头文件报错是最冤的翻车原因。2.3 什么必须背什么可以留到现场推背诵范围的取舍依据模板集再全也不可能全部背下来。我的取舍标准是两条代码长而且容易写错的必须背代码短、现场推也就十几秒的不值得占脑子。下面这张表是我常用的优先级算法处理方式原因二分/三分必背边界条件极易写错现场调容易死循环并查集必背代码短但容易忘初始化和路径压缩KMP必背现场推导next数组非常费时间Dijkstra堆优化必背细节多堆和vis配合容易写乱Floyd现场写三层循环很短只有60行快速幂/扩欧必背组合数学题里出现频率极高背包一维滚动必背顺序和逆序决定正确性不能现场试后缀数组/平衡树查模板常规比赛极少裸考遇到再翻一个容易被忽略的观点模板不是越全越好。几百个文件的模板库只会增加选择成本真正高频使用的算法通常不超过二十个。我把模板分成两档第一档是晚饭后能默写出来的第二档是知道放在哪个目录下、用的时候去复制。比赛时90%的题用第一档就能覆盖。3. 高频模板怎么写才靠谱快读、并查集、最短路与DP的落地写法这一章给出四个我认为使用率最高的可抄写法。这些写法考虑了赛场上常见的坑是我反复调整后留下的稳定版本不是从书里原样摘抄的。每个代码后面会补上逻辑说明和参数调整建议。3.1 快读快写模板大输入时的第一道防线输入规模到百万级别时快读能明显拉开差距。我用的是基于getchar的整型快读#include bits/stdc.h using namespace std; inline int readInt() { int x 0, f 1; char c getchar(); while (c 0 || c 9) // 跳过非数字字符 { if (c -) f -1; // 记录负数符号 c getchar(); } while (c 0 c 9) { x (x 3) (x 1) (c - 0); // 等价于 x x * 10 数字 c getchar(); } return x * f; } inline void writeInt(int x) { if (x 0) { putchar(-); x -x; } if (x 10) writeInt(x / 10); putchar(x % 10 0); }逻辑上第一个while吃掉数字前的空白、换行和正负号第二个while逐位累加。x的计算用移位代替乘法是老写法但现代编译器会把乘以10优化成等价指令所以写x * 10也完全没问题看个人习惯。参数上需要注意这个版本没有处理读取到EOF的情况如果题目存在“读一个数判断是否结束”的写法建议升级成返回bool的版本通过引用参数带回读到的值防止把EOF误判为0。混用cin和快读会出大问题。很多人关掉sync_with_stdio后又用快读结果输入顺序错乱表现为数据完全对不上。原则只有一条要么全局用iostream要么全局用快读不要在一个程序里混两套输入函数。3.2 并查集模板路径压缩加按秩合并的稳定写法并查集是图论题的底座Kruskal、连通块计数、离线查询都靠它。稳定写法如下struct DSU { vectorint fa, sz; void init(int n) { fa.resize(n 1); // 多开一个位置方便点编号从1开始 sz.assign(n 1, 1); // 每个集合初始大小都是1 iota(fa.begin(), fa.end(), 0); // 初始化每个点的父节点是自己 } int find(int x) { if (fa[x] x) return x; return fa[x] find(fa[x]); // 路径压缩直接把父节点指向根 } void unite(int x, int y) { x find(x); y find(y); if (x y) return; // 已经在同一集合 if (sz[x] sz[y]) // 按秩合并小树接在大树上 swap(x, y); fa[y] x; sz[x] sz[y]; } bool same(int x, int y) { return find(x) find(y); } };路径压缩保证了find几乎O(1)按秩合并保证即使路径压缩失效树高也不会超过log n。sz数组记录集合大小在很多统计连通块大小的题目里可以直接用顺手省掉一个额外数组。初始化用iota填0到nfa[0]也会指向自己如果题目点编号从1开始多出来的0号位不影响逻辑但递归find时要小心别把0号点并进去。find写成递归在极端链状情况下可能栈溢出。路径压缩后递归深度一般都很小但如果某道题先反复unite形成一条链再做深度find还是可能爆栈。真遇到这种数据可以把find改成迭代版或者提前调用一次统一的find来快速压平。我一般先写递归版被卡一次再换。3.3 堆优化Dijkstra模板邻接表与优先队列的配合单源非负权最短路是图论题里出现频率最高的类型。我的模板用vector存邻接表优先队列做小顶堆const int MAXN 200000 5; using ll long long; struct Edge { int v, w; }; vectorEdge g[MAXN]; ll dis[MAXN]; bool vis[MAXN]; void dijkstra(int s) { priority_queuepairll, int, vectorpairll, int, greaterpairll, int q; memset(dis, 0x3f, sizeof(dis)); dis[s] 0; q.push({0, s}); while (!q.empty()) { auto [d, u] q.top(); q.pop(); if (vis[u]) continue; // 跳过过时的堆顶 vis[u] true; // 标记已确定最短路 for (auto e : g[u]) { if (dis[e.v] dis[u] e.w) { dis[e.v] dis[u] e.w; q.push({dis[e.v], e.v}); } } } }pair默认比较先比first再比second所以把距离放在第一位每次弹出的就是当前未确定距离中最小的点。vis数组的continue写法比“删除堆中旧项”更简单代价是堆里可能有重复点但重复点总数不超过松弛次数复杂度仍在O((n m) log n)级别。0x3f3f3f3f这个INF值很讲究它比1e9略大且用memset按字节填充时每个字节都是0x3f所以可以直接对long long数组用memset结果接近1e18量级还能防住dis[u] w溢出。参数上最需要注意的是两点一是边权可能为负时绝对不能用Dijkstra要换SPFA或Bellman-Ford二是稠密图且点数不超过400时Floyd的O(n^3)反而比堆优化Dijkstra更好写、常数更小。MAXN的值按题目的点数上限调整不要无脑开1e6数组开太大会拖慢全局构造时间多组数据时尤其明显。3.4 背包与LIS模板滚动数组和二分优化的两个典型动态规划模板里最常抄的是背包和最长上升子序列。01背包和完全背包在一维滚动数组下只差一个循环方向int dp[MAXV]; void zeroOnePack(int v, int w, int cap) { for (int j cap; j v; --j) // 倒序保证每个物品只选一次 dp[j] max(dp[j], dp[j - v] w); } void completePack(int v, int w, int cap) { for (int j v; j cap; j) // 正序允许重复选择 dp[j] max(dp[j], dp[j - v] w); }参数v是体积、w是价值、cap是背包容量这三个名字我固定不变比赛时盯着参数改数值比现场理解含义更快。倒序和正序的本质区别倒序时dp[j - v]还没有被本次物品更新过所以不会出现“同一个物品被连续放入多次”正序则相反。记忆办法是“01倒序、完全正序”背的时候顺带想一遍原因考场才不会慌。LIS的二分优化写法更短但有一个大坑vectorint lis; for (int x : a) { auto it lower_bound(lis.begin(), lis.end(), x); if (it lis.end()) lis.push_back(x); // x比当前所有数都大直接扩展 else *it x; // 替换掉第一个不小于x的数 } // lis.size() 就是最长严格递增子序列长度这个写法只能得到长度不能得到真正的子序列。如果题目要求输出序列需要在替换位置记录前驱或者老老实实写O(n^2)的dp回溯版。模板注释里我会专门标一行“需要序列时改用回溯版”防止比赛到一半才想起来自己抄错了版本。4. 抄模板翻车的五个血泪坑从TLE到WA的排查记录模板本身没错错的是抄的时候少了些条件。下面五条是我自己和周围同学赛场翻车的高频场景每条按现象、原因、解决的思路整理。4.1 现象本地跑得飞快评测机却TLE原因多半是memset清超大数组。比如dis数组在头文件里开了MAXN 1e6每次测试用例都执行memset(dis, 0x3f, sizeof(dis))多组数据叠加后清零本身就成了O(n)乘用例数直接拖到超时。另一个常见原因是vector g[MAXN]开得过大即使题目n只有1000数组本身仍有1e6个vector对象要构造析构。解决方法是精确控制清理范围用fill(dis 1, dis n 1, INF)代替memset整个数组vector开成局部vector g[MAXN]时按实际点数resize。对于“本轮是否访问过”这类标记可以用时间戳代替memsetint used[MAXN], stamp; void nextCase() { stamp; } bool isUsed(int x) { return used[x] stamp; } void markUsed(int x) { used[x] stamp; }stamp每次用例自增判断是否访问过就看used[x]是否等于当前stamp全程不用清数组。这个技巧在dis、vis、cnt三个数组都要清理时特别省事但要注意stamp是int用例数超过2亿才可能溢出竞赛场景基本不会。4.2 现象数组越界不报错输出却明显离谱有些题目数据范围是n 1头文件里写了MAXN n 1结果邻接表从1号点开始存恰好越界写到了下一个数组的首位。本地小数据恰好没触发评测机的随机数据一碰就炸表现是输出完全不对但能跑完。解决的关键是数组上限永远比题目极限多开几个MAXN 200000 5而不是200001。多出的4到8个元素能吸收大部分越界问题。更大范围的问题可以用本地编译器开AddressSanitizer定位命令是g -fsanitizeaddress -g x.cpp -o x跑一遍随机数据就能看到越界发生的行号。另一个相关问题是递归深度过大导致栈溢出表现为RE而不是WA链状图上跑DFS尤其容易触发这类题建议提前改成非递归或使用显式栈。4.3 现象二分死在while循环里调了一整晚二分是玄学重灾区。最常见的死循环写法是while (l r) 配 if (check(mid)) l mid;当l和r相差1时mid (l r) 1会取到lcheck成立后l mid区间长度不再缩小循环永远出不来。稳定的做法是固定两套模板。找满足条件的最左值mid (l r) 1成立时r mid不成立时l mid 1。找满足条件的最右值mid (l r 1) 1成立时l mid不成立时r mid - 1。记忆要点是“右边界收缩时mid要向上取整”。如果数据范围到1e18l r可能溢出写成mid l (r - l 1) / 2更稳。4.4 现象加了快读反而更慢甚至读错数据快读不是万能的。输出数据量小的时候putchar逐字符写可能比printf慢输入本身只有几百个数时快读省下的时间几乎为零却多了一堆代码。更严重的是混用输入输出函数cin和getchar混在一起会读到意料之外的缓冲内容表现是“第一个数对了第二个数开始全错”。我的习惯是数据规模超过1e6才上快读否则正常用scanf或关同步后的cin。如果用了快读输出也尽量用writeInt不要一半快读一半printf。还有Windows环境下数据文件的行尾是\r\ngetchar会读到一个\r字符不过它在第一个while的跳过逻辑里会被吞掉一般不会造成问题真正需要注意的是读EOF时返回0导致负数判断错误处理方式就是前面说的引用参数版快读。4.5 现象模板背得很熟考场上不知道该用哪个原因不是代码没背熟而是只记了代码没记适用边界。看到负权图还在跑Dijkstra看到n500的稠密图却写堆优化Dijkstra而不是Floyd看到最小生成树的题误以为是单源最短路这些都是不读适用边界造成的。解决方法是比赛前把每个模板头部的“适用/不适用”重新过一遍而不是只背代码。我在模板文件里会用加粗注释写一条“如果边权有负数立即换SPFA不要犹豫”这种条件反射比任何代码都值钱。比赛时拿到题先花三十秒标注“图论/DP/数据结构”再进对应目录翻模板能避免大量方向性错误。5. 把模板变成赛场的即时武器调用时机、改题思路与训练节奏模板不是死背的东西而是赛场的“第一版草稿”。熟练选手的流程是题目读完先想算法再翻对应模板按题目改三到四个位置跑一遍样例和随机数据最后提交。这一章讲怎么把流程走顺。5.1 先判断题型归属一道题进来先翻哪一类模板判断题型不需要读完整题读题时抓三个关键词数据结构、操作类型、数据范围。比如“给一个n个点m条边的无向图求1到n最短路径边权非负n和m都是2e5”数据范围直接排除Floyd非负权排除SPFA一眼翻图论分类下的Dijkstra模板。再比如“给一个数组q次询问区间最大值带单点修改n和q都是1e5”这是典型的数据结构题操作是单点改和区间查树状数组或线段树二选一。这里有个常见误判“区间最大值”听起来像单调栈或RMQ但带修改就必须上线段树或树状数组翻错模板会越改越乱。还有一种题型靠伪装题目背景是图核心却是排序加并查集。比如“若干个点给定边的代价求使所有点连通的最小总代价”眼睛看到图字就去找最短路模板实际该翻的是最小生成树分类下的Kruskal。判断方法很简单题目求的是“访问路径”还是“连接代价”前者最短路后者生成树。5.2 复制不要照抄从模板到题解要检查的四个位置模板是通用版本题目一定会加自己的限制条件。我把复制后要检查的点固定成四个每次改完按顺序过一遍下标从0还是从1。我的Dijkstra模板默认点编号从1开始如果题目从0开始所有循环边界和初始化都要平移最容易漏的是for (int i 1; i n; i)改成从0开始。多组输入是否清空状态。模板里的dis和vis只在单组数据下有效套到多组数据循环里必须把初始化放到每组数据的开头而不是主函数入口。模数是否一致。很多DP模板自带MOD 1e97题目可能要求998244353或1000000009复制时只改了变量名没改MOD值会一路错到答案全错。int和long long。题目答案上界超过int时模板里涉及加法、乘法结果的变量都要改long long。开了#define int long long的写法要把main改成signed main这个细节我每次写代码前都会提醒自己。改完之后不要直接交先跑一遍题目样例再对拍一组小数据。样例过了只是起点随机对拍能抓住大部分边界问题。5.3 让模板库跟着你长每次比赛后合并三处以上的改动模板不是一劳永逸的。每次比赛或训练结束我都会把赛中实际用过的模板版本更新回自己的模板库这才是《ACM基础算法模板2》这类整理真正的用法它给你一个起点你用实战数据把它变成自己的东西。比如某场题要求在Dijkstra里额外输出路径赛后我会在dijkstra_heap.cpp里补一个pre数组记录前驱并在注释里写明“需要输出路径时用这个版本”。又比如有一次并查集题要求支持删除操作我研究了半天发现纯并查集不能删只能借用离线逆向处理技巧这个结论也写进模板注释里避免下次重复踩坑。更新的频率不用太高每周一次就够。注意每个模板文件保持短小控制在80到120行超过这个体量就说明这个模板需要拆分成两个变体。模板库的价值在于“每个文件都是我亲手跑过的”而不是“文件越多越好”。6. 验证模板能不能用的三板斧对拍、极限数据与性能基准模板写好不等于能过题赛前验证是必须的。我最喜欢的三板斧是对拍、极限数据和性能基准依次解决“答案对不对”“空间够不够”“时间快不快”三个问题。6.1 随机对拍让暴力程序当裁判对拍的前提是有一个绝对正确但复杂度高的暴力程序。用脚本循环生成随机数据分别跑暴力和模板比较输出#!/bin/bash for i in $(seq 1 1000); do python3 gen.py in.txt ./bf in.txt bf.out ./ac in.txt ac.out if ! diff -q bf.out ac.out /dev/null; then echo 在测试 $i 处发现不一致 break fi donegen.py里的随机生成器要覆盖边界n取1、取最大值、取中间值权值包含0、负数如果题意允许和大数。对拍的作用不只是检验模板本身更重要的是检验你把模板改成题解之后是否正确每次改完模板都要重新对拍一次不能只对拍原始模板。6.2 极限数据测试检验时间与空间的上限对拍保证正确性极限数据保证能过。做法是按照题目的最大约束生成数据用time命令测运行时间time ./ac big.txt /dev/null看两个指标耗时是否小于时限的一半越界和栈溢出是否出现。递归型模板在极限数据下最危险链状DFS几千层就能让程序崩掉这类问题提前发现比在赛场上发现好得多。6.3 性能基准与赛后复盘把模板的底色摸清楚最后一个习惯是给模板做基准测试。同一份数据跑三遍取平均对比快读版和scanf版、递归find和迭代find的差距知道每个模板的真实上限比赛时才好判断“这题用这个模板会不会卡常”。用chrono计时代码片段很短auto start chrono::steady_clock::now(); dijkstra(1); auto end chrono::steady_clock::now(); double ms chrono::durationdouble, milli(end - start).count();我自己的习惯是每次比赛结束后复盘哪一题因为模板改错挂掉就在对应模板文件头部加一条警告注释比如“Dijkstra模板里dis数组记得开long long”。这些标注全是实际翻车换来的经验。希望这份模板的使用思路也能帮你少踩一些我踩过的坑。本文还有配套的精品资源点击获取