企业官网建设流程全解析

简介：这是一份面向ACM竞赛选手与算法自学者的基础算法模板合集，涵盖快速读入、高精度四则运算、快速幂、组合数与排列数（模运算）、质数判定与分解质因数、欧拉筛等常用实现，并附最大公约数、最小公倍数及整数二分模板，可直接套用于平时练习与赛场编码。包体为单个PDF文档，共513KB，便于离线查阅或打印；结构按数论与基础运算模块编排，代码风格简洁，关键函数均给出参数与边界处理说明。目前已有224人浏览学习，适合刚接触竞赛编程、需要系统性整理常用代码模板的读者。通过这份模板，可快速搭建自己的算法工具箱，减少重复造轮子的时间，同时通过对照标准实现加深对高精度进位、快速幂与线性筛等核心思路的理解。

1. 拿到《ACM基础算法模板2》后，我做的第一件事不是背它

《ACM基础算法模板2》这名字听起来像一本要背的板子合集，但实际用下来，它更像一份“前人把坑都踩平了”的代码库。我见过不止一个同学拿到之后从头抄到尾，抄完照样不会做题；也有人只翻目录，比赛时现搜现改，最后连编译错误都来不及修。《ACM基础算法模板2》真正解决的问题只有一个：让常用算法从“凭记忆写”变成“按需取用”，把省下来的时间留给思路而不是敲键盘。适合三类人：刚入门的竞赛新手、准备算法面试想快速找回手感的人、以及每周带训的教练。这篇笔记不评价它哪里写得好，只讲怎么用、怎么改、怎么让它为你所用。

2. 拆模板库的骨架：目录结构、快读快写与调试开关

模板库到手，先别急着打开某个算法的源文件。我习惯先把整份模板当成一个项目来做结构拆解，搞清楚目录怎么组织、公共模块有哪些、模块之间有没有依赖。这一步花不了二十分钟，但能省掉后面无数次“这个板子从哪个文件复制”的纠结。

2.1 目录结构：按算法分类还是按题目场景分类

第一版模板库常见的组织方式是纯算法分类：图论一个目录、数论一个目录、数据结构一个目录。但做题时你在读题阶段往往不知道这题考的是哪个算法，只知道“这题要求最大连通块”“这题是最小值最大”这类场景特征。市面上大多数实用的ACM模板第二版会采用“场景+算法”混合索引，比如把“区间问题”“树上问题”“背包问题”这类目录直接放在一级分类旁边。目录长什么样直接影响你比赛时翻模板的速度。

我一般会先确认“00 输入输出”和“07 杂项”里有没有对拍脚本和调试开关。原因很简单：模板里的算法代码是拿来抄的，而输入输出、调试、对拍是拿来活命的。没有这两个目录的模板库，哪怕算法再全，比赛现场也容易在低级问题上翻车。

第二版模板和第一版比，有个常见变化值得注意：易错点不再单独写在文档里，而是直接写进每个模板文件头部的注释中。这个设计很实用，因为赛场上没人有时间切出去翻说明文档，能让你一眼看到“注意：这里的模数可能为 1”的模板，才是救命的模板。

2.2 快读快写：为什么模板里总有一套自制的 IO 类

几乎每一份 ACM 模板库都会自带一套快读快写，那是因为cin和cout在关闭同步后虽然勉强能用，但只要数据量一上百万、或者需要大量混合读入字符和数字，性能就会变得非常不靠谱。而scanf/printf虽然稳定，处理数字时却不如手写字符解析快。模板第二版里最常见的做法是给一个定制的 FastIO 类：

