简介本资源是面向OI、ACM、PAT、CSP等编程竞赛选手的高频代码模板合集聚焦算法竞赛中反复出现的核心问题求解范式助力参赛者在限时环境下快速构建正确、高效、可复用的代码框架。压缩包共53个文件以41份Markdown文档系统讲解算法原理与实现要点和11个C源码文件含快读、KMP、Dijkstra、并查集、线段树等关键模板为主体辅以.gitignore配置总容量仅51KB轻量易集成。已有740人学习下载覆盖从入门到进阶的备赛需求。内容按模块结构化组织涵盖基础算法排序、二分、前缀和、动态规划背包、区间DP、图论最短路径、强连通、最小生成树、数学快速幂、欧拉函数、组合数、字符串Trie、Manacher、数据结构堆、平衡树、并查集及计算几何与位运算等十大方向每类均提供可直接调试的代码清晰注释典型应用场景说明。1. 项目概述为什么你需要一份“代码模板”如果你正在准备信息学奥赛OI、在线评测OJ、ACM国际大学生程序设计竞赛ACM、浙江大学计算机程序设计能力考试PAT或者中国计算机学会的软件能力认证CSP那么你大概率经历过这样的场景比赛或考试时间分秒流逝你面对一道题目思路清晰但敲代码时却卡在了如何快速实现一个“并查集”或者“Dijkstra最短路算法”上。手动实现不仅容易出错调试起来更是耗时。这时一份经过千锤百炼、可以直接“填空”的代码模板就成了你手中最锋利的武器。这份“常用代码模板”项目本质上是一个针对上述五大高频竞赛/认证场景的“算法实现工具箱”。它不是一个简单的代码片段合集而是一套经过实战检验的、模块化的、即插即用的解决方案库。其核心价值在于将比赛中那些思想经典但实现繁琐的算法封装成高度可靠、接口清晰的函数或类。选手在解题时无需再从零推导算法细节只需理解模板的输入输出含义便能将主要精力集中于问题建模和逻辑设计上从而在时间紧迫的竞赛环境中抢占先机。简单来说它解决的是“重复造轮子”和“临场实现易错”两大痛点。无论是初学者希望有一个可靠的学习参照还是资深选手追求极致的编码速度与准确性这样一份模板都至关重要。接下来我将为你深度拆解如何构建、使用并优化属于你自己的竞赛代码模板库。2. 模板库的整体架构与设计哲学2.1 核心设计原则模块化、鲁棒性与可读性的平衡构建一个优秀的模板库首先需要明确设计原则。这绝非简单的代码堆砌。1. 模块化与高内聚每个模板应独立解决一个明确的算法问题。例如“快速排序”是一个模板“线段树区间查询与修改”是另一个模板。模板之间尽量减少耦合通过清晰的接口函数参数、类公有方法进行交互。这样在解决复杂问题时你可以像搭积木一样组合多个模板。2. 鲁棒性优先竞赛代码没有第二次机会。模板必须能处理各种边界情况。例如图的邻接表存储模板要能处理重边和自环如果算法允许二分查找模板要能清晰定义搜索区间[left, right]是左闭右开还是左闭右闭并确保循环终止条件正确不会死循环。一个健壮的模板其正确性不应依赖于特定的数据特点。3. 效率与可读性的权衡竞赛环境追求极限效率但过于晦涩的“奇技淫巧”会大幅增加调试和维护成本。我的原则是在保证可读性的前提下进行优化。例如使用scanf/printf而非cin/cout处理大量输入输出是必要的优化但为了微小的性能提升将一段清晰的循环改为难以理解的位运算或宏定义则需谨慎。模板的终极目标是帮你快速写出正确的代码而不是炫耀技巧。4. 统一的代码风格与注释统一的变量命名如n代表数据规模g代表图、一致的缩进和空格、关键步骤的简明注释这些都能让你在紧张比赛中快速定位和理解模板。建议为每个模板编写简要的使用说明包括功能、时间复杂度、输入格式和输出格式。2.2 内容范畴规划覆盖五大场景的算法频谱不同的竞赛侧重点略有不同模板库需要全面覆盖OI/OJ/ACM这三者高度重叠侧重于经典算法与数据结构。模板库的核心应包括基础算法排序、二分、前缀和、差分、双指针。数据结构数组模拟链表、栈、队列、堆、并查集、树状数组、线段树、Trie树、ST表。图论邻接表存图、DFS/BFS、拓扑排序、最短路Dijkstra, SPFA, Floyd、最小生成树Kruskal, Prim、最近公共祖先LCA、网络流Dinic。数学快速幂、素数筛、最大公约数、组合数计算、矩阵快速幂。动态规划背包模板、线性DP、区间DP、树形DP的常用框架。字符串KMP、字符串哈希。PAT除了上述算法PAT更注重实际工程能力的考察因此需补充STL的熟练运用vector,map,set,string的常用操作模板化片段。排序与查找复杂结构体的多级排序sort自定义cmp。模拟题常用技巧日期处理、进制转换、多项式运算等“琐碎但易错”的代码块。CSP认证CSP题目难度跨度大且近年倾向于考察思维和建模能力。除了经典算法模板还应准备大整数运算CSP中有时会超出long long范围需要高精度加减乘除的模板。复杂模拟状态机、事件驱动模拟的框架代码。搜索优化剪枝技巧的常用模式可行性剪枝、最优性剪枝。注意模板不是越多越好而是越精越好。优先掌握和打磨那些在历年真题中出现频率最高的“王牌模板”如并查集、Dijkstra、快速排序、二分查找。一个你能闭着眼睛写对的简单模板远胜于十个你半懂不懂的复杂模板。3. 核心模板深度解析与实现要点3.1 数据结构之王并查集模板的三种写法与优化并查集是解决元素分组、连通性问题的神器。其模板的健壮性至关重要。基础模板路径压缩class DSU { private: vectorint parent; public: DSU(int n) : parent(n) { for (int i 0; i n; i) parent[i] i; // 初始化每个元素的父节点是自己 } // 查找根节点含路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩路径 } return parent[x]; } // 合并两个集合 void unionSet(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootY] rootX; // 将y的根节点接到x的根节点下 } } // 判断两个元素是否在同一集合 bool connected(int x, int y) { return find(x) find(y); } };要点解析路径压缩find函数中的递归操作parent[x] find(parent[x])使得后续查找同一节点的复杂度接近O(1)。这是模板效率的关键。初始化务必在构造函数中完成每个元素自成一集的初始化。合并策略上述是最简单的合并未按秩优化。在数据倾斜严重时树可能退化成链虽然路径压缩能缓解但并非最优。优化模板路径压缩 按秩合并 按秩合并通过记录树的深度或大小总是将较矮的树连接到较高的树上从而保证树的高度增长缓慢。class DSU { private: vectorint parent, rank; // rank可理解为树高的上界 public: DSU(int n) : parent(n), rank(n, 0) { // 初始高度为0 for (int i 0; i n; i) parent[i] i; } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unionSet(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { // 两树同高任意合并但合并后树高1 parent[rootY] rootX; rank[rootX]; } } };实操心得在绝大多数OJ题目中只使用路径压缩的简易版完全够用且代码更短。只有在极端数据或对性能有严苛要求的场景下如频繁合并与查询才需要使用“路径压缩按秩合并”的完全优化版。PAT和CSP的常规题目简易版足矣。并查集的一个常见变种是维护“到根节点距离”的带权并查集用于解决种类问题如食物链这需要额外维护一个distance数组并在find和unionSet中更新。这属于进阶模板建议在掌握基础后专门练习。3.2 图论基石Dijkstra最短路径算法的邻接表实现Dijkstra算法用于求解非负权图的单源最短路径。其堆优化版本是必须掌握的模板。模板代码C使用优先队列小顶堆#include vector #include queue #include climits using namespace std; typedef pairint, int PII; // first: 距离, second: 节点编号 vectorint dijkstra(int n, vectorvectorPII graph, int start) { vectorint dist(n, INT_MAX); // 存储起点到所有点的最短距离 dist[start] 0; priority_queuePII, vectorPII, greaterPII pq; // 小顶堆 pq.emplace(0, start); while (!pq.empty()) { auto [curDist, u] pq.top(); // C17 结构化绑定 pq.pop(); // 关键如果当前取出的距离大于记录的距离说明是旧数据直接跳过 if (curDist dist[u]) continue; for (auto [v, weight] : graph[u]) { // 遍历u的所有邻接点 int nextDist curDist weight; if (nextDist dist[v]) { dist[v] nextDist; pq.emplace(nextDist, v); } } } return dist; // 如果 dist[t] INT_MAX说明起点无法到达t点 }要点与避坑指南图的存储graph是一个邻接表graph[u]存储的是从u出发的所有边每个元素是{v, weight}。这种存储方式对于稀疏图非常高效。优先队列的使用使用priority_queuePII, vectorPII, greaterPII定义一个小顶堆确保每次取出的都是当前已知距离最小的节点。这是算法效率O(E log V)的保证。旧数据跳过if (curDist dist[u]) continue;这行代码至关重要。因为同一个节点可能被多次加入堆中每次找到更短距离时这条语句可以过滤掉那些已经过时的、距离较大的记录避免无效操作。初始化与返回值距离数组dist初始化为一个极大值如INT_MAX起点距离为0。函数返回dist数组调用者需自行判断终点是否可达。负权边禁忌Dijkstra算法不能处理含有负权边的图因为其贪心策略会失效。遇到负权边应考虑SPFA或Bellman-Ford算法。个人优化技巧在一些卡常数的题目中使用scanf/printf输入图数据会比cin快很多。如果节点编号从1开始记得将n传入n1并调整循环范围。对于超大规模图如n 1e5可以考虑使用vectorvectorpairint, int的存储方式但要注意初始化时指定大小以避免频繁扩容graph.resize(n);。3.3 二分查找的“万能”模板与边界处理二分查找思想简单但边界条件极易写错。一个清晰的模板能拯救无数调试时间。模板代码查找有序数组中第一个 target 的元素位置// 在升序数组 nums 中查找返回第一个大于等于 target 的元素的索引。 // 如果所有元素都小于 target则返回 nums.size()。 int lower_bound(vectorint nums, int target) { int left 0, right nums.size(); // 注意right 初始为 n区间为 [left, right) while (left right) { // 区间不为空时继续 int mid left (right - left) / 2; // 防止溢出 if (nums[mid] target) { right mid; // 目标在左半部分缩小右边界 } else { left mid 1; // 目标在右半部分缩小左边界 } } return left; // 此时 left right即为所求位置 }为什么这个模板好区间定义清晰使用左闭右开区间[left, right)。这意味着搜索范围包含left但不包含right。这种定义使得循环条件left right非常自然终止时left right这个位置就是答案。中间值计算安全mid left (right - left) / 2避免了(left right) / 2可能导致的整数溢出。分支明确if (nums[mid] target)说明mid可能是一个候选答案因为我们要找第一个target的但左边可能还有所以将搜索区间调整为[left, mid)即right mid。else说明mid肯定不是答案答案在右边所以调整为[mid1, right)即left mid 1。变体与记忆口诀查找第一个 target 的位置将条件if (nums[mid] target)改为if (nums[mid] target)。这个函数通常叫upper_bound。查找最后一个 target 的位置可以利用lower_bound的结果减一得到如果存在。口诀“ 找左界 找右界区间左闭右开循环小于更新看条件”。常见错误循环条件写成left right但更新时right mid - 1或left mid 1容易混淆区间开闭导致死循环或漏解。忘记处理目标值不存在的情况。本模板中如果target大于所有元素返回值left将等于nums.size()这是一个“越界”的合法索引调用者需要检查。4. 模板的实战应用与调试技巧4.1 如何将模板“组装”成解题代码以一道经典的图论问题为例“城市间最短路径”。题目描述给定n个城市节点和m条双向道路边每条道路有长度边权。求从城市s到城市t的最短路径长度。n最大为1e5m最大为2e5。解题步骤与模板组装问题识别明显的单源最短路问题边权非负节点和边数量级大 - 使用Dijkstra堆优化模板。数据输入与存储使用邻接表存图模板。调用核心算法传入参数获取dist数组。输出结果检查dist[t]是否为无穷大并输出。完整代码框架#include iostream #include vector #include queue #include climits using namespace std; typedef pairint, int PII; vectorint dijkstra(int n, vectorvectorPII graph, int start) { // ... 插入上述Dijkstra模板代码 ... } int main() { int n, m, s, t; scanf(%d %d %d %d, n, m, s, t); s--; t--; // 如果题目城市编号从1开始通常转为0-based vectorvectorPII graph(n); for (int i 0; i m; i) { int u, v, w; scanf(%d %d %d, u, v, w); u--; v--; graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); // 无向图双向加边 } vectorint dist dijkstra(n, graph, s); if (dist[t] INT_MAX) { printf(-1\n); // 不可达 } else { printf(%d\n, dist[t]); } return 0; }组装心得接口匹配确保你的模板输入输出与题目要求一致。例如Dijkstra模板返回整个dist数组而题目只问s到t的距离这并不冲突直接取用即可。数据预处理注意题目输入的节点编号习惯通常从1开始而我们的模板习惯从0开始在读入后立即进行--转换是一个好习惯。资源清理对于C如果题目有多组测试数据切记在每组开始时清空graph等全局数据结构否则会上组数据残留导致错误。4.2 模板的调试与验证如何确保你的模板是对的再好的模板如果本身有bug也是灾难。在将其纳入你的“武器库”前必须经过充分测试。1. 单元测试法 为每个核心模板编写简单的测试程序。例如测试并查集void testDSU() { DSU dsu(5); dsu.unionSet(0, 1); dsu.unionSet(2, 3); assert(dsu.connected(0, 1) true); assert(dsu.connected(0, 2) false); dsu.unionSet(1, 2); assert(dsu.connected(0, 3) true); cout DSU test passed! endl; }使用assert断言关键功能确保合并和查询操作正确。2. 对拍法 对于有明确暴力解法通常复杂度高但正确性易保证的问题可以用模板生成的代码与暴力代码对拍。步骤 a. 写一个数据生成器随机生成符合题目限制的输入。 b. 写一个暴力求解程序保证正确如用Floyd算法求最短路。 c. 写一个使用模板的快速求解程序。 d. 运行脚本让生成器不断生成随机数据分别用暴力程序和模板程序求解对比结果。工具在Windows下可以用批处理在Linux/Mac或在线IDE可以用简单的Shell脚本或Python脚本控制。3. 边界条件测试 专门针对模板的边界设计输入。并查集测试只有一个元素的情况测试反复合并同一对元素的情况。Dijkstra测试只有一个节点的图测试起点终点相同的情况测试存在重边的情况。二分查找测试空数组测试目标值小于最小值、大于最大值、等于某个值、不存在但处于中间值的情况。4. 线上OJ验证 找一些只考察该模板基本用法的“裸题”进行提交。例如洛谷的P3367【模板】并查集、P4779【模板】单源最短路径标准版。ACAccepted是模板正确性的最终证明。5. 模板的个性化管理与高效使用5.1 模板的组织与存储从零散到系统当模板数量增多后有效的管理能极大提升检索和使用效率。1. 按算法分类存储 在本地建立一个代码库文件夹结构如下Code_Templates/ ├── 01_Basic/ │ ├── fast_io.cpp // 快速输入输出 │ ├── binary_search.cpp // 二分查找 │ └── sort.cpp // 排序相关 ├── 02_Data_Structure/ │ ├── dsu.cpp // 并查集 │ ├── fenwick.cpp // 树状数组 │ └── segment_tree.cpp // 线段树 ├── 03_Graph/ │ ├── dijkstra.cpp │ ├── kruskal.cpp │ └── topological_sort.cpp ├── 04_Dynamic_Programming/ │ └── knapsack.cpp // 背包模板 └── 05_Math/ ├── quick_pow.cpp └── sieve.cpp // 素数筛每个.cpp文件是一个独立的、可编译的单元包含该算法的完整实现和简要注释。2. 使用代码片段管理工具VS Code利用用户代码片段功能为每个模板设置一个触发前缀。例如输入dsu然后按Tab自动展开完整的并查集代码。Sublime Text / CLion类似地都有强大的代码片段或实时模板功能。在线笔记使用 Notion、语雀等工具建立模板库支持代码高亮和分类检索方便跨设备查看。3. 制作“头文件”合集 对于C选手可以将所有常用模板整合进一个或多个.h头文件中。在比赛开始前直接将这个头文件包含进代码。但需注意这可能会增加编译时间且如果模板之间有依赖关系需要仔细处理。更常见的做法是只整合最核心、最通用的几个模板如快速读入、宏定义。5.2 比赛中的模板使用策略速度与准确性的博弈1. 赛前准备打印纸质版对于最重要的模板如Dijkstra、线段树可以打印出来带在身边作为参考。但最终目标是熟记于心。环境配置在比赛用的IDE中提前配置好代码片段并测试其展开是否正确。2. 赛中决策优先使用最熟悉的模板不要为了追求“更优”的写法而临场改用生疏的模板。你练习时敲过上百遍的模板才是你最可靠的伙伴。“填空式”编程读题后先确定需要哪些算法模块。然后在代码框架中像填空一样插入对应的模板函数。先保证主干正确再补充题目特有的输入输出和逻辑处理。模板的微调模板不是一成不变的。可能需要根据题目修改数据结构存储的信息如线段树维护的和、最值等或调整算法的细节如Dijkstra中距离的比较方式。修改时务必集中精力一次只改一个地方并立即在脑中或草稿上演算其正确性。3. 调试模板相关错误 如果怀疑是模板本身导致WAWrong Answer或RERuntime Error按以下步骤排查静态检查再次仔细阅读模板代码特别是循环条件、边界更新、初始化语句。小数据测试构造一个能用笔算得出结果的小样例用你的程序跑一遍逐行输出中间变量如dist数组的变化与你的笔算过程对比。替换法如果时间允许用一个你绝对信任的、AC过的简单程序中的同功能模板替换当前模板看是否通过。这能快速定位问题是否在模板。常见陷阱全局变量未初始化多组数据时忘记在每组开头清空全局的vector或数组。数组越界模板中申请的空间大小与题目输入的n不匹配特别是0-based和1-based混用导致访问n索引。无穷大设置不当最短路中将INF设为0x3f3f3f3f约10^9是一个安全且常用的选择因为它满足INF INF不会溢出int。如果使用INT_MAX在做加法时如dist[u] weight可能溢出变成负数。5.3 从使用模板到理解模板内化与超越模板的终极目的不是让你死记硬背而是帮助你跨越实现的鸿沟最终深刻理解算法本身。1. 分阶段学习第一阶段抄写与使用。初期可以完全照搬一个可靠的模板在简单题目中反复使用熟悉其接口和效果。第二阶段逐行解读。对模板中的每一行代码提问为什么这么写这行代码删了会怎样这个变量是什么意思尝试给模板加上详细的注释。第三阶段手动推导。合上模板尝试在白板上从零开始实现这个算法。卡住时回顾模板的关键步骤。直到你能独立、正确地写出来。第四阶段变通与创造。遇到问题变体时如边权有零、需要输出路径知道如何修改模板来适应。甚至能根据新的问题设计新的数据结构或算法框架。2. 参与模板建设 不要只做模板的使用者尝试做贡献者。当你发现某个模板有更优雅的实现、更快的常数、更清晰的逻辑时动手改进它。或者为你所在的团队如ACM队维护一份共用的模板库制定规范定期 review 和更新。这个过程本身就是对算法和编程能力的极大锻炼。一份好的代码模板是竞赛路上最忠实的伙伴。它凝结了前人的智慧和你自己的汗水。希望这份超详细的指南不仅能给你一套可用的“兵器”更能让你理解打造和维护这些“兵器”的方法论。在紧张的赛场上当别人还在为调试基础算法焦头烂额时你已凭借可靠的模板库从容地迈向更富挑战性的问题建模与优化。这就是模板的力量。本文还有配套的精品资源点击获取 算法竞赛代码模板：从Dijkstra到并查集，构建你的编程武器库
简介本资源是面向OI、ACM、PAT、CSP等编程竞赛选手的高频代码模板合集聚焦算法竞赛中反复出现的核心问题求解范式助力参赛者在限时环境下快速构建正确、高效、可复用的代码框架。压缩包共53个文件以41份Markdown文档系统讲解算法原理与实现要点和11个C源码文件含快读、KMP、Dijkstra、并查集、线段树等关键模板为主体辅以.gitignore配置总容量仅51KB轻量易集成。已有740人学习下载覆盖从入门到进阶的备赛需求。内容按模块结构化组织涵盖基础算法排序、二分、前缀和、动态规划背包、区间DP、图论最短路径、强连通、最小生成树、数学快速幂、欧拉函数、组合数、字符串Trie、Manacher、数据结构堆、平衡树、并查集及计算几何与位运算等十大方向每类均提供可直接调试的代码清晰注释典型应用场景说明。1. 项目概述为什么你需要一份“代码模板”如果你正在准备信息学奥赛OI、在线评测OJ、ACM国际大学生程序设计竞赛ACM、浙江大学计算机程序设计能力考试PAT或者中国计算机学会的软件能力认证CSP那么你大概率经历过这样的场景比赛或考试时间分秒流逝你面对一道题目思路清晰但敲代码时却卡在了如何快速实现一个“并查集”或者“Dijkstra最短路算法”上。手动实现不仅容易出错调试起来更是耗时。这时一份经过千锤百炼、可以直接“填空”的代码模板就成了你手中最锋利的武器。这份“常用代码模板”项目本质上是一个针对上述五大高频竞赛/认证场景的“算法实现工具箱”。它不是一个简单的代码片段合集而是一套经过实战检验的、模块化的、即插即用的解决方案库。其核心价值在于将比赛中那些思想经典但实现繁琐的算法封装成高度可靠、接口清晰的函数或类。选手在解题时无需再从零推导算法细节只需理解模板的输入输出含义便能将主要精力集中于问题建模和逻辑设计上从而在时间紧迫的竞赛环境中抢占先机。简单来说它解决的是“重复造轮子”和“临场实现易错”两大痛点。无论是初学者希望有一个可靠的学习参照还是资深选手追求极致的编码速度与准确性这样一份模板都至关重要。接下来我将为你深度拆解如何构建、使用并优化属于你自己的竞赛代码模板库。2. 模板库的整体架构与设计哲学2.1 核心设计原则模块化、鲁棒性与可读性的平衡构建一个优秀的模板库首先需要明确设计原则。这绝非简单的代码堆砌。1. 模块化与高内聚每个模板应独立解决一个明确的算法问题。例如“快速排序”是一个模板“线段树区间查询与修改”是另一个模板。模板之间尽量减少耦合通过清晰的接口函数参数、类公有方法进行交互。这样在解决复杂问题时你可以像搭积木一样组合多个模板。2. 鲁棒性优先竞赛代码没有第二次机会。模板必须能处理各种边界情况。例如图的邻接表存储模板要能处理重边和自环如果算法允许二分查找模板要能清晰定义搜索区间[left, right]是左闭右开还是左闭右闭并确保循环终止条件正确不会死循环。一个健壮的模板其正确性不应依赖于特定的数据特点。3. 效率与可读性的权衡竞赛环境追求极限效率但过于晦涩的“奇技淫巧”会大幅增加调试和维护成本。我的原则是在保证可读性的前提下进行优化。例如使用scanf/printf而非cin/cout处理大量输入输出是必要的优化但为了微小的性能提升将一段清晰的循环改为难以理解的位运算或宏定义则需谨慎。模板的终极目标是帮你快速写出正确的代码而不是炫耀技巧。4. 统一的代码风格与注释统一的变量命名如n代表数据规模g代表图、一致的缩进和空格、关键步骤的简明注释这些都能让你在紧张比赛中快速定位和理解模板。建议为每个模板编写简要的使用说明包括功能、时间复杂度、输入格式和输出格式。2.2 内容范畴规划覆盖五大场景的算法频谱不同的竞赛侧重点略有不同模板库需要全面覆盖OI/OJ/ACM这三者高度重叠侧重于经典算法与数据结构。模板库的核心应包括基础算法排序、二分、前缀和、差分、双指针。数据结构数组模拟链表、栈、队列、堆、并查集、树状数组、线段树、Trie树、ST表。图论邻接表存图、DFS/BFS、拓扑排序、最短路Dijkstra, SPFA, Floyd、最小生成树Kruskal, Prim、最近公共祖先LCA、网络流Dinic。数学快速幂、素数筛、最大公约数、组合数计算、矩阵快速幂。动态规划背包模板、线性DP、区间DP、树形DP的常用框架。字符串KMP、字符串哈希。PAT除了上述算法PAT更注重实际工程能力的考察因此需补充STL的熟练运用vector,map,set,string的常用操作模板化片段。排序与查找复杂结构体的多级排序sort自定义cmp。模拟题常用技巧日期处理、进制转换、多项式运算等“琐碎但易错”的代码块。CSP认证CSP题目难度跨度大且近年倾向于考察思维和建模能力。除了经典算法模板还应准备大整数运算CSP中有时会超出long long范围需要高精度加减乘除的模板。复杂模拟状态机、事件驱动模拟的框架代码。搜索优化剪枝技巧的常用模式可行性剪枝、最优性剪枝。注意模板不是越多越好而是越精越好。优先掌握和打磨那些在历年真题中出现频率最高的“王牌模板”如并查集、Dijkstra、快速排序、二分查找。一个你能闭着眼睛写对的简单模板远胜于十个你半懂不懂的复杂模板。3. 核心模板深度解析与实现要点3.1 数据结构之王并查集模板的三种写法与优化并查集是解决元素分组、连通性问题的神器。其模板的健壮性至关重要。基础模板路径压缩class DSU { private: vectorint parent; public: DSU(int n) : parent(n) { for (int i 0; i n; i) parent[i] i; // 初始化每个元素的父节点是自己 } // 查找根节点含路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩路径 } return parent[x]; } // 合并两个集合 void unionSet(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootY] rootX; // 将y的根节点接到x的根节点下 } } // 判断两个元素是否在同一集合 bool connected(int x, int y) { return find(x) find(y); } };要点解析路径压缩find函数中的递归操作parent[x] find(parent[x])使得后续查找同一节点的复杂度接近O(1)。这是模板效率的关键。初始化务必在构造函数中完成每个元素自成一集的初始化。合并策略上述是最简单的合并未按秩优化。在数据倾斜严重时树可能退化成链虽然路径压缩能缓解但并非最优。优化模板路径压缩 按秩合并 按秩合并通过记录树的深度或大小总是将较矮的树连接到较高的树上从而保证树的高度增长缓慢。class DSU { private: vectorint parent, rank; // rank可理解为树高的上界 public: DSU(int n) : parent(n), rank(n, 0) { // 初始高度为0 for (int i 0; i n; i) parent[i] i; } int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } void unionSet(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { // 两树同高任意合并但合并后树高1 parent[rootY] rootX; rank[rootX]; } } };实操心得在绝大多数OJ题目中只使用路径压缩的简易版完全够用且代码更短。只有在极端数据或对性能有严苛要求的场景下如频繁合并与查询才需要使用“路径压缩按秩合并”的完全优化版。PAT和CSP的常规题目简易版足矣。并查集的一个常见变种是维护“到根节点距离”的带权并查集用于解决种类问题如食物链这需要额外维护一个distance数组并在find和unionSet中更新。这属于进阶模板建议在掌握基础后专门练习。3.2 图论基石Dijkstra最短路径算法的邻接表实现Dijkstra算法用于求解非负权图的单源最短路径。其堆优化版本是必须掌握的模板。模板代码C使用优先队列小顶堆#include vector #include queue #include climits using namespace std; typedef pairint, int PII; // first: 距离, second: 节点编号 vectorint dijkstra(int n, vectorvectorPII graph, int start) { vectorint dist(n, INT_MAX); // 存储起点到所有点的最短距离 dist[start] 0; priority_queuePII, vectorPII, greaterPII pq; // 小顶堆 pq.emplace(0, start); while (!pq.empty()) { auto [curDist, u] pq.top(); // C17 结构化绑定 pq.pop(); // 关键如果当前取出的距离大于记录的距离说明是旧数据直接跳过 if (curDist dist[u]) continue; for (auto [v, weight] : graph[u]) { // 遍历u的所有邻接点 int nextDist curDist weight; if (nextDist dist[v]) { dist[v] nextDist; pq.emplace(nextDist, v); } } } return dist; // 如果 dist[t] INT_MAX说明起点无法到达t点 }要点与避坑指南图的存储graph是一个邻接表graph[u]存储的是从u出发的所有边每个元素是{v, weight}。这种存储方式对于稀疏图非常高效。优先队列的使用使用priority_queuePII, vectorPII, greaterPII定义一个小顶堆确保每次取出的都是当前已知距离最小的节点。这是算法效率O(E log V)的保证。旧数据跳过if (curDist dist[u]) continue;这行代码至关重要。因为同一个节点可能被多次加入堆中每次找到更短距离时这条语句可以过滤掉那些已经过时的、距离较大的记录避免无效操作。初始化与返回值距离数组dist初始化为一个极大值如INT_MAX起点距离为0。函数返回dist数组调用者需自行判断终点是否可达。负权边禁忌Dijkstra算法不能处理含有负权边的图因为其贪心策略会失效。遇到负权边应考虑SPFA或Bellman-Ford算法。个人优化技巧在一些卡常数的题目中使用scanf/printf输入图数据会比cin快很多。如果节点编号从1开始记得将n传入n1并调整循环范围。对于超大规模图如n 1e5可以考虑使用vectorvectorpairint, int的存储方式但要注意初始化时指定大小以避免频繁扩容graph.resize(n);。3.3 二分查找的“万能”模板与边界处理二分查找思想简单但边界条件极易写错。一个清晰的模板能拯救无数调试时间。模板代码查找有序数组中第一个 target 的元素位置// 在升序数组 nums 中查找返回第一个大于等于 target 的元素的索引。 // 如果所有元素都小于 target则返回 nums.size()。 int lower_bound(vectorint nums, int target) { int left 0, right nums.size(); // 注意right 初始为 n区间为 [left, right) while (left right) { // 区间不为空时继续 int mid left (right - left) / 2; // 防止溢出 if (nums[mid] target) { right mid; // 目标在左半部分缩小右边界 } else { left mid 1; // 目标在右半部分缩小左边界 } } return left; // 此时 left right即为所求位置 }为什么这个模板好区间定义清晰使用左闭右开区间[left, right)。这意味着搜索范围包含left但不包含right。这种定义使得循环条件left right非常自然终止时left right这个位置就是答案。中间值计算安全mid left (right - left) / 2避免了(left right) / 2可能导致的整数溢出。分支明确if (nums[mid] target)说明mid可能是一个候选答案因为我们要找第一个target的但左边可能还有所以将搜索区间调整为[left, mid)即right mid。else说明mid肯定不是答案答案在右边所以调整为[mid1, right)即left mid 1。变体与记忆口诀查找第一个 target 的位置将条件if (nums[mid] target)改为if (nums[mid] target)。这个函数通常叫upper_bound。查找最后一个 target 的位置可以利用lower_bound的结果减一得到如果存在。口诀“ 找左界 找右界区间左闭右开循环小于更新看条件”。常见错误循环条件写成left right但更新时right mid - 1或left mid 1容易混淆区间开闭导致死循环或漏解。忘记处理目标值不存在的情况。本模板中如果target大于所有元素返回值left将等于nums.size()这是一个“越界”的合法索引调用者需要检查。4. 模板的实战应用与调试技巧4.1 如何将模板“组装”成解题代码以一道经典的图论问题为例“城市间最短路径”。题目描述给定n个城市节点和m条双向道路边每条道路有长度边权。求从城市s到城市t的最短路径长度。n最大为1e5m最大为2e5。解题步骤与模板组装问题识别明显的单源最短路问题边权非负节点和边数量级大 - 使用Dijkstra堆优化模板。数据输入与存储使用邻接表存图模板。调用核心算法传入参数获取dist数组。输出结果检查dist[t]是否为无穷大并输出。完整代码框架#include iostream #include vector #include queue #include climits using namespace std; typedef pairint, int PII; vectorint dijkstra(int n, vectorvectorPII graph, int start) { // ... 插入上述Dijkstra模板代码 ... } int main() { int n, m, s, t; scanf(%d %d %d %d, n, m, s, t); s--; t--; // 如果题目城市编号从1开始通常转为0-based vectorvectorPII graph(n); for (int i 0; i m; i) { int u, v, w; scanf(%d %d %d, u, v, w); u--; v--; graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); // 无向图双向加边 } vectorint dist dijkstra(n, graph, s); if (dist[t] INT_MAX) { printf(-1\n); // 不可达 } else { printf(%d\n, dist[t]); } return 0; }组装心得接口匹配确保你的模板输入输出与题目要求一致。例如Dijkstra模板返回整个dist数组而题目只问s到t的距离这并不冲突直接取用即可。数据预处理注意题目输入的节点编号习惯通常从1开始而我们的模板习惯从0开始在读入后立即进行--转换是一个好习惯。资源清理对于C如果题目有多组测试数据切记在每组开始时清空graph等全局数据结构否则会上组数据残留导致错误。4.2 模板的调试与验证如何确保你的模板是对的再好的模板如果本身有bug也是灾难。在将其纳入你的“武器库”前必须经过充分测试。1. 单元测试法 为每个核心模板编写简单的测试程序。例如测试并查集void testDSU() { DSU dsu(5); dsu.unionSet(0, 1); dsu.unionSet(2, 3); assert(dsu.connected(0, 1) true); assert(dsu.connected(0, 2) false); dsu.unionSet(1, 2); assert(dsu.connected(0, 3) true); cout DSU test passed! endl; }使用assert断言关键功能确保合并和查询操作正确。2. 对拍法 对于有明确暴力解法通常复杂度高但正确性易保证的问题可以用模板生成的代码与暴力代码对拍。步骤 a. 写一个数据生成器随机生成符合题目限制的输入。 b. 写一个暴力求解程序保证正确如用Floyd算法求最短路。 c. 写一个使用模板的快速求解程序。 d. 运行脚本让生成器不断生成随机数据分别用暴力程序和模板程序求解对比结果。工具在Windows下可以用批处理在Linux/Mac或在线IDE可以用简单的Shell脚本或Python脚本控制。3. 边界条件测试 专门针对模板的边界设计输入。并查集测试只有一个元素的情况测试反复合并同一对元素的情况。Dijkstra测试只有一个节点的图测试起点终点相同的情况测试存在重边的情况。二分查找测试空数组测试目标值小于最小值、大于最大值、等于某个值、不存在但处于中间值的情况。4. 线上OJ验证 找一些只考察该模板基本用法的“裸题”进行提交。例如洛谷的P3367【模板】并查集、P4779【模板】单源最短路径标准版。ACAccepted是模板正确性的最终证明。5. 模板的个性化管理与高效使用5.1 模板的组织与存储从零散到系统当模板数量增多后有效的管理能极大提升检索和使用效率。1. 按算法分类存储 在本地建立一个代码库文件夹结构如下Code_Templates/ ├── 01_Basic/ │ ├── fast_io.cpp // 快速输入输出 │ ├── binary_search.cpp // 二分查找 │ └── sort.cpp // 排序相关 ├── 02_Data_Structure/ │ ├── dsu.cpp // 并查集 │ ├── fenwick.cpp // 树状数组 │ └── segment_tree.cpp // 线段树 ├── 03_Graph/ │ ├── dijkstra.cpp │ ├── kruskal.cpp │ └── topological_sort.cpp ├── 04_Dynamic_Programming/ │ └── knapsack.cpp // 背包模板 └── 05_Math/ ├── quick_pow.cpp └── sieve.cpp // 素数筛每个.cpp文件是一个独立的、可编译的单元包含该算法的完整实现和简要注释。2. 使用代码片段管理工具VS Code利用用户代码片段功能为每个模板设置一个触发前缀。例如输入dsu然后按Tab自动展开完整的并查集代码。Sublime Text / CLion类似地都有强大的代码片段或实时模板功能。在线笔记使用 Notion、语雀等工具建立模板库支持代码高亮和分类检索方便跨设备查看。3. 制作“头文件”合集 对于C选手可以将所有常用模板整合进一个或多个.h头文件中。在比赛开始前直接将这个头文件包含进代码。但需注意这可能会增加编译时间且如果模板之间有依赖关系需要仔细处理。更常见的做法是只整合最核心、最通用的几个模板如快速读入、宏定义。5.2 比赛中的模板使用策略速度与准确性的博弈1. 赛前准备打印纸质版对于最重要的模板如Dijkstra、线段树可以打印出来带在身边作为参考。但最终目标是熟记于心。环境配置在比赛用的IDE中提前配置好代码片段并测试其展开是否正确。2. 赛中决策优先使用最熟悉的模板不要为了追求“更优”的写法而临场改用生疏的模板。你练习时敲过上百遍的模板才是你最可靠的伙伴。“填空式”编程读题后先确定需要哪些算法模块。然后在代码框架中像填空一样插入对应的模板函数。先保证主干正确再补充题目特有的输入输出和逻辑处理。模板的微调模板不是一成不变的。可能需要根据题目修改数据结构存储的信息如线段树维护的和、最值等或调整算法的细节如Dijkstra中距离的比较方式。修改时务必集中精力一次只改一个地方并立即在脑中或草稿上演算其正确性。3. 调试模板相关错误 如果怀疑是模板本身导致WAWrong Answer或RERuntime Error按以下步骤排查静态检查再次仔细阅读模板代码特别是循环条件、边界更新、初始化语句。小数据测试构造一个能用笔算得出结果的小样例用你的程序跑一遍逐行输出中间变量如dist数组的变化与你的笔算过程对比。替换法如果时间允许用一个你绝对信任的、AC过的简单程序中的同功能模板替换当前模板看是否通过。这能快速定位问题是否在模板。常见陷阱全局变量未初始化多组数据时忘记在每组开头清空全局的vector或数组。数组越界模板中申请的空间大小与题目输入的n不匹配特别是0-based和1-based混用导致访问n索引。无穷大设置不当最短路中将INF设为0x3f3f3f3f约10^9是一个安全且常用的选择因为它满足INF INF不会溢出int。如果使用INT_MAX在做加法时如dist[u] weight可能溢出变成负数。5.3 从使用模板到理解模板内化与超越模板的终极目的不是让你死记硬背而是帮助你跨越实现的鸿沟最终深刻理解算法本身。1. 分阶段学习第一阶段抄写与使用。初期可以完全照搬一个可靠的模板在简单题目中反复使用熟悉其接口和效果。第二阶段逐行解读。对模板中的每一行代码提问为什么这么写这行代码删了会怎样这个变量是什么意思尝试给模板加上详细的注释。第三阶段手动推导。合上模板尝试在白板上从零开始实现这个算法。卡住时回顾模板的关键步骤。直到你能独立、正确地写出来。第四阶段变通与创造。遇到问题变体时如边权有零、需要输出路径知道如何修改模板来适应。甚至能根据新的问题设计新的数据结构或算法框架。2. 参与模板建设 不要只做模板的使用者尝试做贡献者。当你发现某个模板有更优雅的实现、更快的常数、更清晰的逻辑时动手改进它。或者为你所在的团队如ACM队维护一份共用的模板库制定规范定期 review 和更新。这个过程本身就是对算法和编程能力的极大锻炼。一份好的代码模板是竞赛路上最忠实的伙伴。它凝结了前人的智慧和你自己的汗水。希望这份超详细的指南不仅能给你一套可用的“兵器”更能让你理解打造和维护这些“兵器”的方法论。在紧张的赛场上当别人还在为调试基础算法焦头烂额时你已凭借可靠的模板库从容地迈向更富挑战性的问题建模与优化。这就是模板的力量。本文还有配套的精品资源点击获取