简介面向ACM竞赛与算法学习者的基础算法模板合辑涵盖快速读入、高精度四则运算加/减/乘低精度/除低精度、快速幂、组合数与排列数模运算、质数判定、分解质因数、欧拉筛等十余个高频考点。每个模板均提供可直接套用的C函数实现并附关键逻辑注释如高精度加减法的进位与借位处理、乘除低精度时的逐位运算、组合数通过阶乘与逆元快速计算、欧拉筛利用最小质因子实现线性筛选等方便理解原理并迁移到题目中。资源收录为一份PDF文档压缩包仅513KB体积轻量但知识点密集既可用于赛前快速回顾也可作为刷题时的查询手册。截至目前已有224人学习下载内容难度适中适合具备C基础、正在备赛ACM/蓝桥杯等算法竞赛的入门至中级选手据此逐步搭建个人算法模板库。1. 从“背模板”到“懂模板”中间隔了不止一次 WA某天拿到一份编译不过的板子排查到最后是递归爆栈导致的运行时错误。那时候才意识到算法模板不是背下来就完事环境差异、数据范围、输入方式全都会让同一份代码在不同赛场上表现完全不一样。这份《ACM基础算法模板2》不是零基础入门讲义更像一份把常用算法按“可抄、可改、可排错”三个标准重新整理的代码库——适合已经会写题、但想建立自己板子库的选手也适合老手对照查漏。它能帮你缩短“想到思路”到“跑出结果”之间的时间更重要的是让你知道每个模板的边界在哪、什么时候该换一种写法。2. 模板的底座快读、编译选项与代码习惯2.1 快读模板为什么 cin 优化后仍可能不够用竞赛题的数据量一旦到 1e6 级别输入就成了第一个性能瓶颈。常见做法是关闭 C 输入输出同步代码写起来很简单#include iostream using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 正常使用 cin / cout }这段代码的作用是取消 C 标准 IO 与 C 流之间的同步缓冲避免每次读写做两次缓冲检查。tie(nullptr)则断开 cin 与 cout 的绑定防止每次输出前强制刷新输入流。多数情况下优化后 cin 已经能跑过 1e6 级别数据。但有几类场景仍然建议直接上自定义快读数据量在 1e7 以上时或者题目输入格式比较怪比如读入若干组以数字结尾但不确定长度的数据又或者评测机环境本身对 IO 开销敏感。给你一个我常放在模板里的整数快读#include cstdio template typename T inline T read() { T x 0, f 1; int c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * f; }核心思路是逐字符解析整数跳过空白字符和符号位。模板参数 T 让它支持 int、long long 等不同类型。while循环跳过非数字字符时千万注意它也会跳过正负号之外的其他字符所以文件里出现分隔符也能正常工作。要注意这个版本依赖getchar的返回值正常读到文件尾返回 EOF配合 fread 批量读还能再快一截但会牺牲一些可读性。2.2 本地调试与线上评测的开关隔离模板里常出现一个容易被忽略的问题输出在代码里到处都是交上去忘删产生大量多余输出WA 得莫名其妙。更稳妥的做法不是“写完删”而是用条件编译把调试输出默认关闭#ifdef LOCAL #define dbg(x) cerr #x x \n #else #define dbg(x) #endif本地编译时加上-DLOCAL选项dbg输出到标准错误流。提交时没有定义 LOCAL所有调试输出自动消失。这个方法比“我注释掉了”靠谱得多——多组数据调试时dbg里的#x会把变量名转成字符串你一眼就能看到是哪个变量出了问题。我习惯在做模板文件头部写清楚每题必带的编译期约定- C17 - -O2 / -stdc17 - 关闭栈限制使用迭代或显式栈避免递归过大本地我一般用-Wall -Wextra把警告全开。模板题最容易翻车的不是逻辑而是忘记初始化变量。全开警告后未初始化变量和 signed/unsigned 比较都会先暴露出来。2.3 命名、注释与参数默认值让板子真正属于你模板最怕只有代码没有说明。比赛里时间紧你不可能在每道题重新读一遍模板实现。我的习惯是每个模板文件顶部写清三件事适用数据范围、时间复杂度和一个典型题目场景。举例来说/** * 树状数组单点修改 区间查询 * n 1e5 时效果明显n 1e6 时需注意常数 * 下标从 1 开始禁止传 0 */很多选手的板子是从别人那里复制的变量名和注释都是原作者的思路。复制进来没问题但一定要亲手跑一遍样例、改一遍参数再写进自己的模板库。这种做法不是浪费时间——比赛时你调用的是“自己验证过的代码”而不是“别人说能跑的代码”。3. 高频数据结构树状数组、并查集与单调栈/队列3.1 树状数组单点修改、区间查询的常数级数据结构树状数组适合 n 在 1e5 到 1e6 之间、操作次数同样在 1e6 级别的问题。它比线段树短很多常数也小代码量不到线段树一半。先看最基础的单点修改 区间查询int n; // 数据范围 long long bit[100005]; // 下标从 1 开始 inline int lowbit(int x) { return x (-x); } void add(int pos, long long val) { for (int i pos; i n; i lowbit(i)) { bit[i] val; } } long long prefixSum(int pos) { long long res 0; for (int i pos; i 0; i - lowbit(i)) { res bit[i]; } return res; } long long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); }lowbit是树状数组的核心操作x (-x)取到 x 二进制中最低位的 1。修改时从 pos 向上跳查询时从 pos 向下退每个操作都是 O(log n)。add的参数val用 long long 是为了防止前缀和相加时溢出。如果你是 1e5 级别的数据int 通常够用但统一用 long long 能减少思考成本。这里必须强调一个约定下标从 1 开始。如果外面传入下标 0lowbit(0)恒为 0修改和查询都会死循环。我从第一次用树状数组到现在因为这个细节卡住的次数不少于三次。3.2 树状数组进阶区间修改 区间查询的双 BIT 写法区间修改、区间查询如果把线段树搬出来代码量直接翻倍。用两个树状数组实现“区间加 区间求和”是很多进阶选手的通用做法。原理基于差分设差分数组 d[i] a[i] - a[i-1]那么区间加只需要修改四个点区间和则需要同时维护 d[i] 前缀和和 i*d[i] 前缀和。struct BITRange { int n; long long bit1[100005], bit2[100005]; void init(int _n) { n _n; memset(bit1, 0, sizeof(bit1)); memset(bit2, 0, sizeof(bit2)); } void add(long long bit[], int pos, long long val) { for (int i pos; i n; i lowbit(i)) { bit[i] val; } } long long sum(long long bit[], int pos) { long long res 0; for (int i pos; i 0; i - lowbit(i)) { res bit[i]; } return res; } void rangeAdd(int l, int r, long long val) { add(bit1, l, val); add(bit1, r 1, -val); add(bit2, l, val * (l - 1)); add(bit2, r 1, -val * r); } long long prefixSum(int pos) { return sum(bit1, pos) * pos - sum(bit2, pos); } long long rangeSum(int l, int r) { return prefixSum(r) - prefixSum(l - 1); } };这段代码里rangeAdd对 r 1 位置加负值是为了消除区间外的差分影响。位运算取 lowbit 时注意递归边界任何pos为 0 的调用都属于非法输入。对于多数区间操作问题这套模板能直接替代线段树的简单用法但在需要区间最大/最小值或区间最值赋值时树状数组并不适用需要线段树状态压缩甚至这门课里后续的高级数据结构。3.3 并查集路径压缩与按秩合并的取舍并查集是图论题和连通性题的基础工具。最常见的写法是递归路径压缩加按秩合并struct DSU { vectorint fa, sz; DSU(int n) { fa.resize(n 1); sz.assign(n 1, 1); for (int i 1; i n; i) fa[i] i; } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } bool same(int a, int b) { return find(a) find(b); } void unite(int a, int b) { int r1 find(a), r2 find(b); if (r1 r2) return; if (sz[r1] sz[r2]) swap(r1, r2); fa[r2] r1; sz[r1] sz[r2]; } };路径压缩把查询路径上的节点直接接到根上按秩合并把较小的树接到较大的树下两者配合使每次操作接近常数级。这个版本的unite里同时做了路径压缩和秩合并可以保证生成的树高度控制在 O(log n) 以内即使没有路径压缩也能保证效率。但递归find在链特别长时可能爆栈。如果你处理 1e6 级别的节点并且题目故意构造深度很大的树就换成迭代式路径压缩int find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; // 隔代压缩 x fa[x]; } return x; }这个版本不递归利用“祖父接点”的方式压缩路径。实际测试中竞争类题目里递归版本通常能过但如果你本地调试时发现 RE第一反应就应该是把递归改成迭代。3.4 单调栈寻找左右第一个更小值单调栈解决的是“每个位置左侧第一个比它小/大的值”复杂度 O(n)。比线段树在这种特定问题上的 O(n log n) 要快得多而且代码极短vectorint leftSmaller(const vectorint a) { int n (int)a.size(); vectorint res(n, -1); stackint st; for (int i 0; i n; i) { while (!st.empty() a[st.top()] a[i]) { st.pop(); } if (!st.empty()) res[i] st.top(); st.push(i); } return res; }逻辑是维护一个单调递增从栈底到栈顶的下标序列。当新元素比栈顶元素小时不断弹出直到找到比它小的元素。栈里存的是下标不是值避免索引回溯的麻烦。把改成得到的是严格小于关系改成反向比较就能求左侧第一个更大值。单调栈的问题形态很固定柱状图最大矩形、接雨水、每日温度。如果你判断出题意和“下一个更大/更小元素”相关直接套这个模式会比每次重写快很多。3.5 单调队列滑动窗口最值的常用解法滑动窗口最大值可以用 multiset 解决但常数大能卡着时间过但不够干净。单调队列是正解复杂度 O(n)vectorint maxSlidingWindow(const vectorint a, int k) { int n (int)a.size(); vectorint res; dequeint q; for (int i 0; i n; i) { // 弹出不在窗口内的队首 if (!q.empty() i - q.front() k) q.pop_front(); // 弹出队尾比当前元素小的值 while (!q.empty() a[q.back()] a[i]) q.pop_back(); q.push_back(i); // 窗口形成后记录答案 if (i k - 1) res.push_back(a[q.front()]); } return res; }队列中维护的是下标a[q.front()]是当前窗口最大值。为什么可以把队尾小于当前元素的值全部弹出因为后续窗口里这些旧元素永远不会比当前元素更优——它们的下标更靠前且值更小剥离后对答案不产生任何影响。这是一个典型的“时间维度和值维度双单调”的结构。注意q.pop_front()的判断条件用的是i - q.front() k而不是 k。窗口长度是 k当前元素下标为 i队首坐标要是小于等于 i - k 就出队。这个判断条件容易写错建议默写时多确认一遍。4. 图论常用模板存图、最短路、最小生成树与拓扑排序4.1 链式前向星为什么比赛存图用它更省心图论题的存图方式看似小事却直接影响写法和调试效率。vector 邻接表写起来最方便但遇到memset初始化、反复建图销毁场景时链式前向星更稳定、内存更连续struct Edge { int to, nxt; long long w; } e[200005]; int head[100005], tot 0; void addEdge(int u, int v, long long w) { e[tot] {v, head[u], w}; head[u] tot; }head[u]记录 u 的第一条边的编号nxt指向同一起点的下一条边。遍历时for (int i head[u]; i; i e[i].nxt) { int v e[i].to; // 处理边 e[i].w }这个写法比 vector 邻接表多一个“nxt 跳转”的概念但换来的是不用反复resize多组数据时memset(head, 0, sizeof(head))一次清空而且边数组本身是静态分配不会被 vector 内部扩容影响。输入规模在 2e5 边以下的题vector 和链式前向星差距不大超过这个规模我会优先选择链式前向星。4.2 Dijkstra 堆优化延迟删除与 INF 设计单源最短路的经典写法。用优先队列维护“当前已知最短距离”的候选节点每次扩展距离最小的点long long d[100005]; int n; void dijkstra(int s) { const long long INF 4e18; for (int i 1; i n; i) d[i] INF; d[s] 0; priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; pq.push({0, s}); while (!pq.empty()) { auto [dist, u] pq.top(); pq.pop(); if (dist ! d[u]) continue; // 延迟删除 for (int i head[u]; i; i e[i].nxt) { int v e[i].to; if (d[v] d[u] e[i].w) { d[v] d[u] e[i].w; pq.push({d[v], v}); } } } }重点在if (dist ! d[u]) continue;这一行。它替代了vis数组的工作如果该节点已经被更短的距离更新过那么队列里残留的旧记录直接跳过。使用vis数组的写法要额外加判断分支而延迟删除天然避免重复扩展代码量还更小。INF的取值在这里很关键。0x3f3f3f3f约等于 1.06e9适合 int 范围内路径和不超过这个值的题目。如果边权可以达到 1e9路径长度轻松超过 1e9这时候继续用INF 0x3f3f3f3f会导致距离值“合理”地小于 INF结果却已经不是最终答案最后变成 WA 而不是溢出崩溃。用 long long 存 d 时把 INF 设成4e18配合d[u] INF判断再去执行松弛操作可以避免d[u] e[i].w溢出 long long。4.3 Kruskal 最小生成树排序后并查集合并Kruskal 的思路是把边按权值排序从小到大判断两端是否连通不连通就加入生成树。模板代码几乎不需要额外封装long long kruskal(int n, vectorEdge edges) { sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { return a.w b.w; }); DSU dsu(n 1); long long total 0; int cnt 0; for (auto e : edges) { if (!dsu.same(e.u, e.v)) { dsu.unite(e.u, e.v); total e.w; cnt; if (cnt n - 1) break; } } if (cnt ! n - 1) { // 图不连通不存在生成树 } return total; }Edge 这里的三元组结构要自己定义。排序按边权升序cnt统计已选边数。如果最终 cnt 不等于 n - 1说明原图不连通这是好代码必须具备的失败处理。时间复杂度主要来自排序 O(m log m)并查集部分接近线性。对稠密图用 Prim 可能会更快但 Kruskal 的实现代价更低也更不容易写错这是我个人更常用它的原因。4.4 拓扑排序环检测与字典序变体拓扑排序处理有向无环图的顺序关系核心是 BFSvectorint topologicalSort(int n, vectorvectorint g) { vectorint indeg(n 1, 0); for (int u 1; u n; u) { for (int v : g[u]) indeg[v]; } queueint q; for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } vectorint res; while (!q.empty()) { int u q.front(); q.pop(); res.push_back(u); for (int v : g[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } if ((int)res.size() ! n) { // 有环无合法拓扑序 } return res; }入度为 0 说明“没有前置约束”可以安全输出。每处理一个节点它指向的节点入度减一减到 0 时进入队列。最终如果 res 长度不等于 n必然存在环。这个判断在很多题目里就是核心逻辑比如判断某个课程安排是否可行。一个变体是“要求输出字典序最小的拓扑序”此时把队列改为小顶堆或 priority_queue。原题是“任意拓扑序”时用普通队列即可加上字典序要求后只需要把 queue 换成priority_queueint, vectorint, greaterint其余逻辑不变。我见过不少人在这种题上硬写排序后处理结果越改越乱不如直接在模板上换个容器。5. 避坑合集模板里最值钱的其实是边界条件5.1 多组数据下root 节点初始化不彻底现象第一组样例 AC第二组开始出现随机 WA偶尔 RE。原因多组数据复用时全局数组、vector 或 map 残留上一组数据的内容。最常见的是 head 数组没清零或者并查集 fa 数组没有恢复初始状态。这是因为你在模板注释里写了“每组数据初始化”却没有把所有容器纳入初始化范围。解决在每组数据输入后统一调用 resetmemset(head, 0, sizeof(head)); tot 0; dsu.init(n);注意 vector 不能直接memset需要vectorint tmp(n 1);再赋值或者assign方法。写模板时把需要重置的容器集中在一个函数里避免漏项。5.2 INF 设得不够大导致 WA 而不是 RE现象最短路代码在单源距离很大的题目里输出错误答案但程序不崩溃。原因0x3f3f3f3f约等于 1e9如果图的最长路径超过 1e9d[v]可能在你有意无意的松弛中偏离真实值但因为类型没有溢出所以难以察觉。解决统一使用const long long INF 4e18并在松弛前判断d[u] ! INF。这样既不会溢出也避免无效松弛。5.3 树状数组传 0 下标死循环现象程序在add(0, val)或prefixSum(0)时卡死甚至本地调试时 stderr 能看到死循环。原因lowbit(0) 恒等于 0循环i lowbit(i)永远停在原地。解决封装时强制断言或者在调用前统一从输入的下标 1。比如原始数据下标从 0 开始就在读入时add(index 1, val)统一把底层下标偏移到 1 起点。5.4 递归并查集在极端链状数据下爆栈现象失败的点全是 RE不超时不开全栈也能复现。本地小数据没问题大数据直接挂。原因路径压缩递归深度在链状结构上可以达到 n栈空间不够。解决改用迭代查找函数这个函数在 3.3 节已经给出。如果你确实想保留递归版本就在编译选项里加-Wl,--stack268435456这类参数扩栈但这属于环境相关的做法比赛服务器不一定支持不如直接写迭代。5.5 拓扑排序判环条件写成cnt n现象有环图输出答案错误偶尔输出一个不存在的合法序列。原因判环标准是实际输出节点数是否等于 n但如果你用cnt在 while 循环里统计同时循环内可能遗漏最终仍有入度的节点判断逻辑就会出错。解决while 执行完后统一比较res.size()和n写准这一行的意义前者是实际消费的节点后者是图的总节点。6. 进阶用法用对拍脚本把模板信任成本降下来模板光靠样例验证远远不够。边界数据、随机数据、构造数据常常能暴露模板里的隐性错误。我现在每个新模板或者改动过的模板第一件事就是写对拍脚本。核心是三个文件一个正确但可能慢的标程一个使用你的模板实现的程序以及一个随机数据生成器。#!/bin/bash for i in $(seq 1 100); do python3 gen.py input.txt ./std input.txt stdout.txt ./my input.txt myout.txt if diff -q stdout.txt myout.txt /dev/null; then echo Case $i: OK else echo Case $i: FAILED break fi done随机数据生成器要覆盖题型边界不能只出弱数据。比如最短路题生成器里需要包含重边、自环、孤立点、不连通图和大权值边import random random.seed(2024) n random.randint(1, 10) # 小数据方便人眼检查 m random.randint(1, 20) print(n, m) for _ in range(m): u random.randint(1, n) v random.randint(1, n) w random.randint(-1e5, 1e5) # 负数边不要直接跑 Dijkstra print(u, v, w)对拍脚本找到反例后优先把input.txt缩小手动推演一遍流程。这是一种比较费时间但绝对值得做的事你可能用十分钟对拍换回比赛场上省掉的一次 WA。从那以后我拿到新板子第一件事就是放进对拍框架里用一百组随机数据验证过再收入库。不同题的边界组合往往坑点各异跑完对拍心里才有底。希望帮到你。本文还有配套的精品资源点击获取