企业官网建设流程全解析

简介：面向ACM/ICPC等程序设计竞赛的C++实用模板库，按七大主题分类组织，涵盖头文件模板、数学、字符串、数据结构、图论、计算几何与动态规划，既适合赛前速刷，也可用于日常训练和教学参考。压缩包共83个文件，以65个C++代码文件为主，辅以TeX/PDF速查手册、Python辅助脚本、Makefile及开源许可说明，整体约449KB，目录结构清晰，便于按需取用。已有29人学习下载。模板内置快速幂、Dijkstra、KMP、线段树、凸包、LCS等经典实现，覆盖数论、图论、字符串匹配、区间维护、几何凸包和最长公共子序列等高频考点，各模块代码注释规范，可按需裁剪组合。配套的LaTeX源码可自行编译生成速查手册，Python脚本和Makefile能辅助本地测试与环境配置，降低上手成本。对需要系统储备算法模板、快速搭建代码骨架的竞赛选手而言，是一份开箱即用、便于二次修改的工具集。

1. C++竞赛常用算法模板合集：背得下来的代码才算模板

C++竞赛常用算法模板合集，覆盖图论、动态规划、计算几何等核心模块——这句话听起来像网盘里某个几百兆的压缩包，但真正上过赛场的人知道另一件事：模板的价值不在文件数量，而在你能不能顶着压力三分钟之内敲对、调通、跑出样例。见过太多同学收藏了别人的豪华模板库，考场上却连一个堆优化 Dijkstra 都要翻笔记翻五分钟，最后对着输出发呆。

这个方向真正要解决的，从来不是「有没有代码」，而是「这套代码是不是你自己的」。一份合格的竞赛模板，每个算法背后至少要带三样东西：选型理由、边界设定、已经踩过的坑。图论、动态规划、计算几何刚好是赛题里最高频的三个分类，把它们各自固定成一两套顺手写法，比收集一百个版本有用得多。适合读下去的人，是已经学过基础语法、刷过一定题量、准备系统整理自己代码库的选手，下面按模块讲我常用的方案。

2. 图论模板：堆优化 Dijkstra 与并查集的两套赛场写法

2.1 建图选型：邻接表为什么是默认选项

拿到一道图论题，第一步是建图。很多入门教程先教邻接矩阵，但竞赛数据规模普遍到 1e5 个点以上，g[N][N]的二维数组光内存就是 40GB 起步，直接出局。所以邻接表是默认选项，常见写法有两种：vector邻接表和链式前向星。

#include <bits/stdc++.h> using namespace std; const int N = 100005; vector<pair<int, int>> g[N]; // g[u] = {v, w}，表示 u 到 v 有一条边权为 w 的边 void addEdge(int u, int v, int w) { g[u].push_back({v, w}); // 如果是无向图，再补一行 g[v].push_back({u, w}); }

vector<pair<int,int>>的写法在大多数在线评测系统上完全够用，代码短、调试方便、遍历时直接拿auto [v, w]拆包。它的代价是内存不连续，极端密集图上访问速度稍慢，但竞赛中 2e5 级别边的场景很少被这点差距卡掉。链式前向星用数组模拟链表，内存连续、常数更小，缺点是插入顺序是逆序的，代码也长一截。我一般建议：平时练习和多数比赛用vector版本，只有遇到老牌题库那种卡常严重的题目才临时切前向星。

建图这步最容易翻车的不是选型，而是忘记开N的上限。N开小了，越界写入会静默污染相邻内存，表现是「本地跑得好好的，交上去随机 WA」。我的习惯是N直接开到题目上限加 5，多出来的几个位置不心疼。

2.2 堆优化 Dijkstra：INF 与过期出堆

单源最短路里，堆优化 Dijkstra 是出场率最高的模板，没有之一。它要求边权非负，复杂度 O(M log M)，应对 2e5 级别数据是常规操作。下面这份代码我用了很多年，重点在两处：INF 的取值和出堆时的判断。