#include <bits/stdc++.h> using namespace std; class FastIO { static const int BUF_SIZE = 1 << 20; char rbuf[BUF_SIZE], *p1, *p2; char wbuf[BUF_SIZE], *p3; int wsize; public: FastIO() : p1(rbuf), p2(rbuf), p3(wbuf), wsize(0) {} ~FastIO() { flush(); } char getch() { if (p1 == p2) { p1 = rbuf; p2 = rbuf + fread(rbuf, 1, BUF_SIZE, stdin); if (p1 == p2) return EOF; } return *p1++; } int readInt() { int x = 0, sign = 1; char c = getch(); while (c != '-' && (c < '0' || c > '9')) { if (c == EOF) return 0; c = getch(); } if (c == '-') { sign = -1; c = getch(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getch(); } return x * sign; } void writeInt(int x) { if (x < 0) { putch('-'); x = -x; } char s[12]; int n = 0; do { s[n++] = char('0' + x % 10); x /= 10; } while (x); while (n--) putch(s[n]); putch('\n'); } void putch(char c) { if (wsize == BUF_SIZE) flush(); wbuf[wsize++] = c; } void flush() { if (wsize) { fwrite(wbuf, 1, wsize, stdout); wsize = 0; } } };

这段代码的逻辑核心是“绕过标准库，自己做字符缓冲”。readInt从输入缓冲区里逐个字符读，跳过非数字字符，遇到-记符号，再连续累加数字，最后拼成整数。writeInt则把整数一位一位拆出来写进字符数组，最后统一输出，避免频繁调用系统写入。

值得注意的参数是BUF_SIZE = 1 << 20，也就是 1MB 的输入输出缓冲区。这是竞赛圈里很常见的折中值：缓冲区太小会频繁触发系统调用，太大则浪费内存而且缓存命中率反而下降。这道模板里用了fread做整块读入，p1和p2分别指向当前读取位置和块结束位置，当p1 == p2时说明当前块读完了，再读下一块。我一般会提醒新手：把readInt返回类型改成long long时，内部累加变量也要一起改，只改外层是 dalao 才能驾驭的写法，普通人容易在负数输入上出问题。

2.3 调试开关与对拍脚本：第二版模板里最容易被忽略的部分

模板库里的算法代码再漂亮，没有一套可靠的验证手段也是白搭。第二版模板通常会把“本地调试”和“赛场提交”区分开，最常见的手段是编译器宏：

#ifdef LOCAL freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); #endif

本地编译时加一个-DLOCAL参数就会读文件，提交到 OJ 时不加这个宏，代码自动走标准输入输出。这个技巧比在代码里写死文件名要安全，因为 OJ 上一般不允许读取本地文件。另一个配套工具是数据生成器和暴力对拍脚本，跑随机数据验证模板的正确性：

#!/bin/bash # 对拍脚本：随机生成数据 -> 跑两份代码 -> 比较输出 # 用法：./duipai.sh your_solver std_solver data_generator for i in $(seq 1 100); do ./$3 > input.txt ./$1 < input.txt > out_a.txt ./$2 < input.txt > out_b.txt if ! diff -q out_a.txt out_b.txt > /dev/null; then echo "第 $i 组数据出错" break fi done

这段脚本的逻辑是循环 100 轮，每轮先用第三参数（数据生成器）生成一组随机输入，再分别运行你的程序和一个保底的暴力程序，最后用diff比对输出。只要有一组不一致就停住并打印轮数。参数说明里最容易踩的坑是脚本参数的顺序：三个参数分别是“被测程序”“标准程序”“生成器”，写反了脚本会直接报“权限不够”或者跑出令人迷惑的结果。第二版模板里的对拍脚本一般会写得更完善，比如加一个“生成的数据同时保存一份到当前目录”的选项，方便出错后复现，这个设计很实用，我很推荐自己加上。

3. 核心模板的选型：并查集、前向星与快速幂的取舍

模板库里的算法往往不止一种写法。同样是并查集，有的给递归版，有的给迭代版；同样是建图，有的用vector邻接表，有的用链式前向星；快速幂也分普通版本和应对溢出风险的版本。第二版模板真正考验人的不是“抄哪个”，而是“这题该选哪个写法”。选错写法的后果通常不是 WA，而是 TLE 或者爆栈，这类问题比算法想错更隐蔽。

3.1 并查集：递归版简洁，迭代版保底

并查集是 ACM 里出现频率极高的数据结构，它的核心操作只有两个：查找根节点和合并两个集合。递归版写起来非常短：

int find(int x) { return fa[x] == x ? x : (fa[x] = find(fa[x])); }

