企业官网建设流程全解析

简介：面向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 默认配置表：一进考场先敲这三行

我的模板库每个文件顶部都有一段固定配置，避免每道题都临时想类型和常量：

两个 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，否则 i=0 时 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; }; vector<Edge> g[MAXN]; long long dis[MAXN]; bool vis[MAXN]; // 从起点 s 跑单源最短路，结果存在 dis 里 void dijkstra(int s) { memset(dis, 0x3f, sizeof(dis)); dis[s] = 0; priority_queue<pair<long long, int>, vector<pair<long 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 标记不能在建堆时打，要在出队时打，否则同一个节点可能被多个松弛操作反复入队。模板有两个边界要记得：稠密图（比如 n=1000、m=50 万）直接用 O(n^2) 的朴素写法反而更快，堆优化的 log 常数在这种图上不划算；遇到负权边不能用 Dijkstra，要么 SPFA 要么 Bellman-Ford，把模板切换条件写进注释里，比赛时少踩很多坑。

4.2 字符串匹配模板：KMP 的 next 数组与字典树的静态写法

字符串匹配在基础模板里占两席：单模式串匹配用 KMP，多模式串前缀匹配用字典树。KMP 的难点是 next 数组的定义和回退逻辑：

// 构建 next 数组：nxt[i] 表示 p[0..i] 的最长相等前后缀长度 vector<int> build_next(const string &p) { int m = p.size(); vector<int> 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) { vector<int> 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(n+m)，模板本身没什么可调的，容易被坑的是 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)，当 i=0 时 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 在稠密图上反而更慢

现象：n=1000、m=50 万的图，堆优化 Dijkstra 跑了 O(n^2) 两倍以上的时间。原因：堆优化的瓶颈在堆操作上，每条边都有可能入堆出堆，m 达到几十万时，log 级别的堆操作常数被放大；而 n=1000 时 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，命令名写成兼容变量PY=python3，Windows 下改成PY=python。对拍脚本本身也是模板，存进模板库时要保证跨平台能跑。

6. 给新模板做冒烟测试：一份边界数据构造清单

模板写进库里不等于能用，我习惯在每份模板旁边放一个边界数据生成器，把最容易触发 bug 的输入写死，先跑一遍再上对拍。这份清单比随机数据可靠得多：

对应的生成器可以做成一个带参数的小脚本，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 相加溢出成负数，从那以后每份模板进库先跑边界数据，再交给对拍脚本做十万组随机验证。模板的价值不在数量，在于它能让你在赛场上少想十秒钟、少错一个下标。希望这份清单对你也有用。

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