简介本资源是一套面向OI、ACM、PAT、CSP等编程竞赛选手的高频代码模板合集聚焦算法竞赛中高频出现的经典问题与优化实现解决选手在限时编码中重复造轮子、边界处理失误、效率不足等痛点。压缩包共53个文件含41份Markdown文档系统讲解算法原理、适用场景与注意事项、11个可直接编译运行的C模板代码如快读、KMP、Dijkstra、并查集、线性DP等以及1个.gitignore配置文件整体仅51KB轻量易集成。已有740人学习下载内容覆盖基础算法、动态规划、贪心与回溯、数学与字符串、图论、网络流、计算几何及位运算优化等十大模块目录按知识域分层组织每类模板均附典型题目链接与关键注释便于快速检索、理解迁移与实战调用。1. 项目概述为什么我们需要一份“常用代码模板”在算法竞赛和编程能力测试的世界里无论是初出茅庐的新手还是身经百战的老将几乎每个人的代码库深处都藏着一份或几份被视为“压箱底宝贝”的代码模板。这份模板就是我们今天要深入探讨的核心一份面向OI信息学奥林匹克、OJ在线评测系统、ACM-ICPC国际大学生程序设计竞赛、PAT浙江大学计算机程序设计能力考试以及CSP计算机软件能力认证等主流赛事的通用代码模板集。你可能会问网上模板不是一抓一大把吗确实但问题也恰恰出在这里。很多流传的模板要么过于庞杂包含了大量你可能一辈子都用不上的冷门算法要么过于简陋只给了核心函数缺乏关键的边界处理和初始化细节直接套用反而容易踩坑。更常见的是模板的风格和实现方式千差万别如果不理解其背后的原理和适用场景在紧张的比赛或考试中你根本不敢用也不会用。因此我结合自己多年打比赛和带新人的经验整理并重构了这份“常用代码模板”。它的目标非常明确不是最全的但一定是最常用、最可靠、最易于理解和现场默写的。它更像是一个经过实战检验的“工具箱”里面的每一件“工具”算法或数据结构都打磨得趁手并且附上了清晰的使用说明书和“防呆”提示。无论是应对考研机试、准备CSP认证还是冲击ACM区域赛这份模板都能为你节省大量重复编码和调试的时间让你把精力集中在问题建模和策略选择上。2. 模板设计哲学与核心原则在开始罗列代码之前我们必须先统一思想。一份好的模板不是代码片段的简单堆砌它背后有一套完整的设计哲学。盲目套用未经消化的模板比从零开始写更容易出错。2.1 核心设计原则可靠性与简洁性的平衡我的模板设计首要原则是“可靠性压倒一切”。竞赛和考试中的代码正确性是唯一的标准没有“差不多”。一个在99%情况下正确的快速排序会因为那1%的退化情况例如已排序数组导致超时从而让你丢掉整道题。因此模板中的每一个算法都必须经过精心设计以杜绝常见的边界情况错误和性能陷阱。其次是“现场可重现性”。模板再精妙如果你在考场上记不住、写不出来也是白搭。所以我倾向于选择那些逻辑清晰、结构对称、易于记忆的实现方式。有些算法存在多种优化版本我会选择那个在时间复杂度和代码复杂度上取得最佳平衡的版本而不是一味追求极致的性能。例如Dijkstra算法我使用优先队列的标准实现而不是更复杂但常数更小的配对堆因为前者更容易在高压环境下一次性写对。最后是“接口一致性”。所有模板的输入输出格式、命名风格、错误处理方式都尽量统一。例如图论算法通常接受(n, m, edges)这样的参数并使用从0或1开始编号的约定。这能减少你在组合不同模板时的认知负担。2.2 模板的“黑盒”与“白盒”使用观对于模板的使用我建议分两个阶段“黑盒”阶段初学/应急在不理解内部原理的情况下先将模板当作一个函数来用。你需要准确知道它解决什么问题输入是什么格式输出是什么含义时间复杂度是多少这个阶段的目标是“会用”快速解决眼前问题。“白盒”阶段精通/内化在时间充裕时必须深入理解模板的每一行代码。为什么这里要1那个数组为什么开两倍大小这个特判是处理什么情况的只有理解了原理你才能信任它才能在它出错时快速定位问题甚至根据题目特性进行微调。永远不要满足于“黑盒”使用。2.3 代码风格与规范为了保证代码的清晰度本模板遵循以下约定以C为例命名全局数组、变量使用全大写或g_前缀如MAXN,g_graph函数和局部变量使用小写加下划线。缩进与空格使用2或4个空格缩进运算符两侧加空格增强可读性。注释在关键步骤、易错点、时间复杂度处添加简洁注释。不写“这里循环”这种废话而是写“循环条件当队列不空且未找到目标”。常用头文件与宏一份统一的、包含所有常用头文件和宏定义的“板子头”是节省时间的利器。#include bits/stdc.h // 竞赛常用万能头但需注意某些环境不支持 using namespace std; typedef long long ll; typedef pairint, int pii; #define rep(i, a, b) for(int i (a); i (b); i) #define per(i, a, b) for(int i (a); i (b); --i) const int MAXN 1e5 5; // 根据题目数据范围调整 const int INF 0x3f3f3f3f; // 一个很大的数常用于初始化距离注意#include bits/stdc.h并非C标准但在绝大多数OJ和竞赛环境中都被支持。在要求严格的场合如某些企业面试手写请使用标准的iostream,vector等头文件。3. 基础数据结构模板精讲基础数据结构是构建一切算法的砖瓦。这里的模板不仅要实现功能更要考虑竞赛中的典型用法。3.1 并查集路径压缩与按秩合并的权衡并查集是处理动态连通性问题的神器。最朴素的实现会在链式结构下退化。因此“路径压缩”和“按秩合并”是两个必须掌握的优化。我的模板通常同时使用两者以达到近乎常数时间的查询效率。class DSU { private: vectorint parent, rank; // rank也可以是size按大小合并 public: DSU(int n) : parent(n), rank(n, 0) { iota(parent.begin(), parent.end(), 0); // 初始化每个元素的父节点为自己 } int find(int x) { // 路径压缩在查找过程中将节点直接连到根 return parent[x] x ? x : parent[x] find(parent[x]); } bool unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return false; // 已在同一集合 // 按秩合并将矮树接到高树下保持树的高度最小 if (rank[rx] rank[ry]) { parent[rx] ry; } else if (rank[rx] rank[ry]) { parent[ry] rx; } else { parent[ry] rx; rank[rx]; // 两树同高合并后高度1 } return true; } bool connected(int x, int y) { return find(x) find(y); } };实操心得初始化大小一定要根据题目最大节点数n来初始化通常开n5留有余量。“按秩”的秩rank数组记录的是树高的上界不是精确高度。用size数组记录集合大小在需要知道连通块大小时非常有用如“朋友圈”问题。find函数递归写法简洁但极端深度下可能有栈溢出风险。非递归写法更安全while (parent[x] ! x) { parent[x] parent[parent[x]]; x parent[x]; } return x;。3.2 树状数组与线段树区间操作的左右手两者都用于处理动态区间查询与更新但各有侧重。树状数组代码量极小、效率高但功能受限主要处理前缀和型的区间问题如区间和、区间加单点查询。其核心在于lowbit操作。class Fenwick { private: vectorint tree; int n; int lowbit(int x) { return x -x; } public: Fenwick(int size) : n(size), tree(size 1, 0) {} // 单点增加 val void add(int idx, int val) { for (; idx n; idx lowbit(idx)) tree[idx] val; } // 查询前缀和 [1, idx] int query(int idx) { int sum 0; for (; idx 0; idx - lowbit(idx)) sum tree[idx]; return sum; } // 查询区间和 [l, r] (1-indexed) int rangeQuery(int l, int r) { return query(r) - query(l - 1); } };线段树功能强大可以处理几乎所有满足结合律的区间运算和、最值、GCD等也支持复杂的懒惰标记实现区间修改。但代码较长容易写错。class SegmentTree { private: vectorint arr, tree, lazy; int n; void build(int node, int start, int end) { if (start end) { tree[node] arr[start]; return; } int mid (start end) / 2; build(node * 2, start, mid); build(node * 2 1, mid 1, end); tree[node] tree[node * 2] tree[node * 2 1]; // 这里可以是 max, min, gcd 等 } void pushDown(int node, int start, int end) { if (lazy[node] ! 0) { int mid (start end) / 2; // 更新子节点值和懒惰标记 tree[node * 2] lazy[node] * (mid - start 1); lazy[node * 2] lazy[node]; tree[node * 2 1] lazy[node] * (end - mid); lazy[node * 2 1] lazy[node]; lazy[node] 0; // 清除当前节点标记 } } void updateRange(int node, int start, int end, int l, int r, int val) { if (l end || r start) return; if (l start end r) { // 完全包含更新当前节点并打上懒惰标记 tree[node] val * (end - start 1); lazy[node] val; return; } pushDown(node, start, end); // 向下传递标记 int mid (start end) / 2; updateRange(node * 2, start, mid, l, r, val); updateRange(node * 2 1, mid 1, end, l, r, val); tree[node] tree[node * 2] tree[node * 2 1]; } int queryRange(int node, int start, int end, int l, int r) { if (l end || r start) return 0; if (l start end r) return tree[node]; pushDown(node, start, end); int mid (start end) / 2; return queryRange(node * 2, start, mid, l, r) queryRange(node * 2 1, mid 1, end, l, r); } public: SegmentTree(vectorint nums) : arr(nums), n(nums.size()) { tree.resize(4 * n); lazy.resize(4 * n, 0); build(1, 0, n - 1); } void update(int l, int r, int val) { updateRange(1, 0, n - 1, l, r, val); } int query(int l, int r) { return queryRange(1, 0, n - 1, l, r); } };选择策略求区间和/单点更新无脑用树状数组。求区间最值线段树或ST表静态RMQ。区间加/赋值等复杂操作必须用带懒标记的线段树。二维问题树状数组套树状数组二维BIT比二维线段树好写得多。4. 图论算法模板实战图论是算法竞赛的重中之重也是最需要模板的领域之一。这里的模板必须健壮能处理各种图形态稠密、稀疏、负权边等。4.1 最短路径算法Dijkstra, SPFA 与 FloydDijkstra堆优化版解决非负权图的单源最短路。这是你必须刻在脑子里的模板。vectorint dijkstra(int n, vectorvectorpii graph, int start) { vectorint dist(n, INF); dist[start] 0; // 使用小顶堆pair的first是距离second是节点编号 priority_queuepii, vectorpii, greaterpii pq; pq.push({0, start}); while (!pq.empty()) { auto [cur_dist, u] pq.top(); pq.pop(); // 关键优化如果当前取出的距离大于记录的距离说明是旧数据跳过 if (cur_dist dist[u]) continue; for (auto [v, w] : graph[u]) { int new_dist cur_dist w; if (new_dist dist[v]) { dist[v] new_dist; pq.push({new_dist, v}); } } } return dist; }踩坑实录priority_queue默认是大顶堆必须用greaterpii改成小顶堆。那个if (cur_dist dist[u]) continue;判断至关重要不加的话复杂度会退化在稠密图上可能TLE。SPFABellman-Ford的队列优化可以处理负权边并能检测负权环。虽然其最坏时间复杂度是O(VE)但在随机图和竞赛数据中往往表现良好是“救急”的利器。// 返回一个vectorint为最短路长度如果存在负权环则返回空vector vectorint spfa(int n, vectorvectorpii graph, int start) { vectorint dist(n, INF); vectorint cnt(n, 0); // 记录入队次数用于检测负环 vectorbool inqueue(n, false); queueint q; dist[start] 0; q.push(start); inqueue[start] true; cnt[start]; while (!q.empty()) { int u q.front(); q.pop(); inqueue[u] false; for (auto [v, w] : graph[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; if (!inqueue[v]) { q.push(v); inqueue[v] true; cnt[v]; // 如果入队次数超过n次说明存在负环 if (cnt[v] n) return {}; // 返回空表示有负环 } } } } return dist; }Floyd-Warshall全源最短路核心代码就三重循环简单暴力。注意循环顺序是k, i, j且初始化和对自环的处理。vectorvectorint floyd(int n, vectorvectorint graph) { // graph是邻接矩阵 vectorvectorint dist graph; // 拷贝初始化 // 初始化自己到自己是0不连通是INF for (int i 0; i n; i) dist[i][i] 0; for (int k 0; k n; k) for (int i 0; i n; i) for (int j 0; j n; j) if (dist[i][k] INF dist[k][j] INF) // 防止INF相加溢出 dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]); return dist; }4.2 最小生成树Kruskal 与 PrimKruskal基于并查集适合稀疏图。思路极其清晰对所有边排序从小到大取边如果边的两端不在同一集合就选中它并合并集合。struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } }; int kruskal(int n, vectorEdge edges) { sort(edges.begin(), edges.end()); DSU dsu(n); int total_weight 0, edges_used 0; for (auto e : edges) { if (dsu.unite(e.u, e.v)) { total_weight e.w; edges_used; if (edges_used n - 1) break; // 树有n-1条边 } } return edges_used n - 1 ? total_weight : -1; // -1表示图不连通 }Prim堆优化版类似Dijkstra适合稠密图。从一个点开始不断选择连接“已选集合”和“未选集合”的最小权边。int prim(int n, vectorvectorpii graph) { vectorbool visited(n, false); priority_queuepii, vectorpii, greaterpii pq; // {weight, vertex} pq.push({0, 0}); // 从节点0开始初始距离为0 int total_weight 0, nodes_visited 0; while (!pq.empty() nodes_visited n) { auto [w, u] pq.top(); pq.pop(); if (visited[u]) continue; visited[u] true; total_weight w; nodes_visited; for (auto [v, weight] : graph[u]) { if (!visited[v]) { pq.push({weight, v}); // Prim是加入边的权重不是累积距离 } } } return nodes_visited n ? total_weight : -1; }重要区别Prim的优先队列里存的是边的权重而Dijkstra存的是从起点到该点的累积距离。这是两者实现上最核心的不同写混了结果就全错了。5. 动态规划与数论核心模板动态规划DP模板性较弱但一些经典模型和优化技巧可以模板化。数论则是充满了固定公式和结论的领域。5.1 经典DP模型背包、LCS与LIS0/1背包这是所有背包问题的基础。dp[j]表示容量为j的背包能获得的最大价值。int knapsack_01(int W, vectorint weights, vectorint values) { int n weights.size(); vectorint dp(W 1, 0); for (int i 0; i n; i) { for (int j W; j weights[i]; --j) { // 必须逆序 dp[j] max(dp[j], dp[j - weights[i]] values[i]); } } return dp[W]; }为什么逆序这是0/1背包的精髓。正序更新会导致物品被重复选取变成了完全背包。逆序保证了每个物品只被考虑一次。最长公共子序列经典二维DP。int longestCommonSubsequence(string text1, string text2) { int m text1.size(), n text2.size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); for (int i 1; i m; i) { for (int j 1; j n; j) { if (text1[i-1] text2[j-1]) { dp[i][j] dp[i-1][j-1] 1; } else { dp[i][j] max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; }最长上升子序列标准解法是O(n²) DP但优化版贪心二分可以达到O(n log n)。// O(n log n) 解法 int lengthOfLIS(vectorint nums) { vectorint tails; // tails[k] 存储长度为 k1 的LIS的最小可能结尾元素 for (int num : nums) { // 在 tails 中寻找第一个 num 的位置 auto it lower_bound(tails.begin(), tails.end(), num); if (it tails.end()) { tails.push_back(num); // 所有结尾都小于num可以延长LIS } else { *it num; // 用更小的 num 替换它为后续延长提供可能 } } return tails.size(); // tails的长度就是LIS的长度 }5.2 数论工具质数筛、快速幂与逆元埃拉托斯特尼筛法快速得到一定范围内的所有质数。vectorint sieveOfEratosthenes(int n) { vectorbool is_prime(n 1, true); is_prime[0] is_prime[1] false; vectorint primes; for (int i 2; i n; i) { if (is_prime[i]) { primes.push_back(i); // 从 i*i 开始标记因为 i*(i-1) 已被更小的质数标记过 if ((long long)i * i n) { for (int j i * i; j n; j i) { is_prime[j] false; } } } } return primes; }快速幂计算a^b mod m的利器基于二进制分解。long long fastPow(long long a, long long b, long long mod) { long long res 1 % mod; // 处理 mod1 的情况 a % mod; while (b 0) { if (b 1) res (res * a) % mod; // 当前二进制位为1乘上a a (a * a) % mod; // a自乘 b 1; // b右移一位 } return res; }乘法逆元费马小定理当模数mod为质数时a关于mod的逆元为a^(mod-2) mod mod。long long modInverse(long long a, long long mod) { // 前提mod 是质数且 a 与 mod 互质 return fastPow(a, mod - 2, mod); }6. 搜索与字符串处理模板6.1 深度优先搜索与回溯框架DFS回溯是解决排列、组合、子集等问题的通用框架。vectorvectorint res; vectorint path; void backtrack(vectorint nums, int start) { res.push_back(path); // 收集子集 for (int i start; i nums.size(); i) { // 去重逻辑如果nums有重复元素if (i start nums[i] nums[i-1]) continue; path.push_back(nums[i]); backtrack(nums, i 1); // 注意是 i1不是 start1 path.pop_back(); // 回溯 } } // 调用sort(nums.begin(), nums.end()); backtrack(nums, 0);关键点backtrack函数参数中的start用于控制选择列表避免重复选择。path记录当前路径res收集结果。回溯的三要素选择、递归、撤销选择。6.2 字符串匹配KMP算法KMP是字符串匹配的经典算法理解next数组是关键。vectorint buildNext(string pattern) { int m pattern.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 pattern[i] ! pattern[j]) { j next[j - 1]; // 回退 } if (pattern[i] pattern[j]) { j; } next[i] j; } return next; } int kmpSearch(string text, string pattern) { int n text.size(), m pattern.size(); if (m 0) return 0; vectorint next buildNext(pattern); for (int i 0, j 0; i n; i) { while (j 0 text[i] ! pattern[j]) { j next[j - 1]; } if (text[i] pattern[j]) { j; } if (j m) { return i - m 1; // 找到匹配返回起始位置 // 如果找所有匹配这里记录位置后执行 j next[j-1]; } } return -1; // 未找到 }next数组的含义next[i]表示模式串P[0...i]这个子串的最长相等前后缀的长度。这是KMP能跳过无效比较的核心。7. 模板使用心法与避坑指南有了模板不等于高枕无忧。下面这些从无数次WA错误答案和TLE超时中总结出的经验可能比模板本身更重要。7.1 输入输出优化与边界处理在C中对于大数据量如1e5以上级别的输入输出关闭同步流可以大幅提升速度。ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);警告使用了这行代码后严禁将cin/cout与scanf/printf混用否则会导致输入输出顺序混乱。边界处理是永恒的主题数组开得足够大吗通常要比题目数据范围多开5-10个元素。图论中邻接表或边数组的大小是多少如果是无向图边数m要开2*m。递归深度是否可能爆栈DFS深搜时如果树或图深度可能很大如1e5需要手写栈或改用BFS。整数溢出涉及乘法时特别是求最小公倍数、组合数或距离累加时果断使用long long。7.2 调试与对拍技巧在OJ上无法调试如何定位错误小数据测试自己构造一些小的、边界的数据n0,1,2负数最大值等。输出中间变量在关键步骤后输出关键变量值提交前记得注释掉。对拍这是最强大的调试手段。写一个绝对正确但可能很慢的暴力算法BF和你的优化算法OPT在同一个随机数据生成器下跑几百上千次比较结果。一旦发现不一致就用这个数据去细查。// 简易对拍框架思路 while (true) { generate_random_input(); // 生成随机输入数据 ans_bf brute_force(input); ans_opt my_algorithm(input); if (ans_bf ! ans_opt) { cout Found mismatch! endl; // 输出输入数据和两个结果 break; } }7.3 模板的“魔改”与适配没有能解决所有问题的万能模板。你必须学会根据具体问题调整模板。状态定义DP模板的核心是状态定义。背包问题的dp[j]定义是价值但如果问“能否恰好装满”就可以定义为布尔值。图论算法的初始化dist数组初始化为INF但INF的值要足够大又不能大到加法溢出。通常用0x3f3f3f3f其两倍仍在int范围内。并查集处理“删除”操作标准并查集不支持删除。如果题目有删除可以考虑使用“反向操作”离线处理从最终状态倒着加边或“时光倒流”技巧。8. 从模板到思维算法的本质最后我想强调一点模板是拐杖不是腿。真正的能力在于将实际问题抽象为算法模型的能力。看到一个题目你能迅速判断它是最短路、网络流、贪心还是DP这需要大量的练习和总结。建议你建立一个自己的“解题档案”记录每道题的关键题意转化点、使用的算法或数据结构、以及易错点。例如“看到‘最短时间’、‘最少步骤’优先考虑BFS。”“看到‘最大值最小’或‘最小值最大’考虑二分答案。”“看到序列上的区间操作想到线段树/树状数组/前缀和。”“看到依赖关系、拓扑排序想到是DAG有向无环图。”这份代码模板是我多年竞赛和教学经验的结晶它应该成为你武器库中的标准装备而不是思考的替代品。多写多练多思考在理解的基础上记忆在实战中灵活运用你才能真正驾驭这些算法让它们成为你解决复杂问题的得力工具。本文还有配套的精品资源点击获取