这一行做了两件事：沿着父指针向上找根，同时把路径上经过的每个节点直接挂到根上，这就是路径压缩。下次再查同一个节点时，只需要走一步就能到根。递归版的问题是，当数据构造出深度很大的链时，递归层数可能达到1e5甚至更多，在部分评测机上会爆栈。迭代版多写几行，但完全避免了这个问题：

int find(int x) { int r = x; while (fa[r] != r) r = fa[r]; // 先找到根 r while (x != r) { // 再回头把路径上的节点压缩 int t = fa[x]; fa[x] = r; x = t; } return r; }

逻辑拆成两段：第一段从当前节点一路往上走到根，第二段把路径上所有节点的父指针直接指向根。参数说明里要注意fa数组的初始化，每个节点的fa[i] = i不能漏，否则find会无限循环。我一般会建议模板使用者把迭代版作为默认版本，递归版只在确认数据规模小（比如点数不超过1e4）时使用，毕竟谁也不知道出题人会不会构造一条链来卡递归。

并查集的复杂度分析有一个常用结论：只做路径压缩、不按秩合并，单次操作摊还复杂度接近O(log n)；路径压缩加按秩合并后接近O(1)。第二版模板里通常会同时给出这两个优化。按秩合并的意思是让深度小的树挂到深度大的树上，代码上需要维护一个depth或size数组。实际比赛里，只做路径压缩的并查集已经能应付绝大多数题目，但如果你正在写 Kruskal 最小生成树且边数达到1e6级别，加个按秩合并能稳定减少运行时间。

3.2 建图方式：邻接表和链式前向星怎么选

图论题的模板第一步是建图，而建图方式直接决定后续代码的写法和常数。vector<int> g[N]这种方式最直观，每加一条边就push_back一次，遍历时用范围循环很方便。链式前向星则更接近数组模拟链表的写法，内存更紧凑，而且在网络流这类需要成对建反向边的算法里有决定性优势。对比一下两者：

链式前向星的模板代码：

struct Edge { int to, w, next; } edge[M]; int head[N], cnt = 0; void addEdge(int u, int v, int w) { edge[++cnt] = {v, w, head[u]}; head[u] = cnt; }

这里的逻辑是：每条边用一个整数cnt作编号，head[u]记录从点u出发的第一条边编号，edge[i].next指向下一条边。加边时把新边插到链表头部，所以遍历顺序与加边顺序相反。参数说明里有两个关键点：第一，M必须开成2 * maxEdgeCount，因为无向图每条边要存两遍；第二，head数组初始化为 0，同时edge编号从 1 开始，这样i = edge[i].next到 0 时表示遍历结束。如果head初始化成-1，edge编号从 0 开始也可以，但代码会多几行判断，不太推荐。

什么时候必须用链式前向星？写最大流（Dinic 或 ISAP）的时候几乎必须。网络流算法需要在加正向边时同时加一条反向边，这两条边的编号相邻，可以通过i ^ 1找到彼此。用vector存边时，reverse边的下标管理会很痛苦，而前向星只需要从cnt = 1开始编号，正向边和反向边就天然配对。如果不涉及网络流，我一般更推荐vector邻接表，因为它写起来快、不容易出错，普通最短路和 DFS 题完全够用。

3.3 快速幂与逆元：模运算里藏着三个坑

快速幂是数论模板里最基础的板子，几乎每份模板里都有。但这份板子恰恰是最容易被“以为对了”的代码，原因在于模运算的边界条件特别多。标准的迭代写法：

using ll = long long; ll qpow(ll a, ll b, ll mod) { ll res = 1 % mod; a %= mod; while (b) { if (b & 1) res = (__int128)res * a % mod; a = (__int128)a * a % mod; b >>= 1; } return res; }

逻辑是二进制拆解：把指数b看成二进制数，如果当前位是 1，就把当前的a乘进结果；每处理一位，a自乘一次即平方，然后b右移一位。这里的(__int128)是防止两个接近1e9的数直接相乘溢出 64 位整数。虽然res * a最大到(1e9)^2 = 1e18还没超过long long，但a * a再乘mod的组合在逆元场景下就可能超，提前用__int128是最省心的办法。

这个板子有三个必须注意的参数点。第一，res初始化写成1 % mod而不是裸的1，因为当mod = 1时答案是 0，直接写 1 会 WA；第二，a在运算前要先a %= mod，否则a超过mod时结果会偏；第三，如果指数b是负数，这个快速幂不适用，应该改用扩展欧几里得求逆元。费马小定理inv(a) = qpow(a, mod-2, mod)只有mod是质数时才成立，很多人模板抄多了忘了前提条件，遇到合数模直接套用，结果错得莫名其妙。合数模求逆元必须用扩展欧几里得：

ll exgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) { x = 1; y = 0; return a; } ll gcd = exgcd(b, a % b, y, x); y -= a / b * x; return gcd; }

