简介面向ACM-ICPC等程序设计竞赛的C模板合辑聚焦图论、动态规划、计算几何等高频考点按头文件模板、数学、字符串、数据结构、图论、计算几何、动态规划七大模块分类收纳快速幂、Dijkstra、KMP、线段树、凸包、LCS等可直接使用的核心代码既适合赛前集中速刷也可用于日常算法训练与教学示例。压缩包共83个文件整体约449KB主体是65个cpp源码文件另含LaTeX相关文件与PDF速查手册、Python辅助测试脚本、Makefile构建脚本、开源许可证等便于本地编译、查阅和二次整理。技术文档与代码分离CheatSheet可自行生成速查页src目录下各模块结构鲜明、注释规范降低检索成本。页面已有29人浏览学习对希望建立个人算法模板库的竞赛选手而言是一份轻量但覆盖较全的实用性资源按主题查阅即可快速定位图论、DP或几何模板。1. C竞赛常用算法模板合集先想清楚自己在攒什么很多打算法竞赛的朋友都存过一份“C常用算法模板”但真正到了赛场上能直接抄起来就用的往往不是网上整段整段的题解代码而是你自己整理过、注释过、验证过的一批核心模块。这个合集要解决的不是“有没有模板”而是“模板到了关键时刻能不能信得过”——图论里最短路怎么写不会爆栈动态规划里状态定义怎么不写歪计算几何里凸包排序的极角序怎么不出精度问题。这篇文章不会给你一份打包下载的文件而是把一个可复现的模板库拆开每类模块存什么、参数怎么调、哪些地方最容易翻车以及我踩过的几个血泪坑。适合想系统整理自己模板库的选手也适合刚入门、想从“抄代码”过渡到“用代码”的人。2. 基础数学模板快速幂、素数筛与 IO 加速三板斧2.1 快速幂与矩阵快速幂从 a^b 到斐波那契快速幂是整套模板库里出现频率最高的模块因为几乎所有取模运算场景都会用到它。它的核心思路是把指数拆成二进制用倍增替代循环乘法把 O(b) 降到 O(log b)。平时我用得最多的版本是带取模的模数不固定时建议把 mod 作为参数传进去而不是写成全局变量这样换题时不用改函数体。// 快速幂计算 (base^exp) % mod long long qpow(long long base, long long exp, long long mod) { long long res 1 % mod; base % mod; // 先取模防止后面乘法溢出 while (exp 0) { if (exp 1) res res * base % mod; // 当前位为1时乘入结果 base base * base % mod; // 底数自身平方 exp 1; // 指数右移一位 } return res; }逻辑在于每次对指数右移判断二进制末位是否为 1是则累乘当前底数。底数每次都平方对应二进制位权倍增。参数上要留意三点一是res初始值写成1 % mod可以兼容 mod1 的边界二是所有乘法都要紧跟% mod中间变量必须用 long long否则两数相乘直接溢出 int三是如果指数很大且底数是负数先把base % mod转成正的再运算。矩阵快速幂是同一思想的延伸常见于斐波那契数列、线性递推加速。模板上只需要重载矩阵乘法再复用同样的二进制拆分逻辑。我习惯把矩阵封装成一个结构体矩阵乘法三个循环嵌套时注意内层累加用 long long最后统一取模。struct Mat { long long m[2][2]; Mat(bool unit false) { memset(m, 0, sizeof(m)); if (unit) m[0][0]m[1][1]1; } }; Mat mul(const Mat a, const Mat b, long long mod) { Mat c; for (int i 0; i 2; i) for (int k 0; k 2; k) if (a.m[i][k]) for (int j 0; j 2; j) c.m[i][j] (c.m[i][j] a.m[i][k] * b.m[k][j]) % mod; return c; }这里乘法的循环顺序我刻意调成了 i-k-j先判断a.m[i][k]是否为零能跳过不少无效计算。矩阵尺寸固定为 2 是因为斐波那契递推矩阵是 2x2如果题目给的递推阶数更高把数组开成 N x N 并把循环上界改成变量即可。2.2 素数筛的两个版本埃氏筛与线性筛判断质数这个动作在竞赛题里从来不是单独出现而是内嵌在质因数分解、欧拉函数、数论分块等场景里。单点判断质数用试除法就够O(sqrt(n)) 的写法里注意循环到 sqrt 即可但如果是区间筛、预处理一批质数就要用筛法。埃氏筛代码短、易理解处理 1e6 级别的范围完全够用。// 埃氏筛筛出 1..n 的所有质数isPrime[i]true 表示 i 为质数 void sieve_eratosthenes(int n, vectorbool isPrime, vectorint primes) { isPrime.assign(n 1, true); isPrime[0] isPrime[1] false; for (int i 2; i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) // 从 i*i 开始避免重复标记 isPrime[j] false; } } primes.clear(); for (int i 2; i n; i) if (isPrime[i]) primes.push_back(i); }埃氏筛的优化点是从i*i开始标记因为小于i*i的合数一定被更小的质因子标记过了。如果追求更严格的线性复杂度可以写欧拉筛每个合数只被它的最小质因子筛掉一次。差别在 1e7 以上数据量时才明显普通竞赛 1e6 级别两者时间差可以忽略我一般先写埃氏筛毕竟它不容易写错。欧拉筛的维护要点是i % primes[j] 0时跳出这一步保证了最小质因子唯一性。参数上需要额外注意primes数组会随 n 增大而变长函数外部的 vector 用引用传入避免反复拷贝的开销。// 欧拉筛线性复杂度每个合数仅被最小质因子筛一次 void sieve_linear(int n, vectorint primes, vectorint minPrime) { minPrime.assign(n 1, 0); primes.clear(); for (int i 2; i n; i) { if (minPrime[i] 0) { // i 是质数 minPrime[i] i; primes.push_back(i); } for (int j 0; j (int)primes.size() primes[j] minPrime[i] i * primes[j] n; j) { minPrime[i * primes[j]] primes[j]; if (i % primes[j] 0) break; // 保证每个合数只被最小质因子记录 } } }2.3 快读与关闭同步别让 cin 成为 TLE 元凶这道题明明算法复杂度没问题却超时最后发现是输入太慢——这个场景在竞赛里太常见了。默认的 cin/cout 因为要和 C 标准 IO 同步会做大量额外操作。竞赛环境下ios::sync_with_stdio(false)加上cin.tie(nullptr)能解决大部分输入瓶颈但如果输入数据超过百万行级别的整数我建议直接上 fread 快读模板。// 基于 fread 的整数快读 char buf[1 20]; int idx 0, len 0; inline char getChar() { if (idx len) { len fread(buf, 1, sizeof(buf), stdin); idx 0; } return len ? buf[idx] : EOF; } inline int readInt() { 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; }模板里readInt返回值是 int如果题目数值范围到 1e18 就把类型改成 long long。缓冲区大小 120 也就是 1MB对常见数据量足够。注意这个模板不支持浮点数需要读 double 的题建议输入流直接走 cin 或 scanf不要自己手写浮点解析容易踩边界。输出端同理可以用putchar封装一个快速输出但相比之下输出瓶颈出现频率低很多先保证输入快读到位。2.4 二分边界写对 l 与 r 的三件套二分看起来简单实际翻车率奇高尤其出题人喜欢卡边界。我在模板库里固定存三套二分找第一个满足条件的下标、找最后一个满足条件的下标、实数二分。三套都遵循同样的不变量约定避免临场现推。// 找第一个 target 的位置不存在返回 n int lower_bound_arr(const vectorint a, int target) { int l 0, r (int)a.size(); // 左闭右开区间 [l, r) while (l r) { int mid (l r) 1; if (a[mid] target) r mid; // mid 满足条件向左收 else l mid 1; // mid 不满足向右逼 } return l; }这套左闭右开写法的好处是返回下标天然兼容end()语义r初始化为 n 而不是 n-1当所有元素都小于 target 时返回 n 也不会越界。实数二分则要多加一个迭代次数控制而不是比较 eps因为浮点误差在不同量级下表现不稳定固定跑 60 次二分最稳。// 实数二分求单调函数 f(x) 的零点固定迭代 100 次 double binary_search_real(double l, double r, const functiondouble(double) f) { for (int i 0; i 100; i) { double mid (l r) / 2.0; if (f(mid) 0) r mid; else l mid; } return (l r) / 2.0; }3. 图论模板存图方式、最短路、并查集与网络流的取舍3.1 存图选型vector 邻接表与链式前向星图论题的起点是存图。竞赛里最常用的两种vector 邻接表和链式前向星。vector 邻接表写法直观适合绝大多数题目链式前向星则内存连续、遍历速度快且在某些需要按输入顺序遍历边、或者要反向修改边权的场景典型如网络流的反向边里更顺手。我用链式前向星的一个原因在于网络流的反向边通过异或i ^ 1访问实现简洁且不容易错。struct Edge { int to, next; long long w; }; vectorEdge edges; vectorint head; void initGraph(int n) { head.assign(n 1, -1); edges.clear(); } void addEdge(int u, int v, long long w) { edges.push_back({v, head[u], w}); // 新边插到链表头部 head[u] (int)edges.size() - 1; }next指向同一起点的上一条边在edges数组中的下标head[u]存的是最新一条边的下标。遍历以 u 为起点的所有边时从head[u]开始顺着next走。参数方面注意edges数组容量要预留2 * 边数因为无向图每条边要 add 两次有向图只要边数次。如果题目边数很大先edges.reserve()预分配避免 vector 扩容造成地址变动。3.2 最短路Dijkstra 堆优化与 SPFA 的判断Dijkstra 堆优化是单源最短路的首选前提是所有边权非负。它的复杂度 O((VE)logV)在 1e5 级别的图上可以轻松跑完。模板里我固定用优先队列因为手写堆虽然常数小但竞赛中优先队列的正确率更高优先队列里的 pair 先按距离再按节点排序注意默认是大顶堆要传入greaterpairlong long,int使其变为小顶堆。// Dijkstra 堆优化dist 初始化为 INF从 src 出发 vectorlong long dijkstra(int n, const vectorvectorpairint,long long g, int src) { const long long INF 4e18; vectorlong long dist(n 1, INF); priority_queuepairlong long,int, vectorpairlong long,int, greater pq; dist[src] 0; pq.push({0, src}); 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}); } } } return dist; }这里有个细节很多模板喜欢用if (d dist[u]) continue;我用的是d ! dist[u]因为在溢出风险受控时完全相等才说明这是最新入堆的距离不等则直接跳过。其实两种写法均可重点在于必须判重否则复杂度会退化。SPFA 我平时不主动用只在检测负环时才写。负环检测的思路是记录每个节点入队次数超过 n 次即存在负环因为最短路径包含环时不会超过 n-1 条边。这个写法在随机图上跑得快但构造数据很容易卡死没有负权边时一律 Dijkstra这点要记住。// SPFA 检测负环返回 true 表示存在负环 bool spfa_negative_cycle(int n, const vectorvectorpairint,long long g) { vectorlong long dist(n 1, 0); vectorint inq(n 1, 0), cnt(n 1, 0); queueint q; for (int i 1; i n; i) { q.push(i); inq[i] 1; } while (!q.empty()) { int u q.front(); q.pop(); inq[u] 0; for (auto [v, w] : g[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inq[v]) { q.push(v); inq[v] 1; if (cnt[v] n) return true; } } } } return false; }3.3 并查集路径压缩与按秩合并的组合并查集在竞赛里更多是作为工具型模块嵌入其他算法最小生成树 Kruskal、离线处理连通性问题。单独看代码非常简单但参数选择有讲究路径压缩能摊平查找按秩合并能控制树高。两者合用时复杂度接近反阿克曼函数这是理论上的最优形态而只做路径压缩不按秩合并在极端数据下仍有退化风险。struct DSU { vectorint parent, rnk; DSU(int n) { parent.resize(n 1); rnk.assign(n 1, 0); for (int i1; in; i) parent[i]i; } int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } void unite(int a, int b) { a find(a); b find(b); if (a b) return; if (rnk[a] rnk[b]) swap(a, b); parent[b] a; if (rnk[a] rnk[b]) rnk[a]; } };find里的路径压缩写成了尾递归编译器通常能优化掉额外栈开销但如果数据量到 1e6 以上且树深比较极端可以考虑写成非递归版本。unite的思路是把较矮的树挂到较高的树上rnk只在两棵树高度相等时才加一。这道模板我建议直接存结构体而不是散装函数因为竞赛题里并查集常需要多开几组实例结构体天然支持多个对象。3.4 Dinic 最大流一个够用的模板网络流模板是图论里最长的一块也是争议最多的——有人用 ISAP有人用 HLPP但 Dinic 在 95% 的竞赛题里够用。它的核心是 BFS 分层图 DFS 多路增广每次 BFS 后找最短增广路直到无法继续分层。模板里两个关键优化当前弧优化cur数组记住每条边被用到了哪里和反向边通过异或访问。struct Dinic { struct Edge { int to, next; long long cap; }; vectorint head, level, cur; vectorEdge edges; int n; Dinic(int n_): n(n_) { head.assign(n1, -1); edges.clear(); } void addEdge(int u, int v, long long cap) { edges.push_back({v, head[u], cap}); head[u] (int)edges.size() - 1; edges.push_back({u, head[v], 0}); // 反向边容量 0 head[v] (int)edges.size() - 1; } bool bfs(int s, int t) { level.assign(n1, -1); queueint q; q.push(s); level[s] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int i head[u]; i ! -1; i edges[i].next) { Edge e edges[i]; if (e.cap 0 level[e.to] -1) { level[e.to] level[u] 1; q.push(e.to); } } } return level[t] ! -1; } long long dfs(int u, int t, long long flow) { if (u t) return flow; for (int i cur[u]; i ! -1; i edges[i].next) { Edge e edges[i]; if (e.cap 0 level[e.to] level[u] 1) { long long ret dfs(e.to, t, min(flow, e.cap)); if (ret) { e.cap - ret; edges[i ^ 1].cap ret; return ret; } } } return 0; } long long maxflow(int s, int t) { long long ans 0; while (bfs(s, t)) { cur head; // 每次 BFS 后重置当前弧 while (long long f dfs(s, t, 4e18)) ans f; } return ans; } };用 Dinic 时有个约定addEdge成对添加边正向边和反向边在edges数组里下标必须相邻这样i ^ 1才能取到反向边。反向边初始容量为 0增广后加上实际流量。参数上flow递归传入时会变小所以 dfs 出口返回的是实际增广的流量单次 dfs 可能只有一条路径的增量外部 while 循环反复调用直到本次分层图的流量耗尽。4. 动态规划模板背包、LIS 与区间 DP 的代码化方案4.1 背包问题的三种变体01 背包、完全背包与分组背包动态规划里最容易被模板化的就是背包类问题因为状态定义和转移方程高度固定。01 背包的一维滚动数组写法是基础中的基础外层枚举物品内层体积从大到小遍历保证每个物品只取一次。这个逆序的原因在于一维数组会继承上一层状态如果正序遍历当前物品会被多次使用从而退化成完全背包——这是最经典的边界理解值得在注释里写明白。// 01背包v为体积数组w为价值数组V为背包容量 vectorlong long knap01(const vectorint v, const vectorint w, int V) { vectorlong long dp(V 1, 0); for (int i 0; i (int)v.size(); i) for (int j V; j v[i]; --j) // 逆序遍历容量 dp[j] max(dp[j], dp[j - v[i]] w[i]); return dp; }完全背包只是把内层循环改成从v[i]到V正序遍历含义也从“每个物品取一次”变为“每个物品可以取任意次”。这里有个容易忽略的细节完全背包正序遍历的中间状态dp[j - v[i]]可能已经包含了当前物品这正是无限取用所要的效果。分组背包则是在物品外层套一个组循环每组内做一次 01 背包注意组内不能用滚动数组正序还是得组内逆序。// 分组背包每组选一个物品group 里存 (体积, 价值) vectorlong long knapGroup(const vectorvectorpairint,int groups, int V) { vectorlong long dp(V 1, 0); for (auto items : groups) for (int j V; j 0; --j) for (auto [vol, val] : items) if (j vol) dp[j] max(dp[j], dp[j - vol] val); return dp; }分组背包的容量循环放在物品循环外层组内物品共享同一个逆序容量状态这保证了每组最多选择一个物品。如果你在做树形背包选课问题需要先 DFS 子树合并 dp 数组那是另一个更复杂的变体模板库里单独存档即可。4.2 LIS 与 LCSO(nlogn) 模板及拼接细节最长上升子序列的 O(nlogn) 解法用到了“维护每个长度下末尾元素的最小值”这一贪心思路。具体操作是每次遇到新元素就在tail数组里找第一个大于等于它的位置并替换。代码短但边界条件很容易写错尤其是 lower_bound 还是 upper_bound 的选择——严格上升用 lower_bound非严格上升用 upper_bound。// 最长上升子序列长度严格上升用 lower_bound非严格用 upper_bound int lisLength(const vectorint a) { vectorint tail; // tail[k] 表示长度为 k1 的上升子序列的末尾最小值 for (int x : a) { auto it lower_bound(tail.begin(), tail.end(), x); if (it tail.end()) tail.push_back(x); else *it x; } return (int)tail.size(); }注意tail本身不是 LIS 序列它只保存每个长度下的最优末尾值。如果题目要求输出具体序列需要额外开一个数组记录每个元素作为末尾时的前驱下标然后从最后一个补出来的位置回溯。这个回溯代码在竞赛题里出现频率不高但有备无患。至于 LCS 的 O(nlogn) 做法只适用于两个序列中一个无重复元素的情况——把 A 序列映射成下标B 序列按映射转换成新序列后再求 LIS这招能大幅提速但映射前要确认元素不重复否则会出错。4.3 区间 DP枚举长度还是枚举端点断环成链技巧区间 DP 的固定套路是“枚举区间长度再枚举起点最后枚举分割点”。之所以要先枚举长度是因为转移依赖更短的区间结果而长度天然保证了无后效性。代码结构高度一致只需要根据题目修改转移里的合并逻辑。// 经典石子合并dp[l][r] 表示合并区间 [l,r] 的最小代价 int mergeStones(const vectorint a) { int n a.size(); vectorint pre(n 1, 0); for (int i 0; i n; i) pre[i 1] pre[i] a[i]; vectorvectorint dp(n, vectorint(n, 0x3f3f3f3f)); for (int i 0; i n; i) dp[i][i] 0; for (int len 2; len n; len) { for (int l 0; 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] pre[r 1] - pre[l]); } } return dp[0][n - 1]; }这里的pre前缀和用于快速求区间和是石头总代价的加速工具。0x3f3f3f3f是常见的“大数”用来初始化 dp 数组表示未计算状态。如果要处理环状排列的石子只需要把数组复制一份接在后面跑 2n 长度的区间 DP最后取所有长度为 n 的滑动区间的方案最小值——这就是断环成链是环形 DP 问题的标准解法模板库里可以单独存一个断环版。5. 计算几何模板向量运算、凸包、射线法与旋转卡壳5.1 向量运算基座点积、叉积与精度处理计算几何是所有模块里最容易出精度问题的一类90% 的翻车都和浮点数比较有关。我处理浮点判断的固定习惯是定义一个sgn(x)函数把浮点比较统一转成eps容差内的 -1/0/1 三态输出。所有几何模板都基于这个函数避免在 if 里直接写或。const double eps 1e-8; int sgn(double x) { if (fabs(x) eps) return 0; return x 0 ? 1 : -1; } struct Point { double x, y; }; double cross(const Point a, const Point b, const Point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } double dot(const Point a, const Point b, const Point c) { return (b.x - a.x) * (c.x - a.x) (b.y - a.y) * (c.y - a.y); }叉积cross(a,b,c)的几何含义是向量 ab 与 ac 的有向面积的两倍正负表示 c 在 ab 的哪一侧。点积dot(a,b,c)返回向量 ab 与 ac 的点积可以用来判断夹角是锐角、钝角还是直角。参数上eps的取值在 1e-8 到 1e-10 之间比较安全太小会把有效浮点误差放大成非零太大会把本来不同的点判成相同。这套基座建议所有几何模板都依赖它遇到坐标范围很大的题再单开一个 long long 版本避免中间量溢出。5.2 Andrew 凸包排序扫两遍凸包算法里 Andrew 单调链比 Graham 扫描更好写因为它只需要按坐标排序后做两次单调栈扫描不需要极角排序。整个算法分两步先把点按 x 坐标升序、x 相同时按 y 升序排序然后从左到右扫一遍维护下凸壳从右到左扫一遍维护上凸壳。每次加入新点时用叉积判断栈顶元素是否该被弹出——叉积小于等于 0 说明出现了顺时针转弯或共线要弹出。vectorPoint convexHull(vectorPoint pts) { sort(pts.begin(), pts.end(), [](const Point a, const Point b) { return a.x b.x || (a.x b.x a.y b.y); }); int n pts.size(); vectorPoint hull(2 * n); int k 0; for (int i 0; i n; i) { while (k 2 sgn(cross(hull[k-2], hull[k-1], pts[i])) 0) --k; hull[k] pts[i]; } for (int i n - 2, t k 1; i 0; --i) { while (k t sgn(cross(hull[k-2], hull[k-1], pts[i])) 0) --k; hull[k] pts[i]; } hull.resize(k - 1); return hull; }cross 0会把共线点从凸壳上剔除如果需要保留边界上的所有共线点把条件改成 0即可。hull.resize(k - 1)是因为最后一次循环会把起点重复加入一次。返回的 hull 是逆时针顺序。参数上注意传入pts是值传递sort 会直接修改它如果调用处还需要原始点集记得传拷贝或者调用前自行复制。5.3 点在多边形内射线法与边界判定点在多边形内的经典做法是射线法从目标点向右水平发出一条射线统计与多边形边的交点数量。奇数次交点则点在多边形内偶数次则在外部。难点在于处理三种边界情况射线穿过顶点、射线与边重合、点落在边上。常见的处理技巧是“忽略水平边”并在顶点相交时只统计一边的端点。bool pointInPolygon(const Point p, const vectorPoint poly) { int n poly.size(); bool inside false; for (int i 0, j n - 1; i n; j i) { const Point a poly[i], b poly[j]; if (sgn(cross(a, b, p)) 0 sgn(dot(p, a, b)) 0) return true; // 点在边上 if (((a.y p.y) ! (b.y p.y)) sgn(p.x - a.x (p.y - a.y) / (b.y - a.y) * (b.x - a.x)) 0) inside !inside; } return inside; }这段代码里((a.y p.y) ! (b.y p.y))等价于“p 的 y 坐标严格位于 a.y 和 b.y 之间”这是为了处理射线穿过顶点时只计一次。除法换成叉积形式能减少精度损耗但直接写法更容易读懂。如果多边形顶点数量巨大且查询次数很多可以用扫描线预处理或者用向量叉积判断点是否在凸多边形内——凸多边形只要所有边的叉积方向一致即可判断。5.4 旋转卡壳求凸包直径旋转卡壳解决的问题是“凸包上距离最远的两点”经典应用是平面最近点对之外的最远点对。它基于一个观察距离一个顶点最远的点沿着凸包移动时是单调的所以可以双指针扫描。// 旋转卡壳返回凸包直径的平方避免浮点误差 long long rotatingCalipers(const vectorPoint hull) { int n hull.size(); if (n 2) { long long dx hull[1].x - hull[0].x, dy hull[1].y - hull[0].y; return dx * dx dy * dy; } long long ans 0; int j 1; for (int i 0; i n; i) { while (sgn(cross(hull[i], hull[(j 1) % n], hull[(i 1) % n])) sgn(cross(hull[i], hull[j], hull[(i 1) % n]))) j (j 1) % n; long long dx hull[j].x - hull[i].x, dy hull[j].y - hull[i].y; ans max(ans, dx * dx dy * dy); } return ans; }这里返回的是直径的平方用 long long 规避浮点误差。叉积比较时两边同时过sgn是为了统一量纲防止不同精度的叉积直接比较。参数上有个细节j的初始化为 1循环里(j1)%n保证指针不会越界。旋转卡壳还衍生了求最小外接矩形、两凸包最近距离等变体核心都是这个双指针单调移动的思路模板库里存一份旋转卡壳可以辐射不少题。6. 模板库实战中的六个典型翻车现象原因与对策6.1 快速幂取模结果一直是 0现象某题用快速幂算组合数取模输出恒为 0但手算小数据没问题。原因模数不是质数或者底数和模数不互质时乘法逆元的预处理出现了问题快速幂本身没错错在逆元用了费马小定理——它只对素数模成立。解决确认模数是否为素数不是素数时改用扩展欧几里得求逆元或者用中国剩余定理拆分。这个坑在数论题里出现频率极高建议在模板库的快速幂注释里直接注明“仅当 mod 为素数时可用逆元”。6.2 Dijkstra 堆优化空间爆满现象1e5 点的图跑最短路直接 MLE检查后是优先队列里堆积了大量过期状态。原因没有使用惰性删除或者每次松弛都 push 一个 pair旧状态永远不会弹出去导致堆无限膨胀。解决确认if (d ! dist[u]) continue;的判别在若用d dist[u]也成立但注意两者在数值恰好相等时行为不同。另一个细节是edges的reserve一定要做vector 扩容的峰值内存很容易超过限制。6.3 并查集 find 写成了循环后忘却路径压缩现象数据量一大就超时百思不得其解。原因find函数的路径压缩只发生在递归返回时如果迭代版本里没有把沿途节点的 parent 直接指向根整个树不会变矮。解决检查 find 实现里是否在找到根后回写了 parent。我常用的保险写法是递归版因为即使编译优化不佳绝大多数题目数据规模下递归栈深度不会超过树高而树高在按秩合并下是 log 级别。如果题目构造了故意卡递归的链式数据把树高打满成线性则改用非递归版本并显式回写。6.4 凸包算出来只有两个点现象上千个点求凸包结果 hull 数组只有 2 个元素。原因所有点共线或者叉积判断条件写反了把凹进去的点也弹出了还有一种可能是排序比较器没处理好 x 相同的情况。解决先手动检查输入是否包含共线点cross 0是剔除共线点的选择如果题目要求保留共线点改成 0排序比较器改成先 x 再 y 的严格弱序杜绝比较器返回相等歧义导致 sort 崩溃。这类问题在几何题里叫“数据退化”出题人经常故意塞这种边界。6.5 区间 DP 初始化 0x3f3f3f3f 后求最小值取到巨大值现象dp 数组大量状态依然是 INF但正确结果应该存在。原因枚举分割点时某个合法的分割点组合提前被剪枝跳过了或者枚举区间长度时起点写成了 0 而不是 1导致部分区间从未被计算。解决在区间 DP 模板里打印中间 dp 状态排查先确认dp[i][i] 0的初始化覆盖了全部单点状态再确认长度循环的下界从 2 开始且llen-1不越界。很多区间 DP 的代码看起来一致实际 bug 都在下标偏移上。6.6 射线法判断点在多边形内部但外部点也进了现象用射线法测试几何题数据部分明显在图形外的点被判定在内部。原因射线恰好穿过多边形顶点交了两次交点被误判为偶数但实际应算作奇数。解决上面给的模板里(a.y p.y) ! (b.y p.y)这种写法就是为了规避顶点重复计数问题。如果还出错检查点是落在边上的判定是否生效——边上的点必须优先返回 true否则射线法会把它当成外部。以上六条坑是我在整理模板库过程中反复踩过的。每条最后都落在了具体写法选择上而不是玄学调参。我的习惯是每踩一次就回模板库补一条注释把“为什么这么写”写清楚而不是只留代码。模板的价值不在代码本身而在你为它做过的所有验证和记录这个动作比任何现成模板都有用。希望帮到你。本文还有配套的精品资源点击获取