简介面向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; vectorpairint, 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}); }vectorpairint,int的写法在大多数在线评测系统上完全够用代码短、调试方便、遍历时直接拿auto [v, w]拆包。它的代价是内存不连续极端密集图上访问速度稍慢但竞赛中 2e5 级别边的场景很少被这点差距卡掉。链式前向星用数组模拟链表内存连续、常数更小缺点是插入顺序是逆序的代码也长一截。我一般建议平时练习和多数比赛用vector版本只有遇到老牌题库那种卡常严重的题目才临时切前向星。建图这步最容易翻车的不是选型而是忘记开N的上限。N开小了越界写入会静默污染相邻内存表现是「本地跑得好好的交上去随机 WA」。我的习惯是N直接开到题目上限加 5多出来的几个位置不心疼。2.2 堆优化 DijkstraINF 与过期出堆单源最短路里堆优化 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_queuepairll, int, vectorpairll, int, greaterpairll, 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; }; vectorEdge 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)代码还更短。vectorint a; vectorint 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 背包的滚动数组写法几乎每场比赛都会用到。它的核心就一个词倒序。vectorint 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; vectorlong long sum(n 1, 0); for (int i 1; i n; i) sum[i] sum[i - 1] a[i]; vectorvectorlong long dp(n 1, vectorlong 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(...)) epseps 通常取 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; } vectorPoint convexHull(vectorPoint pts) { sort(pts.begin(), pts.end(), cmp); vectorPoint 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的朴素试除快约三倍。批量判断就不该逐个数试除了用欧拉筛vectorint 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浮点坐标比较写一个dcmpint 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 ((i1; i100; 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 donegen.py负责按题目范围生成随机输入std是你信任的正确程序或者是暴力写法wa是待验证的优化写法。这套流程能发现八九成的隐蔽 bug比反复看代码有效得多。模板库本身也要维护我习惯在每个模板文件头部写三行注释适用条件、复杂度、踩过的坑。比如 Dijkstra 那篇写「仅限非负权图2e5 规模 O(M log M)INF 用 4e18勿加 vis」等再遇到这题就能直接定位问题。我印象最深的一次教训是把一个带vis的 Dijkstra 模板原样抄进代码小数据测试全过提交反复 WA 了三次才想起注释里写过「勿加 vis」。从那以后每条模板的坑都写在文件最上面短小但保命。希望帮到你。本文还有配套的精品资源点击获取