简介：面向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会把变量名转成字符串，你一眼就能看到是哪个变量出了问题。

我习惯在做模板文件头部写清楚每题必带的编译期约定：

- C++17 - -O2 / -std=c++17 - 关闭栈限制：使用迭代或显式栈避免递归过大

本地我一般用-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 开始。如果外面传入下标 0，lowbit(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 { vector<int> 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) 要快得多，而且代码极短：

vector<int> leftSmaller(const vector<int>& a) { int n = (int)a.size(); vector<int> res(n, -1); stack<int> 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)：

vector<int> maxSlidingWindow(const vector<int>& a, int k) { int n = (int)a.size(); vector<int> res; deque<int> 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_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long 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, vector<Edge>& 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 拓扑排序：环检测与字典序变体

拓扑排序处理有向无环图的顺序关系，核心是 BFS：

vector<int> topologicalSort(int n, vector<vector<int>>& g) { vector<int> indeg(n + 1, 0); for (int u = 1; u <= n; u++) { for (int v : g[u]) indeg[v]++; } queue<int> q; for (int i = 1; i <= n; i++) { if (indeg[i] == 0) q.push(i); } vector<int> 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_queue<int, vector<int>, greater<int>>，其余逻辑不变。我见过不少人在这种题上硬写排序后处理，结果越改越乱，不如直接在模板上换个容器。

5. 避坑合集：模板里最值钱的其实是边界条件

5.1 多组数据下，root 节点初始化不彻底

现象：第一组样例 AC，第二组开始出现随机 WA，偶尔 RE。

原因：多组数据复用时，全局数组、vector 或 map 残留上一组数据的内容。最常见的是 head 数组没清零，或者并查集 fa 数组没有恢复初始状态。这是因为你在模板注释里写了“每组数据初始化”，却没有把所有容器纳入初始化范围。

解决：在每组数据输入后统一调用 reset：

memset(head, 0, sizeof(head)); tot = 0; dsu.init(n);

注意 vector 不能直接memset，需要vector<int> tmp(n + 1);再赋值，或者assign方法。写模板时把需要重置的容器集中在一个函数里，避免漏项。

5.2 INF 设得不够大，导致 WA 而不是 RE

现象：最短路代码在单源距离很大的题目里输出错误答案，但程序不崩溃。

原因：0x3f3f3f3f约等于 1e9，如果图的最长路径超过 1e9，d[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,--stack=268435456这类参数扩栈，但这属于环境相关的做法，比赛服务器不一定支持，不如直接写迭代。

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。从那以后，我拿到新板子第一件事就是放进对拍框架里，用一百组随机数据验证过再收入库。不同题的边界组合往往坑点各异，跑完对拍，心里才有底。希望帮到你。

本文还有配套的精品资源，点击获取