简介一套服务于ACM-ICPC等程序设计竞赛的C算法模板库按主题拆分为头文件模板、数学、字符串、数据结构、图论、计算几何、动态规划七大模块涵盖快速幂、Dijkstra、KMP、线段树、凸包、LCS等高频算法实现适合赛前速刷、日常训练与教学参考。压缩包共83个文件主体为65个cpp源码另含4个tex文档、3个Python脚本、1个PDF速查手册及Makefile、LICENSE等工程配套整体449KB体积轻量、目录规整。附带CheatSheet.pdf/tex既可直接查阅也可通过LaTeX重新编译生成个人速查手册Python脚本与Makefile辅助本地测试与配置LICENSE与.gitignore保障开源合规与版本管理。目前已有29人浏览学习对希望系统整理竞赛算法模板的选手而言这是一份轻量而实用的代码库。1. C竞赛常用算法模板合集从图论到计算几何的速查式代码库每次赛后复盘时最影响心态的往往不是思维卡壳而是手写基础模板时的小差错某个初始化漏了、某个边界写错一调试就是二十分钟。这份C竞赛常用算法模板合集本质就是把图论、动态规划、计算几何这些考频最高的模块压成可以快速复制进自己代码库的“基础件”。它更适合那些算法思路已经入门、但想减少编码事故率的备赛者也适合日常写题量大、需要统一代码风格的人。模板不能替代对算法的理解但能帮你把精力留给真正需要思考的环节。2. 图论模块最短路、拓扑排序与最小生成树的竞赛化写法2.1 先选对算法再动手图论模板的适用边界图论题的坑很少在编码本身而在选型。同样是求最短路边权非负且点数大时用 Dijkstra 堆优化边权有负数时得换 SPFA 或 Bellman-Ford稠密图求最小生成树用 Prim 更顺手稀疏图反而 Kruskal 更直观。模板本省本身不是万能的套之前先问自己三个问题有向还是无向边权是否有负数点数和边数的量级分别是多少这三个答案基本决定了该打开哪个模板文件。场景推荐模板复杂度非负权最短路Dijkstra堆优化O((nm)log n)负权边/负环判定SPFA / Bellman-FordO(nm)稠密图最小生成树PrimO(n^2) 或堆优化稀疏图最小生成树KruskalO(m log m)我一般会在比赛前把这几份模板都准备好但默认优先使用 Dijkstra 和 Kruskal因为它们对数据规模的适应性更强出错概率也低。2.2 Dijkstra 堆优化邻接表 优先队列的完整实现// 适用范围单源最短路边权均为非负数 // 复杂度O((nm)log n)n 为点数m 为边数 struct Edge { int to; long long w; }; vectorEdge graph[MAXN]; long long dist[MAXN]; const long long INF 4e18; void dijkstra(int start, int n) { for(int i 1; i n; i) dist[i] INF; dist[start] 0; // 小顶堆pair当前距离, 节点编号 // 把距离放第一位堆顶始终是未处理节点中距离最小的 priority_queuepairlong long, int, vectorpairlong long, int, greaterpairlong long, int pq; pq.push({0, start}); while(!pq.empty()) { auto [curDis, u] pq.top(); pq.pop(); // 懒删除如果当前距离比已知距离大说明堆里的旧记录 if(curDis dist[u]) continue; for(const Edge e : graph[u]) { long long nd curDis e.w; if(nd dist[e.to]) { dist[e.to] nd; pq.push({nd, e.to}); } } } }这段模板有三个细节值得说明。第一用pairlong long, int而不用自定义结构体是为了省去重载运算符的麻烦greater让堆顶是最小距离。第二curDis dist[u]这个懒删除判断不是可有可无没有它同一个节点可能被重复弹出和更新最坏情况下复杂度退化。第三数组graph和dist的初始化位置很关键多组测试数据时如果忘记在每组数据开头清空邻接表会出现上一组残留边污染下一组结果的问题。遇到这类情况我通常把整个graph[i]用clear()清理干净再重新建图。这个模板只适用于边权非负。一旦出现负权边Dijkstra 的贪心前提被破坏正确解法是 Bellman-Ford 或 SPFA不少选手在这里翻车认为堆优化能兼容负数场景实际是错的。2.3 拓扑排序判断有环并输出合法顺序拓扑排序常用于任务调度、依赖关系分析以及检测有向图中是否存在环。// n 为点数g 为邻接表in 记录每个节点的入度 vectorint g[MAXN]; int in[MAXN]; vectorint topoSort(int n) { vectorint order; queueint q; // 先把所有入度为 0 的点入队 for(int i 1; i n; i) { if (in[i] 0) q.push(i); } while(!q.empty()) { int u q.front(); q.pop(); order.push_back(u); for(int v : g[u]) { in[v]--; if(in[v] 0) { q.push(v); } } } // 如果最终输出节点数少于 n说明图中有环 if((int)order.size() ! n) { // 根据题目要求返回空或标记有环 return {}; } return order; }这里需要特别留意入度数组的维护。建图时每加一条边u - v都要执行in[v]否则队列初始化为空排序结果为空。还有一个不是所有人都能第一时间反应过来的细节如果题目要求输出字典序最小的拓扑序列把queue换成priority_queueint, vectorint, greaterint即可这个改动在部分竞赛题里直接影响得分。2.4 Kruskal 最小生成树并查集版模板// 适用范围稀疏图求最小生成树 // 复杂度O(m log m)瓶颈在于按边权排序 struct Edge { int u, v; long long w; }; int father[MAXN]; int find(int x) { // 路径压缩把沿途节点直接挂到根上 return father[x] x ? x : father[x] find(father[x]); } long long kruskal(int n, vectorEdge edges) { sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { return a.w b.w; }); for(int i 1; i n; i) father[i] i; long long ans 0; int cnt 0; // 已加入生成树的边数 for(const Edge e : edges) { int ru find(e.u); int rv find(e.v); if(ru rv) continue; // 两端已连通再加就成环 father[ru] rv; ans e.w; cnt; if(cnt n - 1) break; // n 个点连通需要恰好 n-1 条边 } // 如果循环结束后边数不足 n-1说明原图不连通 return cnt n - 1 ? ans : -1; }并查集初始化是这里最容易被忽略的一步。有时候题目点的编号从 0 开始有时候从 1 开始写模板时如果用for(int i 0; i n; i)那么father[n]就是未初始化的脏数据并查集瞬间变成环检测的黑匣子。我的习惯是在函数内部统一按1..n初始化然后根据题目数据范围调整循环边界。Kruskal 的好处在于它不需要建邻接表只要把边收集起来排序即可这在输入边集时尤其省事。如果遇到稠密图Prim 的O(n^2)写法其实更稳定不需要额外排序不过这类模板通常要配合邻接矩阵或者堆优化来写使用场景相对窄一些。3. 动态规划模块从线性 DP 到区间 DP 的状态设计套路3.1 状态定义先于转移方程选型决定的复杂度边界DP 题的难点往往不是代码而是状态定义。同一个问题定义dp[i]和定义dp[i][j]对应的复杂度完全不同。我写 DP 前会先把状态、转移、初始化三件事写在一行注释里避免写了一半脑子混乱。最长上升子序列是线性 DP 里很有代表性的模板。// 求 a[0..n-1] 的最长上升子序列长度 // 贪心 二分复杂度 O(n log n) vectorint lis; for(int x : a) { // lower_bound 找第一个 x 的位置 auto it lower_bound(lis.begin(), lis.end(), x); if(it lis.end()) { lis.push_back(x); } else { *it x; } } // 答案lis.size()这段代码初看会有一个不小的疑问lis里的元素并不是真实的上升子序列为什么长度仍然正确原因是它维护的是“当前长度下最小的末尾值”这个末尾值越小后续接上更长的序列可能性就越大。比如序列[2, 5, 3, 4]前两步lis为[2, 5]遇到 3 时把 5 替换成 3得到[2, 3]之后接 4 变成[2, 3, 4]。如果不替换5 会在那里挡住 4 的插入。理解了这一点就不会把lis和结果序列混淆。lower_bound要求lis本身有序而经过贪心维护后它始终是升序的。3.2 区间 DP合并类问题的循环顺序与边界处理区间 DP 的经典场景是合并石子、矩阵链乘、括号匹配。这类问题的模板特征很明显状态是dp[i][j]表示闭区间[i, j]上的最优值转移时枚举分割点k。// 求合并 n 堆石子的最小代价 // dp[i][j] 表示把第 i 堆到第 j 堆合并成一堆的最小代价 // sum[i] 表示前 i 堆石子的前缀和 const int INF 1e9; int dp[MAXN][MAXN], sum[MAXN]; for(int i 1; i n; i) dp[i][i] 0; // 只有一堆时无需合并 // len 表示当前区间长度从小往大算 for(int len 2; len n; len) { for(int i 1; i len - 1 n; i) { int j i len - 1; dp[i][j] INF; for(int k i; k j; k) { // 左半 [i,k] 右半 [k1,j] // 合并代价是两堆石子数量之和即 sum[j] - sum[i-1] dp[i][j] min(dp[i][j], dp[i][k] dp[k1][j] sum[j] - sum[i-1]); } } } // 答案dp[1][n]这个模板的循环顺序是无数人踩过坑的地方。如果外层换成枚举i、内层枚举j那么计算dp[i][j]时可能依赖的dp[k1][j]还没被求出来得到的结果就是错的。所以必须先枚举区间长度len保证计算长区间时所需的短区间已经算完。前缀和sum[j] - sum[i-1]用于计算区间总代价这个写法比循环累加快得多也减少出错面。如果石子围成一圈处理方法是把数组复制一份接在后面然后枚举长度为 n 的区间。这个扩展只需要在数组长度上动手转移方程不用改。3.3 剪枝、滚动数组与单调队列常用优化的落点不同DP 优化常见的三个方向经常被混在一起。滚动数组解决的是空间问题剪枝解决的是搜索树的扩展问题单调队列解决的是决策集合的滑动问题。它们的落点完全不同不该在一个场景混用。单调队列优化滑动窗口最值的代码骨架// 求每个长度为 k 的窗口中的最大值 // dq 里存的是下标保证下标对应值单调递减 dequeint dq; for(int i 1; i n; i) { // 新元素入队前把队尾比它小的元素淘汰 // 因为它们不可能是当前和后续窗口的最大值 while(!dq.empty() a[dq.back()] a[i]) { dq.pop_back(); } dq.push_back(i); // 队头如果滑出窗口淘汰 while(!dq.empty() i - dq.front() k) { dq.pop_front(); } if(i k) { ans[i] a[dq.front()]; } }单调队列优化的关键是每个元素只进出队列一次整体复杂度 O(n)。如果你在某些 DP 题里看到dp[i] max(dp[j]) cost且j落在一个滑动区间内就可以考虑用这个模板优化。剪枝则更多用于记忆化搜索场景常见做法是提前按值排序先搜可能性大的分支。排序后剪枝效率往往比随机顺序高很多这一点在部分搜索题里决定了超不超时。4. 计算几何模块点、向量与凸包的整套基础件4.1 点和向量结构体把 eps 和大数比较做对计算几何代码出错的第一大来源是浮点比较。直接用判断两个 double 是否相等会在共线、共点这类边界数据上翻车。工程化的做法是引入极小量eps所有比较都改成容差范围。const double eps 1e-8; struct Pt { double x, y; Pt operator - (const Pt p) const { return {x - p.x, y - p.y}; } // 叉积返回有向面积的两倍 double cross(const Pt p) const { return x * p.y - y * p.x; } // 点积 double dot(const Pt p) const { return x * p.x y * p.y; } bool operator (const Pt p) const { // x 不同时按 x 排否则按 y 排 if(fabs(x - p.x) eps) return x p.x; return y p.y; } bool operator (const Pt p) const { return fabs(x - p.x) eps fabs(y - p.y) eps; } };注意cross的正负决定了转向a.cross(b) 0表示 b 在 a 的逆时针方向小于 0 是顺时针方向等于 0 表示共线。这个性质是后面所有凸包和线段相交判断的基础。eps 的取值通常是 1e-8 到 1e-10太大会误判接近但不等的点太小又起不到容差作用。4.2 Graham 扫描凸包一条完整实现// 输入点集输出按逆时针顺序排列的凸包顶点 // 使用 会去除共线点如果题目要求保留共线点把 改成 vectorPt convexHull(vectorPt pts) { int n pts.size(); if(n 1) return pts; sort(pts.begin(), pts.end()); vectorPt hull(2 * n); int k 0; // 构建下凸壳从左到右扫描 for(int i 0; i n; i) { while(k 2 (hull[k-1] - hull[k-2]).cross(pts[i] - hull[k-1]) 0) { k--; } hull[k] pts[i]; } // 构建上凸壳从右到左扫描注意跳过最后一个点 for(int i n - 2, t k 1; i 0; i--) { while(k t (hull[k-1] - hull[k-2]).cross(pts[i] - hull[k-1]) 0) { k--; } hull[k] pts[i]; } // 首尾点重复去掉最后一个重复点 hull.resize(k - 1); return hull; }这个模板的实现思路基于排序后的点集天然有序。先从左往右扫出下半部分再从右往左扫出上半部分每次判断用叉积符号当新加入的点让当前端点发生“右转”或直走时说明该端点不可能出现在凸包上弹出即可。 0表示把共线点剔除最终凸包顶点都是严格拐角的点。如果题目要求凸包周长最小且允许共线点在边上改成 0即可这个改动属于高频需求。4.3 线段相交与多边形面积判定的代码化线段相交用跨立实验判断核心是看两条线段是否互相“跨过”对方。// 判断点 p 是否在线段 ab 上含端点 bool onSegment(Pt a, Pt b, Pt p) { if(fabs((b - a).cross(p - a)) eps) return false; return min(a.x, b.x) - eps p.x p.x max(a.x, b.x) eps min(a.y, b.y) - eps p.y p.y max(a.y, b.y) eps; } // 判断线段 ab 与 cd 是否相交含端点和重合 bool segmentIntersect(Pt a, Pt b, Pt c, Pt d) { double d1 (b - a).cross(c - a); double d2 (b - a).cross(d - a); double d3 (d - c).cross(a - c); double d4 (d - c).cross(b - c); // 规范相交两端点分别位于另一线段两侧 if(((d1 eps d2 -eps) || (d1 -eps d2 eps)) ((d3 eps d4 -eps) || (d3 -eps d4 eps))) { return true; } // 非规范相交端点在另一条线段上也算相交 return onSegment(a, b, c) || onSegment(a, b, d) || onSegment(c, d, a) || onSegment(c, d, b); }注意d1和d2恰好为 0 的情况那表示端点共线需要靠onSegment中的范围判断兜住。如果你发现某些相交测试漏掉端点重合的情况多半是少了最后那个onSegment兜底。多边形面积用鞋带公式实现起来最稳double polygonArea(const vectorPt poly) { double area 0; int n poly.size(); for(int i 0; i n; i) { int j (i 1) % n; area poly[i].x * poly[j].y - poly[j].x * poly[i].y; } return fabs(area) / 2; }这个公式对凸多边形和凹多边形都适用只要点按顺序排列即可。fabs保证面积为正因为顶点顺时针或逆时针顺序会影响求和结果的符号。5. 基础模板与避坑排查快读、离散化与五个实战雷区5.1 快读和离散化把输入输出和值域压缩到安全范围竞赛里数据量一大cin即使关掉同步也可能不够快标准做法是手写快读。同时很多题的值域远大于数据量离散化可以把稀疏的大范围数值压缩成连续编号方便做下标索引。// 通用快读支持负数 inline int read() { int x 0, sign 1; char c getchar(); while(c 0 || c 9) { if(c -) sign -1; c getchar(); } while(c 0 c 9) { x x * 10 (c - 0); c getchar(); } return x * sign; }这段代码的核心在于先用循环跳过非数字字符再逐位累加。如果不处理负号部分数据会整个读崩。离散化的三件套也很固定vectorint all; // 收集所有可能用到的原始值 // ... 把所有候选值 push 进 all ... sort(all.begin(), all.end()); all.erase(unique(all.begin(), all.end()), all.end()); // 之后查询某个值 v 的离散化编号 int id lower_bound(all.begin(), all.end(), v) - all.begin() 1;unique去重后lower_bound返回第一个不小于 v 的位置加 1 是为了让编号从 1 开始方便前缀和等操作从idx 1起步。5.2 编译与 STL 配置比赛环境下的常用设置#include bits/stdc.h using namespace std;这句万能头文件和using namespace std在正式项目中会被吐槽但竞赛场景确实是标准操作能省去大量 include 时间。编译时建议固定使用-O2 -stdc17注意不要开-O0否则 STL 容器性能会差很多。如果确实要用cin在main开头加这两行ios::sync_with_stdio(false); cin.tie(0);5.3 避坑实践五个真实踩坑记录下面五条来自实际调试经历每一条都花了不止十分钟定位。现象 1区间 DP 程序运行结果偶发不对数据大时数组越界。原因写循环时用for(int i 1; i len n; i)导致j i len - 1在边界越界且内层访问到未初始化的dp值。 解决记住i len - 1 n才是合法右端点测试n1和n2两个最小规模数据能覆盖大部分边界错误。现象 2Dijkstra 跑出来的最短路径偏大但样例全过。原因dist数组初始化放在多组数据的循环外面第二组测试时上次的较小值残留部分节点更新不了。 解决每组数据开始前把dist[1..n]全部重设为INF并把graph数组clear()。写完模板后我通常会在 while 循环头部加一个固定的 reset 段。现象 3计算几何题在共线数据上 WA其他情况都正常。原因叉积结果等于 0 的共线情况没有经过eps容差处理 0在浮点误差下失效。 解决所有几何比较统一用fabs(v) eps代替v 0。这个坑最容易出现在凸包与线段相交判断中。现象 4快读在输入末尾多读了一个 EOF 或负数读错。原因跳过非数字字符时把-当成普通字符跳过了或者没有在 EOF 处停止。 解决第一层 while 里单独判断-并设置 sign 标记遇到c EOF时直接返回当前值避免继续读入野数据。现象 5拓扑排序结果比预期短且无环时也返回空。原因in数组没有在每组数据开头清零旧入度残留让初始入队条件失效。 解决建图前对in[1..n]统一赋零并在加边时从0计数。这个坑在多组测试题里最常见。6. 进阶验证把模板压成比赛前十分钟的个人清单模板本身的价值在于关键时刻拿起来就能用所以我在比赛前对自己的要求只有一条所有模板都跑过对拍并且边界数据单独测过。如果条件允许我建议你把核心模板做一次随机对拍。思路是写一个暴力解法作为慢速基准再写一个随机数据生成器然后用脚本循环对比两份程序输出。这份 bash 脚本我经常在比赛前跑一遍#!/bin/bash for i in $(seq 1 1000); do ./gen in.txt ./slow in.txt slow_out.txt ./fast in.txt fast_out.txt if ! diff -q slow_out.txt fast_out.txt /dev/null; then echo case $i failed break fi done echo all cases passedgen是数据生成器slow是暴力版fast是模板版。随机数据能覆盖大多数隐蔽边界尤其适合验证像区间 DP、凸包这些容易在细节出错的模板。diff对比一旦发现不一致立刻用失败用例定位。把模板套到题目里之前我会再多测三组针对性数据n1、图不连通、所有点共线。这三组数据分别对应图论、DP、几何模板最常见的崩溃场景。模板集的最终形态应该是你自己的版本。我会在每份模板开头写清“适用范围、复杂度、需要初始化的变量名”比如 Dijkstra 前先检查dist是否重置、并查集前先确认father范围覆盖所有编号。之前有一次在区域赛模拟题上我直接套用了凸包模板但没注意输出格式要求逆时针白改了半天。从那以后我每次比赛前都强制把所有模板按“输入格式、初始化、输出格式”三个维度走一遍自查。希望这份模板合集也能帮你省下那些不该花在基础代码上的时间把精力留给真正拉开差距的算法思路。希望帮到你。本文还有配套的精品资源点击获取