返回的x就是a在模b意义下的逆元，注意最终要把x调整到非负范围。这个模板同样递归，数据规模小时没问题，超大数时最好也改成迭代版，但一般用到exgcd的数据量不大，递归版够用。

4. 套模板做题的四步流程：识别特征、预演复杂度、修改边界、验证输出

模板库用得好不好，区别不在于你抄了多少段代码，而在于你能不能在三分钟内判断“这题该用哪块板子”。我把这个过程拆成四个固定步骤：识别特征、预演复杂度、修改边界、验证输出。每次套模板都走一遍这个流程，能减少非常多的无效提交。

4.1 题干特征词和模板的对应关系

读题时，题干里的某些关键词几乎直接指明了算法方向。比如“连通块”“是否成环”基本指向并查集；“第 k 小”“最大值最小”“最小值最大”指向二分答案；“区间最大值”“区间和”指向线段树或树状数组；“DAG”“拓扑顺序”指向拓扑排序；“两个字符串的匹配”指向 KMP。这些对应关系在模板第二版的目录里也简化成了一张映射表，但真正用起来可以更细：

这个表不是绝对的，但它能让你在比赛开始前五分钟不至于对着题目发呆。识别特征的关键是注意陷阱：题目说了“无环”不一定用并查集，可能是在考拓扑排序；“最短路径”不一定是单源，可能是多源时就要建超级源点跑一次 Dijkstra。识别题型不是背题，而是用上文已积累的敏感度快速圈定候选模板，真正的判断还要靠下一步的复杂度预演。

4.2 套模板前的三分钟预演：复杂度、空间、边界

锁定候选模板后，不要急着复制粘贴，先做三分钟预演。第一看复杂度是否匹配数据范围：题目给n = 1e5，如果你选的是O(n^2)的板子（比如朴素 LIS），那代码再正确也会 TLE；第二看空间是否够用：线段树开4 * n，树状数组开n + 1，前向星按2 * m开（无向图），这些经验值一旦记错就会出现“数组越界 RE”和“内存超限 MLE”两种极端；第三看边界条件：数组是否可能为空、答案是否可能超过int、图是否有孤立点。这三项里任何一项没确认，都先不要写代码。

预演时有一类高频错误特别值得提：图论题的n和m范围是分开给的，n可以很小但m特别大。比如n = 1e4, m = 1e5，你把邻接表数组开到N = 1e5是够用的，但前向星的edge数组开成MAXN = 1e5就不够了，因为无向图每条边存两遍需要2 * m的空间。这种问题本地小数据根本测不出来，一上大数据就 RE。我把这类坑归类为“范围预演没做全”，记住一个原则：跟边有关的数组看m，跟点有关的数组看n，两者都不能省。

4.3 一个完整示例：把 LIS 的 O(n log n) 板子改成本地可跑的程序

我拿最长上升子序列（LIS）举例，因为这个模板短，但很多人套的时候会在边界上出错。第二版模板里的 LIS 一般有两种实现：lower_bound版和手写二分版。先看最直观的 STL 版：

