简介这份代码模板合集面向参加 OI、OJ、ACM、PAT、CSP 等编程竞赛与认证的选手覆盖从入门到进阶的常用算法实现帮助在有限赛时内快速写出正确且高效的代码。资源包共 53 个文件以 41 个 md 笔记和 11 个 cpp 源码为主另含 1 个 gitignore 配置压缩包约 51KB体积轻便便于随取随用。内容按基础算法、贪心、动态规划、数学、字符串、图论、网络流、数据结构等模块组织涵盖排序与二分、二维前缀和与差分、背包与区间动态规划、组合数与快速幂、KMP 与字典树、最短路与最小生成树、割点割边与强连通分量、并查集与平衡树等高频考点。cpp 文件可直接编译运行md 文档则梳理了思路与结论方便对照理解与赛前速查。目前已有 747 人学习适合希望系统积累模板、提升编码速度的竞赛选手。1. 从 OI 到 CSP一套代码模板怎么覆盖五类判题场景打 OI 和 ACM 的人都有个共同习惯本地攒一套自己顺手的代码模板比赛时直接改主逻辑输入输出、数据结构、图论、数论这些轮子不重复造。但真到 OJ 上刷题、PAT 考级、CSP 认证的时候你会发现同一套模板经常翻车——杭电 OJ 多组输入不给组数PAT 乙级卡输出格式空格CSP 的 T1 又要求极简快速 IO。问题不在算法在模板没有按判题场景分层。这篇笔记拆的就是这件事一套能同时应付 OI、OJ、ACM、PAT、CSP 的代码模板该怎么组织。核心思路是把模板拆成三层——输入输出层、数据结构层、算法层每层按平台特性做开关。适合正在准备 CSP 认证、PAT 乙级、或者刷杭电 OJ、东方博宜 OJ 的在校生和转行刷题的人。下面从选型理由讲到可抄的代码再到我踩过的坑一步步来。2. 模板分层的选型理由为什么不能一套 IO 打天下2.1 五类平台的判题差异到底在哪先把差异摆清楚不然后面写模板没有依据。OI 和 ACM 通常给明组数或读到 EOF输入格式相对规整时间限制宽松的题居多用 cin/cout 加 sync_with_stdio(false) 基本够。OJ 平台就杂了杭电 OJ 经典的多组输入不给 T必须 while(cinn) 或 while(scanf!EOF)东方博宜 OJ、郑轻 OJ 这类教学平台题面里经常混着「输入若干组」和「输入第一行为 T」得看题判断。PAT 乙级最坑的是输出格式1037 在霍格沃茨找零钱那题要求输出 Galleon.Sickle.Knut 格式负号位置、进位规则都得抠模板里得留一个格式化输出函数。CSP 认证的 T1、T2 是拿分题输入量可能到 10^6必须用快读但 T3 之后又是图论和 DP模板要能快速切换。ACM 竞赛题目则要求多测清空全局数组这个在 OI 里反而不常强调。所以一套模板硬扛所有场景要么 IO 太慢超时要么格式错 WA要么多测没清空 RE。分层是唯一解。2.2 三层结构IO 层、容器层、算法层我一般把模板分成三个文件或三个代码块。IO 层管读入读出提供 read()、write() 和格式化输出容器层放并查集、线段树、树状数组这些高频结构算法层放最短路、最小生成树、数论函数。比赛时按平台选 IO 层容器和算法层直接复制。这样分的好处是CSP 用快读 IO 层PAT 用带格式化的 IO 层杭电 OJ 用 EOF 循环 IO 层容器和算法层完全复用。下面给具体代码。2.3 最小可用模板骨架先看 IO 层的三种写法这是最影响判题结果的部分。// IO 层方案 ACSP / 大数据量场景快读快写 #include bits/stdc.h using namespace std; inline 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; } inline void write(int x) { if (x 0) { putchar(-); x -x; } if (x 9) write(x / 10); putchar(x % 10 0); }这段快读的逻辑是逐字符解析跳过非数字字符遇到负号翻转符号位。参数上注意 read() 只处理 int如果题目数据到 long long要把 x 和返回值改成 long long否则溢出后结果全错。write() 递归输出CSP 的 T1 用这个比 cout 快三到五倍。// IO 层方案 B杭电 OJ / 多组输入不给组数 int n; while (scanf(%d, n) ! EOF) { // 每组独立处理注意全局数组要清空 solve(n); }EOF 循环的关键是 scanf 返回值判断不能用 while(1) 然后 break因为有些题最后没有换行cin 会多读一次。参数上如果输入是字符串用 while (scanf(%s, s) ! EOF)注意 s 要开够空间。// IO 层方案 CPAT 乙级 / 格式化输出 void printGalleon(long long totalKnut) { // 1 Galleon 17 Sickle, 1 Sickle 29 Knut long long g, s, k; int sign totalKnut 0 ? -1 : 1; totalKnut llabs(totalKnut); g totalKnut / (17 * 29); s (totalKnut % (17 * 29)) / 29; k totalKnut % 29; if (sign 0) printf(-); printf(%lld.%lld.%lld\n, g, s, k); }PAT 1037 这题的核心是统一换算成最小单位 Knut 再转回负号单独处理。参数上 17 和 29 是题目给定的进制不能写死成其他值。输出格式必须严格是 G.S.K中间用点号末尾换行少一个都 WA。提示PAT 乙级的输出格式题建议先在本地用 printf 拼好字符串再输出不要用 cout 的 链式拼接容易多空格。3. 容器层模板并查集、树状数组、线段树怎么写成即插即用3.1 并查集的路径压缩与按秩合并并查集是 OI 和 ACM 出现频率最高的结构CSP 的 T3 也常考。模板要同时支持路径压缩和按秩合并否则遇到 10^5 次操作会 TLE。struct DSU { vectorint fa, rk; DSU(int n) : fa(n 1), rk(n 1, 0) { for (int i 1; i n; i) fa[i] i; } int find(int x) { // 路径压缩递归把沿途节点直接挂到根 return fa[x] x ? x : fa[x] find(fa[x]); } void unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return; // 按秩合并小树挂到大树上避免退化成链 if (rk[ra] rk[rb]) swap(ra, rb); fa[rb] ra; if (rk[ra] rk[rb]) rk[ra]; } };find 里的 fa[x] find(fa[x]) 是路径压缩的关键把查询路径上所有节点直接指向根下次查询 O(1)。unite 里按秩合并保证树高 O(log n)。参数上 n 是元素个数初始化时 fa 开 n1 是为了 1-indexed如果题目是 0-indexed 要改。常见误用是只写路径压缩不写按秩合并单次操作均摊接近 O(1) 但最坏情况仍可能慢竞赛里建议都写。3.2 树状数组的单点修改与区间查询树状数组代码短适合 CSP 和 PAT 里需要频繁前缀和的题。struct BIT { int n; vectorlong long c; BIT(int n) : n(n), c(n 1, 0) {} void add(int i, long long v) { // i 的二进制最低位决定管辖范围 for (; i n; i i -i) c[i] v; } long long sum(int i) { long long s 0; for (; i 0; i - i -i) s c[i]; return s; } long long rangeSum(int l, int r) { return sum(r) - sum(l - 1); } };add 里 i i -i 是向上更新所有管辖 i 的节点sum 里 i - i -i 是向下累加前缀。参数上 c 数组开 n1下标从 1 开始。如果题目要区间修改单点查询把 add 和 sum 的角色互换即可。注意 long long 防溢出PAT 里有些题数据到 10^9 累加会爆 int。3.3 线段树的懒标记下推线段树比树状数组重但 CSP 的 T3 和 ACM 区域赛常考区间修改加区间查询必须带懒标记。struct SegTree { int n; vectorlong long tree, lazy; SegTree(int n) : n(n), tree(4 * n, 0), lazy(4 * n, 0) {} void pushDown(int node, int l, int r) { if (lazy[node] 0) return; int mid (l r) / 2; // 懒标记下推到左右子节点 tree[node * 2] lazy[node] * (mid - l 1); lazy[node * 2] lazy[node]; tree[node * 2 1] lazy[node] * (r - mid); lazy[node * 2 1] lazy[node]; lazy[node] 0; } void update(int node, int l, int r, int ql, int qr, long long v) { if (ql l r qr) { tree[node] v * (r - l 1); lazy[node] v; return; } pushDown(node, l, r); int mid (l r) / 2; if (ql mid) update(node * 2, l, mid, ql, qr, v); if (qr mid) update(node * 2 1, mid 1, r, ql, qr, v); tree[node] tree[node * 2] tree[node * 2 1]; } long long query(int node, int l, int r, int ql, int qr) { if (ql l r qr) return tree[node]; pushDown(node, l, r); int mid (l r) / 2; long long res 0; if (ql mid) res query(node * 2, l, mid, ql, qr); if (qr mid) res query(node * 2 1, mid 1, r, ql, qr); return res; } };pushDown 是懒标记的核心在访问子节点前把父节点的标记传下去同时更新子节点的 tree 值。参数上 tree 和 lazy 开 4*n因为线段树节点数不超过 4n。update 和 query 的 ql、qr 是查询区间l、r 是当前节点区间。常见翻车点是忘记 pushDown 就递归导致子节点值没更新查询结果偏小。注意线段树的 lazy 标记在多次 update 后可能累积很大如果题目有取模pushDown 里也要同步取模。4. 算法层模板最短路、最小生成树、数论的竞赛写法4.1 Dijkstra 堆优化与 SPFA 的取舍最短路是 ACM 和 CSP T3 的高频考点。正权图用 Dijkstra 堆优化负权图用 SPFA但 SPFA 在竞赛里容易被卡能不用就不用。// Dijkstra 堆优化邻接表存图 struct Edge { int to; long long w; }; vectorvectorEdge g; vectorlong long dist; void dijkstra(int s, int n) { dist.assign(n 1, LLONG_MAX); dist[s] 0; // 小根堆pair距离, 节点 priority_queuepairlong long, int, vectorpairlong long, int, greater pq; pq.push({0, s}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 过期节点直接跳过这是堆优化的关键 if (d dist[u]) continue; for (auto e : g[u]) { if (dist[u] e.w dist[e.to]) { dist[e.to] dist[u] e.w; pq.push({dist[e.to], e.to}); } } } }dijkstra 的核心是优先队列每次取当前距离最小的节点松弛其邻居。if (d dist[u]) continue 是跳过已经过期的堆元素没有这行会重复处理导致 TLE。参数上 dist 初始化为 LLONG_MAXg 是邻接表s 是起点。如果图是 0-indexeddist 开 n 而不是 n1。SPFA 的写法类似 Bellman-Ford 加队列但竞赛里出题人常构造网格图卡 SPFA所以除非题目明确有负权且数据小否则优先 Dijkstra。4.2 Kruskal 最小生成树与并查集复用最小生成树用 Kruskal直接复用第 3 章的并查集。struct Edge { int u, v; long long w; }; long long kruskal(int n, vectorEdge edges) { // 按边权升序排序 sort(edges.begin(), edges.end(), [](const Edge a, const Edge b) { return a.w b.w; }); DSU dsu(n); long long total 0; int cnt 0; for (auto e : edges) { if (dsu.find(e.u) ! dsu.find(e.v)) { dsu.unite(e.u, e.v); total e.w; cnt; // 选够 n-1 条边就提前退出 if (cnt n - 1) break; } } return cnt n - 1 ? total : -1; // -1 表示不连通 }kruskal 的逻辑是贪心选最小边用并查集判断是否成环。参数上 edges 存所有边n 是节点数。cnt n-1 提前退出能省时间。返回 -1 表示图不连通这个约定要在主函数里处理。常见误用是忘记排序或排序方向写反导致选出的不是最小生成树。4.3 数论快速幂、GCD、线性筛数论模板在 PAT 和 CSP 里出现频率不低尤其是快速幂和 GCD。// 快速幂计算 (base^exp) % mod long long fastPow(long long base, long long exp, long long mod) { long long res 1; base % mod; while (exp 0) { if (exp 1) res res * base % mod; base base * base % mod; exp 1; } return res; } // 辗转相除求 GCD long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); } // 线性筛素数O(n) vectorint linearSieve(int n) { vectorint primes; vectorbool isComp(n 1, false); for (int i 2; i n; i) { if (!isComp[i]) primes.push_back(i); for (int p : primes) { if ((long long)i * p n) break; isComp[i * p] true; if (i % p 0) break; // 保证每个合数只被最小质因子筛一次 } } return primes; }fastPow 用二进制拆分指数每次右移一位遇到 1 就乘。参数上 mod 不能为 0base 先取模防止溢出。gcd 用递归写法注意 a、b 顺序不影响结果。linearSieve 里 if (i % p 0) break 是线性筛的关键保证每个合数只被筛一次复杂度 O(n)。常见翻车点是筛法里 i * p 用 int 溢出要转 long long。提示CSP 认证里数论题通常不卡复杂度但 PAT 乙级会有大数据线性筛比埃氏筛稳。5. 避坑与排查模板在真实判题里的五类翻车5.1 多组输入没清空全局数组导致 RE现象杭电 OJ 某题本地跑第一组对提交后第二组开始答案错或直接 RE。原因是全局数组、vector、map 在每组之间没清空上一组的数据残留。解决在每组 solve 开头统一清空或者把变量定义在循环内部。我一般写一个 reset() 函数把 fa、dist、g 这些全局结构重新初始化。5.2 PAT 输出格式多空格或少换行现象PAT 乙级 1037 提交后 WA本地输出看着一样。原因是 printf 里格式串多了空格或者末尾没换行。解决用 diff 对比标准输出或者把输出拼成一个字符串再打印。PAT 的判题机对空格和换行敏感建议所有输出都用 printf 显式控制。5.3 CSP 快读没处理负数导致答案错现象CSP T1 有负数输入用快读后结果全错。原因是 read() 里没处理负号或者 f 变量没重置。解决快读里加 if (c -) f -1并且每次调用 read() 时 f 初始化为 1。这个坑我在 CSP 模拟赛里踩过血泪经验。5.4 线段树 lazy 没下推导致查询偏小现象区间修改后查询结果比预期小。原因是 update 或 query 递归前没调 pushDown。解决在 update 和 query 进入子节点前都调 pushDown确保子节点值已更新。检查方法是用小数据手算对比。5.5 并查集只写路径压缩被卡 TLE现象并查集题提交后 TLE本地小数据正常。原因是只写路径压缩最坏情况树高 O(n)。解决加上按秩合并或者用启发式合并。竞赛里建议两个都写代码量增加不多但稳定性提升明显。6. 模板的进阶用法用宏和条件编译做平台切换模板写到后面最烦的是每次换平台要手动改 IO 层。我的习惯是用条件编译加宏在文件开头定义 PLATFORM 宏编译时切换。// 平台切换宏编译时用 -DPLATFORM_CSP 等指定 #ifdef PLATFORM_CSP #define FAST_IO 1 #elif defined(PLATFORM_PAT) #define FORMAT_OUT 1 #elif defined(PLATFORM_HDOJ) #define EOF_LOOP 1 #endif int main() { #ifdef FAST_IO // CSP 快读快写 int n read(); write(n); #elif defined(FORMAT_OUT) // PAT 格式化输出 printGalleon(total); #elif defined(EOF_LOOP) // 杭电 OJ 多组输入 int n; while (scanf(%d, n) ! EOF) solve(n); #endif return 0; }这样一套模板文件编译时加 -DPLATFORM_CSP 就是 CSP 版本加 -DPLATFORM_PAT 就是 PAT 版本不用改代码。参数上宏名自己定关键是和编译命令对应。我一般还会在模板里留一个 test() 函数用 freopen 重定向输入输出本地调试时打开。验证模板是否可靠我有个笨办法找五道不同平台的题每道用模板跑一遍记录编译命令、输入输出、耗时。如果五道都过模板基本可用。这个习惯帮我省了很多比赛时的调试时间。最后说个教训模板不是越多越好。我早期攒了三十多个算法模板比赛时反而找不到该用哪个。后来精简到 IO、并查集、线段树、Dijkstra、快速幂这五个核心覆盖了八成题目剩下的现场推。模板的价值在于让你少写重复代码不是替你想算法。希望帮到你。本文还有配套的精品资源点击获取