简介《ACM基础算法模板2》是一份面向ACM/ICPC及算法竞赛选手的PDF速查手册聚焦基础算法的模板化实现与考场快速调用。内容涵盖快速读入、高精度四则运算、快速幂、组合数排列数模运算、质数判定、分解质因数、欧拉筛以及最大公约数、最小公倍数和整数二分模板可作为日常刷题与赛前复习的代码库。资源为单个PDF文件体积约513KB排版紧凑、示例代码清晰便于在电子设备或打印后直接查阅。当前已有225人浏览学习适合正在系统整理算法模板、希望提升编码效率的初中级竞赛参与者。文件中的高精度运算与数论模板均给出完整实现并附有复杂度说明与使用提示读者既可直接套用也能在此基础上按需改写便于比赛中快速迁移与扩展。1. 这份基础算法模板2是给比赛现场的“后悔药”存下的底牌做算法题最怕的不是不会是“会但写不完”。很多选手都有过这样的经历Dijkstra 板子抄到一半发现图的存储方式跟题目输入对不上最大流的板子调了二十分钟发现漏了弧优化的那两行线段树模板一粘贴发现数组开小了直接段错误。ACM基础算法模板这个方向要解决的就是这件事——把题解里反复出现的算法沉淀成一份能快速复制、敢直接信任的代码库。而“模板2”这个编号背后意味着它不是从零抄来的第一版而是你在真实赛场上翻过车之后删掉废代码、补上注释、改好参数的第二个版本。这份模板适合三类人正在备战比赛的队伍成员刷题求职需要高效复现算法的人以及做算法原型验证的开发者。它的价值不在于对算法原理的讲解有多深而在于你把板子背下来、拷过去之后能不假思索地跑出正确结果。接下来我按自己的维护习惯从分类骨架、写法规范、验证方式、常见翻车点到进阶用法把这份模板库的搭建过程完整讲一遍。2. 先搭好分类骨架一份基础算法模板库的目录与选型很多人第一次整理模板喜欢把几十个 cpp 文件堆在一个文件夹里文件名写模板1.cpp、模板2.cpp。等到比赛真要用查找的时间比手写还长这就失去了模板的意义。比赛现场的黄金时间是前 30 分钟你需要在一分钟内定位到目标板子再花几十秒完成复制和参数调整。所以目录结构必须按算法类别划分而不是按时间顺序堆叠。2.1 八类核心模板的范围与选型理由我一般会把模板库分成八个目录每个目录只放这一类里出现频率最高、最适合现场复用的板子。下面这张表是近年来比赛题解里出现频率较高的算法分类和选型理由你可以按自己的薄弱环节裁剪。目录核心内容选型理由基础数据结构并查集、单调栈/队列、树状数组、线段树、ST 表这类板子代码短但边界多临时写容易漏复制最快图论链式前向星、Dijkstra、Floyd、Kruskal、Tarjan、Dinic、费用流图论是出题重灾区板子稳定性直接决定能否 AC动态规划背包系列、LIS/LCS、区间 DP、树形 DP、状压 DP、数位 DPDP 的状态转移思路容易忘模板注释里要写清状态定义字符串KMP、Trie、AC 自动机、Manacher、字符串哈希字符串题现场推算法基本来不及必须靠板子数论快速幂、扩展欧几里得、素数筛、逆元、组合数取模、矩阵快速幂数论板子短小精悍重点是处理溢出和取模计算几何凸包、线段相交、点在多边形内、最近点对几何板子精度坑多能用整数判断就不要用浮点常用技巧二分答案、离散化、高精度、随机化这些代码逻辑简单但写起来啰嗦值得存进阶模块树链剖分、可持久化线段树、分块、莫队不常用但遇到难题时救命单独放一层方便找选型有一个原则宁可少不可杂。每个目录控制在 5 到 12 个文件超过 15 个就该做二次筛选。板子太多会导致你根本不记得里面有什么查板子的过程就变成了重新读代码的过程反而拖慢节奏。2.2 把目录搭成可快速定位的层级结构目录结构不是越多层越好我建议最多两层。顶层按类别分底层放具体板子每个板子用英文短文件名不要用日期或中文拼音命名。下面是一个我实际在用的结构示例template/ ├── README.md ├── graph/ │ ├── dijkstra.cpp │ ├── floyd.cpp │ ├── kruskal.cpp │ ├── spfa.cpp │ ├── dinic.cpp │ └── tarjan_scc.cpp ├── data_structure/ │ ├── union_find.cpp │ ├── fenwick.cpp │ ├── segtree.cpp │ └── mono_stack.cpp ├── dynamic_programming/ │ ├── knapsack.cpp │ ├── lis_ons.cpp │ ├── interval_dp.cpp │ ├── tree_dp.cpp │ └── digit_dp.cpp ├── string/ │ ├── kmp.cpp │ ├── trie.cpp │ ├── manacher.cpp │ └── string_hash.cpp ├── number_theory/ │ ├── quick_pow.cpp │ ├── exgcd.cpp │ ├── linear_sieve.cpp │ ├── mod_inverse.cpp │ └── matrix_pow.cpp ├── geometry/ │ ├── andrew_convex.cpp │ └── segment_intersect.cpp └── tricks/ ├── binary_search_answer.cpp └── discretize.cpp这个结构的好处是比赛时你只要判断这道题属于哪个大类直接进目录找文件名。比如看到“求割点”就猜到 tarjan 相关进 graph 目录找。每个文件头部都应该有一段注释写清楚复杂度、适用数据范围、以及默认使用的变量含义。我一般用这种格式// 功能堆优化 Dijkstra 单源最短路 // 复杂度O((N M) log N) // 适用N 1e5, M 2e5, 边权非负 // 注意无向图边数组开 2 倍INF 用 0x3f3f3f3f这段注释是板子最重要的部分比代码本身还关键。因为时间一久你会忘记当初为什么这么写注释能帮你三十秒内判断这个板子能不能用在当前题上。2.3 单品板与配套依赖区分“查一下”和“复制一整份”整理模板时有一个常见误区——把算法封装成类或者带上完整工程结构的写法。比如写个struct Graph内部私有成员、构造函数、析构函数一应俱全。这类写法的代码非常“美观”但比赛时复制麻烦改动参数也麻烦。ACM 现场的核心诉求是复制整个文件后能直接编译运行要尽量减少外部依赖。我会把板子分成两类单品板和一个含多个依赖的配套板。单品板就是一个文件搞定一切比如并查集、快速幂、Dijkstra。配套板则不同比如线段树需要定义pushup和pushdown这两个函数的具体逻辑因题而异你必须带着场景复制。对于配套板我会在文件注释里写明一般要一起复制的函数有哪些而不是把它当成黑匣子。比如 Dinic 最大流板子本身包含 BFS 分层和 DFS 增广但如果你用的题需要记录流量经过的路径就得额外加数组。我在存储板子时会单独开一个dinic_flow_path.cpp把需要改动的行用// CHANGE HERE标出来。这个习惯坚持下来你的板子库会越来越顺手。3. 模板的写法规范让板子不只在本地能跑有了目录结构下一步是解决板子本身的质量。很多人的第一版模板是从题解里东拼西凑来的能过那个题的样例但换一个题就段错误、答案错或者被卡常数。模板和普通提交代码最大的区别在于普通代码只需要解决当前这道题而模板要解决一整类题。所以模板的写法必须符合三个硬性要求。3.1 正确性优先于优雅第一版板子的三条硬性要求第一条要求是能通过该类算法对应的多种题型验证而不是只过一道题。比如存了 Dijkstra就要在稠密图、稀疏图、重边、自环、不连通图、大数值边权这六种场景下都跑出正确结果。这就要求模板里对重边的处理是稳定的而不是靠运气。第二条要求是复杂度要标注清楚并且实现方式与标注匹配。见过有人把 SPFA 写进模板注释写“适用于稀疏图期望 O(KM)”但实际遇到构造数据就会被卡到 O(NM)。SPFA 这类复杂度不稳定的算法更适合当成思想板子来复习不建议放进主模板列表。主模板宁可多存一份堆优化 Dijkstra也不要指望 SPFA 能稳定解决问题。第三条要求是必须单文件可编译。这听起来像是废话但真有很多板子带上了#include local_lib.h或者依赖了之前 AC 代码里的自定义快读函数。比赛时你复制板子不可能连带着把所有工程文件一起复制。所以板子里的所有函数、宏定义、结构体声明都必须在一个 cpp 文件内完整呈现。3.2 一个可抄作业的示例板链式前向星 最短路下面这份 Dijkstra 板子是我认为适合放进模板库的样式它同时满足单文件可编译、复杂度明确、处理重边稳定这几个要求#include bits/stdc.h using namespace std; using ll long long; const int N 100005; // 最大节点数 const int M 200005; // 最大边数无向图开 2 倍 const ll INF 0x3f3f3f3f3f3f3f3fLL; struct Edge { int to, nxt; ll w; } edge[M]; int head[N], tot; inline void add_edge(int u, int v, ll w) { edge[tot].to v; edge[tot].w w; edge[tot].nxt head[u]; head[u] tot; } void dijkstra(int s, int n, ll dist[]) { for (int i 1; i n; i) dist[i] INF; dist[s] 0; priority_queuepairll, int, vectorpairll, int, greaterpairll, int pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 跳过旧更新的节点替代 vis 标记 for (int i head[u]; i ! -1; i edge[i].nxt) { int v edge[i].to; ll nd d edge[i].w; if (nd dist[v]) { dist[v] nd; pq.push({nd, v}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, s; cin n m s; memset(head, -1, sizeof(head)); tot 0; for (int i 0; i m; i) { int u, v; ll w; cin u v w; add_edge(u, v, w); // 有向图 // add_edge(v, u, w); // 无向图再取消注释这行 } vectorll dist(n 1); dijkstra(s, n, dist.data()); for (int i 1; i n; i) { if (dist[i] INF / 2) cout -1 ; else cout dist[i] ; } return 0; }这份代码里我用了几个看起来“不高雅但实用”的设计。第一个是if (d ! dist[u]) continue;它用距离判断替代了vis数组。好处是重边和自环不需要额外特判加入优先队列的旧更新会被直接跳过逻辑上更干净。第二个是距离类型用ll因为比赛中常见边权加和超过 int 范围的题目用ll少操一份心。关于INF的取值我建议用0x3f3f3f3f3f3f3f3fLL而不是1e18。原因很简单0x3f3f在 memset 字节填充后能得到相同的值用memset(dist, 0x3f, sizeof(dist))可以直接初始化而1e18没法这样批量填充。如果你遇到最短路计数或方案数题目INF 还可以参与加法不溢出这个值依然安全。3.3 参数习惯与命名全局数组、短变量名与边界防御模板里的变量名不需要照顾可读性因为只有你自己看但必须照顾调试效率。我建议统一用N、M表示上限u、v表示边的两端s表示源点tot表示边数下标。这套命名一旦定下来所有图论板子都沿用查错的时候不用重新理解命名。数据集上限的声明要写大不写小。比如题面写N 1e5我一般声明const int N 100005留出 5 个单位的余量防止有时候边界条件里隐含了N1这种写法。数组开小了导致的段错误是所有模板问题里最难定位的一类因为它只有在极限数据下才出现本地小样例根本测不出来。另一个防御性习惯是所有递归函数入口处检查边界条件比如线段树update函数的l r判断无论当前题目用不用得到都保留着。综合来看模板写法的核心是“稳定、统一、够用就好”。不要把一个板子写成万能工具库不要试图把十种算法的变体揉进一个函数。每个模板文件解决一类问题的核心需求多余的部分全部删掉这是模板2相比第一版最重要的进化。4. 验证模板的性价比方案对拍与六类边界用例模板写完了接下来要解决的是“它真的对吗”。很多人的验证方式是拿一两道例题跑一下能过就放进库里。这是最大的隐患——例题往往只覆盖了正常路径根本没有触及实现里的边界逻辑。正确的做法是对拍加边界用例用最小的成本覆盖尽可能多的错误。4.1 对拍脚本的写法用脚本把暴力解与模板结果比对对拍是我最推荐的验证方式写一个数据生成器写一个暴力解法再让模板程序和暴力程序跑同样的数据对比输出。下面这段 Python 脚本是我用来对拍最短路模板的通用工具你们可以按自己的算法类型改数据生成策略import random import subprocess import sys def gen_data(): n random.randint(1, 8) m random.randint(0, n * (n - 1) // 2) lines [f{n} {m} {random.randint(1, n)}] edges set() for _ in range(m): u random.randint(1, n) v random.randint(1, n) while (u, v) in edges: # 避免生成完全相同的重边 u random.randint(1, n) v random.randint(1, n) edges.add((u, v)) w random.randint(1, 100) lines.append(f{u} {v} {w}) return \n.join(lines) for t in range(1000): data gen_data() with open(test.in, w) as f: f.write(data) try: r1 subprocess.run([./brute], stdinopen(test.in), stdoutsubprocess.PIPE, timeout2).stdout r2 subprocess.run([./template], stdinopen(test.in), stdoutsubprocess.PIPE, timeout2).stdout except subprocess.TimeoutExpired: print(fCase {t}: time out) print(data) break if r1.split() ! r2.split(): # 按空白分割比较忽略行尾差异 print(fCase {t}: mismatch) print(data) print(brute:, r1.decode()) print(template:, r2.decode()) sys.exit(1) print(all ok)这个脚本的逻辑不复杂gen_data生成小规模的随机数据小规模意味着暴力解法一定能跑完subprocess分别调起暴力程序和模板程序比对输出。如果 1000 组数据全部一致板子基本可以信任。参数方面有一个关键设计n限制在 8 以内。为什么这么小因为暴力程序复杂度可能是阶乘级或指数级数据大了跑不出来。对拍的目的不是测性能而是测逻辑正确性所以数据规模小、随机覆盖多就是最好的参数选择。权值范围设成1到100避免零权边和负权边干扰判断那样会让你分不清到底是算法问题还是数据设计问题。4.2 六类必测边界用例随机对拍能覆盖“常见的输入组合”但边界条件必须靠手动构造。以下六类用例是每个板子入库前必须跑一遍的用例类型构造方式能发现的问题单点图只有一个节点无自环距离初始化错误、数组越界自环u v的边最短路更新是否死循环重边同样的u v出现多次是否保留最小权值最大数据范围按注释中的上限生成数据数组大小、时间是否超限不连通图部分节点没有边相连是否输出正确的不可达标记路径长度溢出边权接近上限路径经过尽可能多的边int 是否溢出INF 是否合理这六类用例分别对应一种经典的模板实现错误。举个例子自环在 Dijkstra 模板里如果不用if (d ! dist[u]) continue而是用vis[u]标记已访问其实也不会死循环。但如果你用while (!pq.empty())且没有跳过旧更新的逻辑自环会让同一个节点反复入队复杂度退化。这一类问题在随机对拍里跑一万次都不一定出现因为随机图很少构造出自环叠加的场景。4.3 每场比赛前的模板自测清单板子验证不是一次性的而是每次比赛前都应该重复一遍。我一般会在赛前两天的晚上花半小时做一次全量回归测试。流程是这样的先重新编译所有板子确认没有因为编译器版本变化引入的语法错误再跑十组随机样例确认核心结果正确最后重点测试自己近期改动过的板子。这里有一个很实在的技巧修改板子之后只跑相关的那几个测试用例不要全量回归。因为全量回归一旦出现错误你很难判断是哪个改动引入的。我用 Git 管理板子每次改完板子先提交一次再做验证验证失败了可以二分查找历史版本快速定位是哪一次改动出了问题。这个习惯帮我解决过好几次“本地能跑、线上翻车”的玄学问题。5. 避坑这些板子让你的题解翻车的五个瞬间在整理和使用模板的道路上有太多坑等着新手去踩。下面这五个问题是参赛者和刷题者最容易遇到的每一条都带有“当时完全没意识到”的特点我按现象到原因到解决的方式记录下来。5.1 复制板子时漏掉依赖文件编译报错找不到函数现象赛场上从模板库复制最短路板子粘贴到代码框架里编译直接在head数组初始化这行报“未定义的引用”因为板子里用了memset(head, -1, sizeof(head))但结构体Edge没复制全或者是板子依赖了一个自定义快读函数而快读函数在另一个文件里。原因早期整理模板时把add_edge、Edge结构体、dijkstra函数拆到了多个文件中标榜“模块化设计”。比赛时一急只复制了核心函数忘掉配套定义。解决强制所有模板单文件可编译。如果某个板子真的需要配套结构就把所有依赖写在同一个 cpp 里并且在文件头部注释写明“完整复制三个部分”。我个人的习惯是每个模板文件在最后加一段main函数示例一方面验证了可编译性另一方面万一复制时漏了哪块编译错误会明确指向缺失的函数。5.2 通用板子上限不够题目 N 到 1e5 直接超时现象第一版模板里存了一份 Floyd 板子注释写“适合 N 500”。某天遇到一道多源最短路题数据范围 N 是 2000选手想都没想就套了这份板子跑了一分钟没出结果直接超时。原因没有养成“看注释再选板子”的习惯。模板注释里写清楚了适用范围但使用的人急着敲代码忽略了 N 的范围。解决每个板子第一行固定写复杂度和数据上限而且在图论类模板的函数名前统一加前缀// O(N^3), N 500。这行提示要足够显眼让人无法忽略。如果题目数据超过板子上限先停下来想是否有更优算法而不是硬套。5.3 读入优化与评测环境冲突本地正常线上输入错乱现象板子里用scanf(%d, x)读入但文件里同时保留了一个自己写的getchar()快读函数某些分支混用了两种读法。本地运行时样例能过交到评测系统上第一个点就 WA检查半天发现是输入顺序错乱。原因scanf和getchar混用会导致输入缓冲区指针错位尤其是程序里同时用cin时更混乱。本地测的样例往往数量少混读不会暴露问题评测数据一多缓冲区状态就失控了。解决统一使用一种输入方式。我的板子里要么全部用cin加ios::sync_with_stdio(false)要么全部用scanf绝不混用。自定义快读板子里也只用快读不跟scanf混在一起。如果你要从模板库里复制读入优化部分务必检查主程序里是否还有别的读入调用。5.4 板子能跑但结果溢出答案错在很隐蔽的大数上现象板子里最短路距离用int存INF定义为0x3f3f3f3f。题目里边权最大值是 1e9路径经过 2 万条边累加后超过 int 范围。本地小样例测不出来交上去 WA 之后打印中间变量才发现溢出。原因模板注释里写的“边权非负”没提数值上限选手直接用int距离代价是溢出。解决在图论、数论这一类需要累加的板子里距离变量统一用long long。虽然内存多一倍但彻底避免溢出问题。INF也改成0x3f3f3f3f3f3f3f3fLL这个值能保持“无穷大加无穷大仍不溢出为负数”的性质。如果板子用于 EXGCD 或组合数取模所有乘法操作前先取模避免溢出。5.5 拿通用板硬凑题反而绕远了路现象一道求“最多能完成多少任务”的题本质上是个贪心加排序但选手看到“最多”两个字直觉反应是套最大流板子。调了二十分钟参数最后发现答案对不上因为这道题的限制条件在流模型里无法完整表达。原因板子目录太全反而让使用者产生了“我什么都有”的错觉。看到一道题第一反应不是分析题型而是翻目录找相似模板。解决在模板README.md里加一个“解题思路速查”表按关键词把题型和对应模板列出来。明确提示“贪心题不要套流”。同时给每个板子加一栏“适用题型”模板文件里不仅写算法功能和复杂度还写“这道题什么时候不该用”。当板子库成为你的武器库时知道哪件武器不适合跟知道哪件武器好用一样重要。6. 把模板用活查表、改参、回归的实战习惯模板库建立之后真正拉开差距的是使用效率。同一个板子有人复制到改完参数要三分钟有人只需要三十秒。这中间的差别在于你针对每个模板都维护了一份“参数速查表”和“改动清单”。我习惯在每一个模板文件的注释下方建一张参数小抄。拿最短路举例速查表长这样题目特征用哪个板子必改参数单源非负权边N 1e5Dijkstra 堆优化N、M 数组大小单源可能存在负权边SPFA 或 Bellman-Ford不需要改但复杂度不可靠多源最短路N 500Floyd无注意 INF 判断方案数取模的最短路Dijkstra cnt 数组加cnt[v]更新逻辑有了这张表赛场上判断完题型到完成参数修改的时间会大大压缩。每次比赛结束把遇到的特殊边界加进对应板子的“改动清单”比如“这道题要求输出路径需要在松弛时记录前驱”。你的模板2 就会慢慢变成结合实战经验的模板3、模板4。在每次修改模板之后必须重跑对拍脚本。我吃过一次亏给线段树板子加了一个区间取模功能顺手改错了pushdown里的顺序本地样例通过但比赛时完全错误。后来我给自己立了规矩每次比赛前重新编译一次全量板子跑一段随机对拍只为确认两件事——板子能编译结果是正确的。这个习惯看起来笨拙但没有它你就无法确定当初整理板子时记录的注释还是否与代码事实相符。关于模板的长期维护还有一点想提醒不要怕删板子。有些板子你存了两年一次没用过这说明你的做题风格用不到它放在目录里只会增加查找成本。我每半年清理一次把没有实际用过的板子移到archive目录主目录里永远只留那些被验证过多次、注释覆盖全面的“主力选手”。真正放进主力目录的板子必须是你能闭上眼睛描述它的实现结构的那种。整理模板这件事入门时看起来是体力活坚持两年以后你会发现自己对算法细节的理解远超那些只刷题不整理的人。因为整理的过程逼着你思考“为什么这样写才对”。希望这份基于实践沉淀的模板维护思路能帮到你在赛场上少一点手忙脚乱多一点胸有成竹。本文还有配套的精品资源点击获取