#include <bits/stdc++.h> using namespace std; int lisLength(const vector<int>& a) { vector<int> tail; for (int x : a) { // lower_bound 返回第一个 >= x 的位置，把这个位置替换成 x auto it = lower_bound(tail.begin(), tail.end(), x); if (it == tail.end()) tail.push_back(x); else *it = x; } return (int)tail.size(); } int main() { vector<int> a = {3, 1, 2, 1, 8, 5}; cout << lisLength(a) << "\n"; // 输出 3（1, 2, 5） return 0; }

这段代码的逻辑是维护一个tail数组，tail[i]表示长度为i + 1的上升子序列的最小末尾值。遍历原数组时，用lower_bound找到第一个不小于x的位置并替换它；如果x比tail里所有数都大，就说明可以接出一个更长的子序列，push_back。最终tail.size()就是 LIS 长度。注意它求的是严格上升，如果题目要求“最长不下降子序列”，要把lower_bound换成upper_bound，这样相等元素也能接上。

手写二分版性能更好一点，因为避免了 STL 迭代器的函数调用开销，但逻辑完全一样。模板库第二版按惯例会同时给两个版本，并在注释里标注“常数列中 STL 版本用于快速实现，大数据量请改手写”。我自己在比赛里几乎只用 STL 版，唯一例外是总运行时间卡得很紧的题，那时才切到“数组 + 手写二分”。套用任何 LIS 板子之前，先确认两件事：第一，输入序列可能为空，此时tail为空、返回 0 是正确的；第二，序列里有重复值时，严格上升和不下降的写法完全不同，题干里的“严格”二字值五分。

5. 模板翻车排查：五个常见问题和对应的解决办法

用了两年模板，我踩过的坑比写过的题多。很多问题不是算法不会，而是模板使用方式出了偏差。下面五条是我在实际使用中见过最多、也最容易反复出现的翻车记录，每一条都按“现象、原因、解决”来梳理。

5.1 本地样例全过，提交上去就是 WA

现象：样例输出和标准答案一模一样，本地随便造几组手写数据也没问题，一提交就是 WA，而且没有 RE 或 TLE，就是单纯答案错。

原因：最常见的是多组测试数据之间没有重置全局数组和计数器。很多模板把数组开在全局，第一组数据跑完后，第二组数据开始时某些数组里还是上一组的残留值；另一个原因是输出格式，比如题目要求每组数据之间输出一个空行，你的代码只在每组结束后printf("\n")，而要求是两组之间才有空行，最后一组后面没有。

解决：每道题都要写一个init()函数，在读到新一组数据开头时调用，把计数器归零、关键数组重置。输出格式的问题用“先构造整串输出再一次性打印”的方式规避，或者干脆把所有输出写进一个string，最后printf一下，这样行末空格和空行的位置都直观可见。

5.2 TLE 不是算法不够优，而是常数大到离谱

现象：复杂度算出来明明是O(n log n)，n也只有1e5，但提交后 TLE，本地跑却只要 0.3 秒。通常这种题你无法通过换算法优化，只能优化常数。

原因：第一，用了cin且没关同步；第二，cout频繁输出，每次输出都触发一次 flush；第三，vector在循环里反复resize或push_back导致多次内存分配；第四，模板里用了lower_bound在大循环内高频调用，STL 的封装和函数指针开销被放大。

解决：输入输出全部换成模板自带的 FastIO 类；cout的endl全部改成'\n'；vector在循环前先reserve好容量；高频二分场景下手写二分，别用 STL。优化顺序一般先 IO 后容器再算法内细节，这三板斧下去绝大多数 TLE 都能缓解。

5.3 数组开多大是门玄学：开小了 RE，开大了 MLE

现象：数组开小了，越界访问在本地小数据时没事，OJ 大数据直接 RE；数组开大了，比如每个都按1e7开，几个数组一叠加就 MLE。

原因：很多人开数组靠猜，而不是计算。不同类型数组占的内存不一样：int4 字节、long long8 字节，bool1 字节。一个long long a[1000005]就占 8MB，OJ 内存限制 256MB 时开几十个这样的数组，MLE 很容易。