typedef long long ll; const ll INF = 4e18; ll dist[N]; void dijkstra(int s) { fill(dist, dist + N, INF); dist[s] = 0; // 小顶堆：pair 先按第一关键字排序，所以距离放前面 priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); // 过期的堆顶：这个节点之前被松弛过，距离已经不是最新值 if (d != dist[u]) continue; for (auto [v, w] : g[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push({dist[v], v}); } } } }

INF 为什么用4e18而不是0x3f3f3f3f？因为dist[u] + w可能超过 int 上限，一旦溢出就会得到错误的比较结果，这是隐蔽的翻车点。用long long配合4e18，只要边权总和不超过 1e18 就安全。出堆判断用d != dist[u]而不是开一个vis数组提前continue，原因是同一个点可能被多次压入堆中，开vis会让「先被非最优路径松弛、后又被更优路径更新」的合法情况被跳过，这个坑在第 5 章还会展开讲。

实际使用注意两点：第一，fill只填了N个位置，如果提前 return 出去导致部分距离没被更新，输出前要判断dist[t] == INF；第二，题目要求最长路时不要直接改符号用 Dijkstra，那需要反过来想或者改用别的算法。

2.3 并查集与 Kruskal：路径压缩一个技巧就够了

并查集是图论里最像「工具件」的模板，判连通、判环、合并集合都靠它。完整写法包含路径压缩和按大小合并两个优化，但竞赛里路径压缩已经能把复杂度压到近似常数，按大小合并属于「锦上添花」。

int fa[N], sz[N]; 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里的swap有人觉得多余，其实它能防止极端数据下链式结构退化。竞赛里我见过有人只写路径压缩不写秩合并也照样过，两者都写上更稳。

Kruskal 最小生成树把并查集的判环能力用得最典型：

struct Edge { int u, v, w; }; vector<Edge> edges; long long kruskal(int n) { sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) { return a.w < b.w; }); init(n); long long ans = 0; int cnt = 0; for (auto e : edges) { if (find(e.u) != find(e.v)) { // 两个端点不连通，说明这条边不会成环 merge(e.u, e.v); ans += e.w; cnt++; } } if (cnt < n - 1) return -1; // 图不连通，补不成生成树 return ans; }

排序是 Kruskal 的复杂度瓶颈，O(M log M)。cnt用来统计已选边数，如果最后少于n - 1，说明原图本身不连通，这种情况下返回 -1 比返回一个错误答案更好排查。

3. 动态规划模板：线性 DP、背包、区间 DP 与状压

3.1 线性 DP 与 LIS 二分优化：长度与序列别混淆

动态规划的地基是线性 DP，而线性 DP 里最值得背进模板的是最长上升子序列（LIS）的二分优化版本。朴素做法 O(N^2) 在 5e4 级别就会超时，二分优化直接降到 O(N log N)，代码还更短。

vector<int> a; vector<int> tails; // tails[len] 表示长度为 len 的上升子序列的最小末尾值 for (int x : a) { auto it = lower_bound(tails.begin(), tails.end(), x); if (it == tails.end()) tails.push_back(x); else *it = x; } cout << tails.size() << '\n';

tails维护的是一组「最小末尾值」，lower_bound找到第一个不小于x的位置并替换它。替换的意义是：同样长度下末尾值越小，后面越容易接上更长的序列。这里有两个高频混淆点：第一，tails本身不是那个上升子序列，它只用于计算长度，想还原具体序列得另开数组记录前驱；第二，题目要求非严格递增时，lower_bound要换成upper_bound，否则连续相等的序列会被错误地算成非法。

线性 DP 不止 LIS，最大子段和、最长公共子序列都有自己的惯用写法，但思路都是「定义状态 → 找转移 → 定边界」，模板里每个留一题做注释就够了。顺便说一句，单调栈这类数据结构虽然不算 DP，但它和线性 DP 经常搭档出现，比如最大矩形面积那题，单调栈维护的就是「以当前位置为高的可扩展边界」，两者可以一起整理进笔记。

3.2 01 背包滚动数组：倒序是硬规则

背包问题在动态规划里的地位不用多说，01 背包的滚动数组写法几乎每场比赛都会用到。它的核心就一个词：倒序。

vector<int> dp(W + 1, 0); // dp[j] 表示容量为 j 时的最大价值 for (int i = 1; i <= n; i++) { int w, v; cin >> w >> v; for (int j = W; j >= w; j--) { // 倒序更新：保证 dp[j-w] 是上一件物品的状态 dp[j] = max(dp[j], dp[j - w] + v); } }

倒序的原因很直接：如果正序更新，dp[j - w]可能已经被本轮物品更新过，相当于同一件物品被取了多次，这就变成完全背包了。反过来，完全背包正是利用正序实现「无限取」，两组模板放一起记，就不容易混。滚动数组把空间从 O(NW) 压到 O(W)，时间没变，仍然要 O(NW)，所以看到 W 到 1e5、N 到 1e4 的题，要立刻反应出这不是裸背包。

一个容易忽略的细节：dp初始化成 0 对应「恰好装满」和「不超过容量」两种语义。题目问「恰好装满」时，通常初始化成-INF，只让dp[0] = 0；问「最大价值不超过容量」则直接全 0。这两种初始化在赛题里反复出现，模板注释里一定要写清楚。

3.3 区间 DP 与状压 DP：两类必须背的转移骨架

区间 DP 的经典场景是合并石子、矩阵链乘、回文分割。「枚举长度、枚举左端点、枚举断点」这三层循环的顺序是硬骨架，写错顺序结果全错。

int n; vector<long long> sum(n + 1, 0); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i]; vector<vector<long long>> dp(n + 1, vector<long long>(n + 1, LLONG_MAX)); for (int i = 1; i <= n; i++) dp[i][i] = 0; for (int len = 2; len <= n; len++) { // 第一维：区间长度 for (int l = 1; l + len - 1 <= n; l++) { // 第二维：左端点 int r = l + len - 1; for (int k = l; k < r; k++) { // 第三维：断点 dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1]); } } }

为什么第一维必须是长度而不是左端点？因为区间 DP 的转移依赖于更短的区间，外层先枚举长度，才能保证计算dp[l][r]时dp[l][k]和dp[k + 1][r]都已经算完。如果先枚举左端点，dp[k + 1][r]里k + 1比l大，对应的区间还没算过，结果就是一堆随机值。sum[r] - sum[l - 1]用前缀和求区间合并代价，这是合并类题目的固定套路。

状压 DP 的骨架完全不同，它用二进制位表示集合状态，典型场景是旅行商问题（TSP）。点数 n 一超过 20 就基本不可行，因为状态数有 2^n 个。

const int INF = 0x3f3f3f3f; int dist[20][20]; int dp[(1 << 20)][20]; // dp[state][u]：已访问集合为 state，当前位置在 u void solve(int n) { memset(dp, 0x3f, sizeof(dp)); dp[1][0] = 0; // 从顶点 0 出发，集合里只有 0 for (int s = 1; s < (1 << n); s++) { for (int u = 0; u < n; u++) { if (!((s >> u) & 1)) continue; // u 不在当前集合里 for (int v = 0; v < n; v++) { if ((s >> v) & 1) continue; // v 已经访问过 dp[s | (1 << v)][v] = min(dp[s | (1 << v)][v], dp[s][u] + dist[u][v]); } } } int ans = INF; for (int i = 1; i < n; i++) { ans = min(ans, dp[(1 << n) - 1][i] + dist[i][0]); // 走完全部点后回到 0 } }

状态转移的方向是「从集合 s 往外扩展一个点」，(s | (1 << v))表示把 v 加入集合。复杂度 O(2^n · n^2)，所以 n 在 15 到 18 之间是安全区。这里有个实用小技巧：枚举 s 的子集用for (int sub = s; sub; sub = (sub - 1) & s)，它在处理「集合划分」类题目时能省掉一层循环，值得单独背下来。

4. 计算几何与数论：叉积、凸包与快速幂

4.1 二维向量与线段相交：叉积定方向

计算几何入门第一件事是明确坐标类型。很多新手直接double一把梭，结果被精度问题折磨到怀疑人生。常见做法是：坐标能整数就整数，用long long存，叉积和点积结果不会溢出；非用浮点不可时，保留 eps 比较。

struct Point { long long x, y; Point operator+(const Point &p) const { return {x + p.x, y + p.y}; } Point operator-(const Point &p) const { return {x - p.x, y - p.y}; } long long cross(const Point &p) const { return x * p.y - y * p.x; } long long dot(const Point &p) const { return x * p.x + y * p.y; } }; // 向量 ab 与 ac 的叉积 long long cross(const Point &a, const Point &b, const Point &c) { return (b - a).cross(c - a); }

叉积的正负号就是方向判定：大于 0 表示 c 在 ab 的逆时针方向，小于 0 是顺时针方向，等于 0 表示三点共线。这个性质撑起了一大批几何操作：判断点是否在线段上、判断线段是否相交、求多边形面积、求凸包。点在线段上判定的标准写法是「先共线、再在包围盒内」：

bool onSegment(Point p, Point a, Point b) { if (cross(a, b, p) != 0) return false; // 不共线直接排除 return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) && min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y); }

这里用!= 0是因为坐标是整数，叉积精确，不存在浮点误差。如果坐标是double，就要换成fabs(cross(...)) <= eps，eps 通常取 1e-9。用long long还有一层好处：1e9 级别的坐标做叉积不会溢出，用int存坐标的话，光这一步就足够让题目变玄学。

4.2 Andrew 凸包：横坐标排序的两趟扫描

凸包是计算几何的中频考点，Andrew 算法比极角排序的 Graham 扫描更好写、更好记，原理是「按横坐标排序后用两趟扫描分别求出下凸壳和上凸壳」。

bool cmp(const Point &a, const Point &b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; } vector<Point> convexHull(vector<Point> pts) { sort(pts.begin(), pts.end(), cmp); vector<Point> hull; hull.reserve(pts.size() * 2); for (int phase = 0; phase < 2; phase++) { int start = hull.size(); for (Point p : pts) { // 逆时针拐弯的点不要，<= 0 表示把共线点也去掉 while (hull.size() >= start + 2 && (hull[hull.size() - 1] - hull[hull.size() - 2]) .cross(p - hull[hull.size() - 2]) <= 0) { hull.pop_back(); } hull.push_back(p); } hull.pop_back(); // 去掉每趟结束时重复的首尾点 reverse(pts.begin(), pts.end()); } return hull; }

第一趟从左往右扫出下凸壳，第二趟把点序反转后扫出上凸壳，最后pop_back去掉重复点。判断条件里的<= 0会把共线点剔除，如果你要保留边界上的所有点，改成< 0即可。这个模板对坐标排序有硬要求：横坐标相同必须按纵坐标排，否则同竖直线上的点会处理错。

凸包题的常见变体是「求凸包周长」和「求最小覆盖矩形」。周长好办，累加相邻点距离，注意别漏掉首尾相连；最小覆盖矩形则要配合旋转卡壳，属于进阶内容，第一版模板先不写进去，等刷到对应的题再补。

4.3 快速幂与质数判断：两个高频数论件

数论模块里最值得放进模板的是快速幂和质数判断。快速幂的递归改迭代版本短小且不容易爆栈：

long long qpow(long long a, long long b, long long mod) { long long res = 1 % mod; // mod == 1 时 res 已经是 0 while (b) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; }

原理是把指数 b 按二进制拆分成若干个 2 的幂次，a每轮自乘对应「指数翻倍」，遇到 b 的最低位是 1 就把当前a乘进答案。复杂度从 O(b) 降到 O(log b)。注意mod很大时a * a可能溢出long long，模数到 1e18 的场景需要额外写快速乘，普通竞赛题模数在 1e9 级别就不用担心。

质数判断的入门写法是试除到根号 n，但可以优化得更彻底一点：所有大于 3 的质数都在 6 的倍数附近，也就是形如6k ± 1的数，所以循环步长直接跨 6。

bool isPrime(long long n) { if (n < 2) return false; if (n % 2 == 0) return n == 2; if (n % 3 == 0) return n == 3; for (long long i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return false; } return true; }

这个写法是判断质数 C++ 优化里最常见的形态，适合 1e12 以内单点判断，速度比i++的朴素试除快约三倍。批量判断就不该逐个数试除了，用欧拉筛：

vector<int> primes; bool isComp[N]; void sieve(int n) { for (int i = 2; i <= n; i++) { if (!isComp[i]) primes.push_back(i); for (int p : primes) { if (1LL * i * p > n) break; isComp[i * p] = true; if (i % p == 0) break; // 核心：每个合数只被最小质因子筛掉一次 } } }

欧拉筛的if (i % p == 0) break;是它区别于埃筛的关键，保证每个合数只被标记一次，复杂度是严格 O(N)。内存上isComp开 bool 数组即可，1e7 规模大约 10MB，在竞赛限制内通常没问题。

5. 模板库落地避坑：初始化、容器与读入的五条血泪经验

5.1 多组数据不清空，答案越跑越离谱

现象：同一份代码，第一组样例输出正确，第二组开始答案偏大甚至越界崩溃。

原因：全局数组和容器带着上一组数据残留，dist没重置、g里还留着上一张图的边、fa数组没重新初始化。最隐蔽的是「只 fill 了前 n 个位置，但后面的访问越过了 n」。

解决：养成两个习惯。第一，把所有状态初始化收进一个init()函数，每组数据开头调用；第二，fill和循环的边界用「实际用到的范围」，比如fill(dist, dist + n + 1, INF)而不是fill(dist, dist + N, INF)，后者虽然没错但浪费，前者逼你想清楚 n 的最大值。vector 邻接表记得for (int i = 1; i <= n; i++) g[i].clear()，这个i <= n少写一个等号就是一组 WA。

5.2 Dijkstra 的 vis 提前跳出：省一步却错一题

现象：堆优化 Dijkstra 加上vis数组，pop 到已访问节点直接continue，小数据全对，大数据随机 WA。

原因：优先队列里同一个节点可能被多次入堆，第一次出堆时距离不一定是最优解——更优的路径可能还在堆里没被 pop 到。如果第一次出堆就标记vis，后面那条更短路径的松弛动作全被跳过。

解决：用if (d != dist[u]) continue;或者if (d > dist[u]) continue;，含义是「这条记录已经过期，丢弃」。这个技巧我在第 2 章就写过，这里再强调一次，是因为我真的见过有人把两份模板混着抄，结果把vis版本和dist版本揉在一起，产出四不像代码。

5.3 01 背包写成正序：完全背包的答案套在 01 背包上

现象：样例过，提交后答案普遍偏大，而且规律是「同一件物品能用多次」。

原因：滚动数组正序更新时，dp[j - w]可能已经是本轮放入该物品后的值，相当于物品被重复选取。

解决：01 背包必须倒序，完全背包必须正序。这两个规则要成对记忆，我见过把「倒序」当万能口诀的人，遇到完全背包也写倒序，答案又偏小，两头挨打。模板里的注释写清楚：「倒序 = 每件最多取一次，正序 = 无限取」。

5.4 计算几何的 int 溢出与 eps 缺失

现象：凸包结果少了点，多边形面积差 1，点在多边形内判断时灵时不灵。

原因：坐标在 1e9 级别时，叉积本身在 1e18 级别，int直接溢出成负数，所有方向判断全反；浮点坐标又没设 eps，相等判断在 0.9999999 和 1.0000001 之间反复横跳。

解决：整数坐标统一long long，浮点坐标比较写一个dcmp：int dcmp(double x) { return fabs(x) < eps ? 0 : (x > 0 ? 1 : -1); }，所有== 0都换成dcmp(...) == 0。eps 取 1e-9，别取 1e-6，后者在坐标值很大的题目里误差会被放大。如果题目要求输出浮点结果，保留位数的同时多留几位中间精度，不要提前四舍五入。

5.5 读入太慢被卡常：2e5 数据量就吃紧

现象：cin >> n读 2e5 个整数直接 TLE，换成scanf勉强过，再大一点又卡。

原因：C++ 的 iostream 和 C 标准 IO 同步导致性能下降，加上cin默认绑定cout，每次输出都要刷新缓冲区。

解决：主函数开头写ios::sync_with_stdio(false); cin.tie(nullptr);，能把cin速度拉到接近scanf。还不够就用简单快读：

int read() { int x = 0, f = 1; char 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; }

快读里f用来记录负数，没有负数的题可以省略。再往上走还有fread批量读的版本，但那属于最后的大招，能把读入压到接近内存带宽，一般比赛用不上。还有一点：刷题平台有时会有特殊交互式题目，这种情况快读和快写要小心使用，避免吞掉不该吞的字符。

6. 把模板变成工具：调试宏、对拍脚本与题目日志

模板不是八股文，背得再熟也要有验证手段。我维护模板库的最后一步，是给每个算法配一套「调试 + 验证」的小工具，这里分享两个最实用的。

第一个是本地调试宏。比赛时提交代码不能带cerr输出，但本地调错又离不开打印中间值，用宏控制是标准做法：

#ifdef LOCAL #define dbg(x) cerr << #x << " = " << x << "\n" #else #define dbg(x) #endif

编译时加-DLOCAL就输出调试信息，去掉就自动消失，不会忘删。第二种是数据验证的兜底手段，也是比赛经验里最重要的一个习惯——不要只测样例。样例是出题人给的，往往跑通就让你产生「这题我会」的错觉。我会准备三组额外测试：边界数据（n 取 1 或最大值）、极端数据（所有值相同）、随机大数（用脚本生成）。

生成大数测试要配一个简单脚本，这比手写数据快得多：

#!/bin/bash for ((i=1; i<=100; i++)); do python3 gen.py > in.txt ./std < in.txt > out_std.txt ./wa < in.txt > out_wa.txt if ! diff -q out_std.txt out_wa.txt > /dev/null; then echo "Wrong at case $i" break fi done

gen.py负责按题目范围生成随机输入，std是你信任的正确程序（或者是暴力写法），wa是待验证的优化写法。这套流程能发现八九成的隐蔽 bug，比反复看代码有效得多。

模板库本身也要维护，我习惯在每个模板文件头部写三行注释：适用条件、复杂度、踩过的坑。比如 Dijkstra 那篇写「仅限非负权图，2e5 规模 O(M log M)，INF 用 4e18，勿加 vis」，等再遇到这题就能直接定位问题。我印象最深的一次教训，是把一个带vis的 Dijkstra 模板原样抄进代码，小数据测试全过，提交反复 WA 了三次才想起注释里写过「勿加 vis」。从那以后，每条模板的坑都写在文件最上面，短小但保命。希望帮到你。

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