解决：把常用数组的经验值背下来。线段树开4 * N是因为递归建树时节点编号可能溢出到4N；树状数组开N + 1因为下标从 1 开始；前向星无向图开2 * M；depth数组在递归 DFS 里默认就是N + 1。如果题目给的是n = 1e5, m = 1e5，算一下总内存：线段树的4 * 1e5个int是 1.6MB，前向星的2 * 1e5个Edge如果每个含两个int和一个int，总共约 2.4MB，完全够。养成“开数组前先乘法算字节”的习惯，MLE 和 RE 能少一半。

5.4 两个模板拼在一起编译不过：宏定义和全局变量打架

现象：把“数论模板”和“图论模板”复制到同一个工程里，编译直接报重定义或宏展开错误。有时候甚至只是两个模板文件各自的#define冲突。

原因：很多模板为了简洁喜欢写#define int long long或者#define rep(i, a, b) for (int i = a; i < b; ++i)。这些宏放在单文件里没有问题，但当你从两份模板里各复制一段时，两个宏定义撞在一起，或者宏作用域意外扩大，STL 内部代码被#define int long long影响后直接编译失败。

解决：模板尽量以struct或namespace封装，全局只暴露少量接口；不要用#define int long long这种作用域不可控的宏，改成using ll = long long然后在代码里显式写ll；如果两个模板确实有同名全局变量，复制时手动加前缀，比如seg_tree_sum和graph_head，虽然难看但安全。养成“模板文件之间尽可能不共享全局命名空间”的习惯后，拼模板基本不会再出编译错。

5.5 上次能过的板子这次 WA 了，但你想不起来改过哪里

现象：某个模板今天用着好好的，过几天再拿来写同类型题，莫名其妙 WA。翻看模板代码，发现里面已经被改得面目全非，但提交记录里看不出哪一步改出了问题。

原因：模板文件被原地直接修改了。比赛时发现模板有 bug，当场顺手改了；赛后没做任何记录，几个月后拿这份“修过”的模板去写新题，bug 早已被遗忘。这是模板使用里最隐蔽的坑，因为问题出在版本管理而不是算法。

解决：用git管理模板库，哪怕不推送到远程仓库，本地也是一个仓库。每次赛前赛后都git commit一次，提交信息写清楚“改了哪份模板、为什么改”。没有git习惯的人至少做到“模板文件只读，每次要用先复制到题目目录再改”。我给自己的规矩是：模板库里任何文件都不能直接编辑，要改先复制出一个带日期后缀的新文件，改完验证没问题再合并回模板目录。这习惯救过我好多次。

6. 让模板库变成自己的算法笔记：一个可持续迭代的小工作流

模板库的价值不是背，而是持续迭代。你做过一百道题之后，应该有一套“只属于自己的模板”——它不像网上公开版那样什么都有，但每一段都是你亲手验证过、踩过坑、注释里写满教训的代码。我的做法是每次比赛或集中刷题结束后，花半小时做一次模板维护。比赛时“想了两小时才写出来”的核心逻辑，赛后提炼成模板；“差点翻车”的边界条件，写进头部注释。

每个模板文件的头部我固定写三行信息：适用条件、复杂度、易错点。适用条件写清楚“这个板子只能在无向图用”“这里的模数必须是质数”；复杂度写清楚是O(n log n)还是O(n^2)；易错点写“数组开 2 倍”“记得清空计数器”这种一句话就能救命的内容。注释写得比代码还多并不丢人，因为三个月后再打开这份模板时，注释才是真正属于你的东西。

版本管理我用最原始的git工作流：模板库是一个本地仓库，每次改动提交一次，提交信息写清楚原因。有一次我用了一个刚加的 Treap 模板，没跑对拍就交，结果 TLE 到比赛结束。赛后复盘发现模板里递归层数太深，大数据直接爆栈。从那以后我立了一条规矩：任何新模板想进“常用”目录，必须先用对拍脚本配合暴力程序跑 100 组随机数据验证；验证通过的才允许进入常用目录，否则只放在“实验区”。这套流程坚持了大半年，赛场上再没出过“模板本身是坏的”这种低级事故。希望这些习惯能帮到你，让你手里那份模板真正成为比赛里的底气。

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