简介面向备战ICPC、CCPC、蓝桥杯及考研机试的算法竞赛学习者整理了一份覆盖动态规划、图论、搜索、数学、数据结构等核心专题的C代码学习仓库。资源汇总了ACWing、CodeForces、Contest Hunter等多个在线评测平台的AC代码文件命名规范并配有参与者学习笔记便于按平台、题目或算法类型快速定位参考。压缩包内共916个文件以577个cc与289个cpp源码为主同时包含少量Kotlin、Python、Java多语言实现以及md笔记、makefile和辅助脚本整体仅1.03MB文件数量虽多但体量轻、结构清晰便于按需取用。可用于刷题复盘、模板速查和赛前系统复习尤其是推箱子、数独、线段树、区间最大公约数等经典竞赛题目均可找到对应AC代码与思路注释便于梳理不同解法的优化过程。目前已有84人学习下载适合ACMer与正在构建个人题单的读者直接借鉴复用减少从零整理代码的时间。 我最早学算法竞赛的时候题解写在Markdown里代码散落在各个文件夹里文件名从1.cpp、2.cpp一路膨胀到final_v2.cpp。过了两周自己都看不下去——不是代码写得不够快而是写完就丢了。下次遇到同类题又得翻开别人的题解重新开始。后来我把整整一个学期踩过的坑沉淀成了这份基于C的算法竞赛学习仓库每一个算法都有可以直接编译运行的源码每一个模板都标注了适用场景、复杂度、易错点每一份代码都带着我在比赛环境下的实测感受。这个仓库不是手机里的收藏夹而是一本能跑起来的算法书。如果你正在准备ACM/ICPC、蓝桥杯、Codeforces或LeetCode周赛或者只是想系统地把C语法、STL和常用数据结构扎扎实实过一遍这份仓库的思路都能直接抄走。下文我会把仓库的目录结构、源码细节、编译环境和踩坑经验全部摊开讲顺带解答一个很多人没想明白的问题——为什么收藏了那么多模板赛场上你还是写不出来。1. 为什么算法竞赛选手要维护自己的C源码仓库1.1 散装笔记解决不了的问题很多人觉得学习算法竞赛就是多看题解、多刷题于是笔记软件里囤了上百篇题解GitHub上Star了一堆算法模板可真到了比赛现场遇到一个需要并查集变式的题手还是停在键盘上脑子一片空白。问题出在哪看题解是输入抄代码是肌肉记忆而比赛需要的是输出和迁移。你要能在5分钟内把模板默写出来还要能判断这道题的模型虽然长了张二分图的脸但本质是带权并查集。这个过程没有捷径只能靠反复动手。C源码仓库的作用就是给动手提供一个明确的抓手——它不是收藏夹里的一堆链接而是你亲手写过、跑过、改过、批注过的代码合集。区别在于收藏夹只会越积越厚仓库则能在每次复习中不断变薄、变精。1.2 仓库、题解合集和算法笔记的根本区别网上能找到很多算法竞赛模板库一上来就是几百个文件按知识点堆得整整齐齐。但那种仓库是别人的不是你的。我见过太多人下载了模板库之后连编译都没编译过更别说理解每一行代码为什么这么写。一份真正属于你自己的C学习仓库至少要满足三个条件每个源文件都能直接编译运行而不是贴一段不完整的片段每段代码都带着注释写清楚适用场景、时间/空间复杂度、易错点每道例题都来自你实际做过的题目记下的是当时卡壳的原因和最终的解法思路。我这份仓库最初就是从这种朴素需求出发的。那时候我每天做完题会花十几分钟把当天的代码整理进对应的目录补上注释。坚持了一个月以后效果非常明显复习的时候不用再翻几十篇散落的题解只需要对着目录按图索骥一条线拉下来知识点之间的关联反而比当初零散学习时清晰得多。2. 仓库目录怎么组织才不会被自己嫌弃三维索引法2.1 目录结构按数据结构—算法—题型分层仓库的顶层目录我最初是按刷题网站来分的比如luogu、codeforces、nowcoder各建一个文件夹。后来发现这个设计很蠢因为同一个知识点会散落在三个不同文件夹里复习的时候要三头跑。后来我把目录彻底推翻改成按计算机科学的知识体系组织效果立竿见影algorithm-notes/ ├── 00_template/ # 竞赛通用模板快读快写、调试宏 ├── 01_basic/ # 基础语法与STLstring、vector、map ├── 02_data_structure/ # 线性表、栈、队列、并查集、树状数组 │ ├── union_find.cpp │ ├── fenwick_tree.cpp │ ├── segment_tree_lazy.cpp │ └── monotonic_stack.cpp ├── 03_algorithm/ # 排序、二分、双指针、贪心、动态规划 │ ├── binary_search.cpp │ ├── dp_knapsack.cpp │ └── dp_longest_increasing_subsequence.cpp ├── 04_graph/ # 图论最短路、最小生成树、拓扑排序 │ ├── dijkstra_heap.cpp │ ├── kruskal.cpp │ └── tarjan_scc.cpp ├── 05_math/ # 数论、组合数学 │ ├── qpow.cpp │ ├── prime_sieve.cpp │ └── matrix_qpow.cpp ├── 06_string/ # 字符串算法 │ └── kmp.cpp ├── 07_geometry/ # 计算几何 ├── 08_problem_sets/ # 按比赛/专题精选题解 ├── tools/ # 对拍脚本、数据生成器、运行脚本 └── README.md这套目录用三个维度帮你定位先确定这是什么数据结构或算法范式再确定这个知识点放在哪个知识模块最后通过08_problem_sets和题目编号做交叉引用。前三个月的学习内容基本落在01和02之后逐步向04、05、06扩散。目录本身就是一张学习路线图学到哪个阶段哪个目录就开始变厚很有成就感。2.2 代码文件头部的注释模板写给未来的自己代码文件名我倾向于用英文小写加下划线比如union_find.cpp、segment_tree_lazy.cpp这样在vscode里按文件名搜索的时候非常快。真正让仓库具备学习属性的是每个文件头部的注释块。我自己的模板长这样/* * 题目编号: P3378 【模板】二叉堆 * 考点: 堆、优先队列 * 思路: 用 priority_queueint, vectorint, greaterint 实现小根堆 * 复杂度: 每次操作为 O(logn) * 易错点: * 1. pop 前要判空 * 2. 优先队列默认是大根堆小根堆要指定 greater * 变体: 对顶堆可用于求动态中位数 */这段注释里最容易被忽略但又最有价值的是易错点和变体。易错点是你自己踩过的坑写下来能防止未来的自己重蹈覆辙变体则是举一反三的入口——比赛中很少直接考模板题考的大多是模板的变式把这个字段想清楚比多刷十道同类题更管用。3. 高频模板源码对抗单调栈、并查集、快速幂里的隐藏坑这一章我挑三个仓库里最高频的模板把源码贴出来顺便把C竞赛里最容易翻车的地方一并说透。这三个模板覆盖了线性结构维护单调栈、集合关系维护并查集和数值运算优化快速幂是算法竞赛里出场率最高的三类代码。3.1 单调栈为什么栈里存的是下标而不是值单调栈的经典应用是找每个数右边第一个比它大的数。暴力的做法是两重循环复杂度O(n^2)。单调栈的思路是维护一个从栈底到栈顶单调递减的栈遍历数组时当前元素不断把栈顶那些比它小的元素弹出去弹出去的元素的答案就是当前下标。// 返回 ans[i]nums[i] 右边第一个比它大的元素的下标不存在则为 -1 vectorint nextGreater(vectorint nums) { int n nums.size(); vectorint ans(n, -1); stackint st; // 栈里存下标 for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { ans[st.top()] i; st.pop(); } st.push(i); } return ans; }很多人第一次写单调栈会纠结栈里到底存值还是存下标我的经验是一律存下标。因为答案要写的是位置存值的话还得拿着值去原数组里反查下标多一次O(n)的遍历完全没有必要。另一个高频困惑是单调递增还是递减。这取决于题目要找的是下一个更大的数还是下一个更小的数。找更大的数时当前元素负责吃掉栈里所有比它小的元素所以从栈底到栈顶是递减的。复杂度方面每个元素最多进栈一次、出栈一次总复杂度O(n)这就是单调栈比暴力优雅的地方。3.2 并查集路径压缩和按秩合并必须一起上并查集是算法竞赛里没有之一的必备数据结构。维护集合的合并与查询均摊复杂度接近O(1)。但前提是同时做了路径压缩和按秩合并少一个都不行。const int N 100005; int fa[N], sz[N]; void init(int n) { for (int i 1; i n; i) { fa[i] i; sz[i] 1; } } int find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; // 路径压缩让 x 指向祖父节点 x fa[x]; } return x; } void merge(int a, int b) { a find(a); b find(b); if (a b) return; if (sz[a] sz[b]) swap(a, b); fa[b] a; sz[a] sz[b]; }这里我用了迭代版本的find而不是网上最常见的递归版本。原因有两个一是在数据规模上到10^6的时候递归深度可能接近链的长度虽然路径压缩已经把链压得很短但迭代版写起来并不复杂没有理由去赌递归安全二是迭代版的路径压缩写法fa[x] fa[fa[x]]采用的是压缩一半的策略实测在多数题里已经够用。merge函数的三个细节我要重点强调合并前必须调用find拿到两个集合的根节点然后合并根而不是合并传入的原始节点if (a b) return;必须写否则可能出现自己指向自己然后把集合大小翻倍的逻辑错误按秩合并指的是把小集合接在大集合下面。这里的秩可以用集合大小sz表示也可以用树高表示。用sz的好处是代码简单而且在路径压缩存在时sz比树高更能反映集合规模。3.3 快速幂long long 的溢出比你想的更容易翻车快速幂的原理是二进制分解指数在O(logn)时间内完成a^b的计算。C竞赛里最常见的写法如下using ll long long; ll qpow(ll a, ll b, ll mod) { ll res 1 % mod; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }这里有两个很容易踩的坑。第一res 1 % mod这个初始化形式很多人会写成res 1。如果mod恰好等于1所有数模1都是0res 1会导致返回值是1而不是0。虽然mod1这种数据很少见但出题人专门卡你的时候一行代码的差距就是AC和WA的距离。第二a a * a % mod这一步必须在乘完之后立刻取模。如果a本身已经接近10^9a * a会直接冲到10^18还在long long范围内可一旦mod接近10^18a * a就会溢出long long。这时候要么改用__int128做中间乘法要么实现快速乘用加法模拟乘法边加边取模来兜底。另外如果b是一个负数这段代码会直接出问题所以调用前务必保证b非负竞赛题里指数一般都会保证非负但自己写对拍生成数据时容易漏掉这个前提。3.4 C竞赛中我还专门写过一页避坑清单仓库的00_template目录下我放了一个cpp_pitfalls.cpp专门记录C语法层面的坑。下面这几条是从多场真实比赛中总结出来的建议你也建一个类似的文件bits/stdc.h是GCC编译器的私货Windows上的MSVC并没有它部分老在线评测系统也编译不过。我在仓库代码里一律用标准头文件列表为了跨平台省心。int溢出是最隐蔽的。题目里n和m都是10^5级别你一时大意写了int area n * m;两个int相乘直接溢出成负数答案错得莫名其妙的。凡是有乘法的地方先确认结果会不会超出int范围不行就转long long。移位运算符的优先级低于加减法。n 1 1会被解析成n (1 1)。想表达(n 1) 1括号必须打。vectorbool不是普通bool数组它是为了压内存做了bit特化的返回的元素是代理对象不是真正的bool。需要频繁修改元素或者想要bool*指针时用vectorint或者普通数组更省心。给sort写比较器时必须满足严格弱序return a b;是错的相等时必须返回false。这个错误在本地跑小数据不一定触发但到评测机大数据下就会变成段错误或者超时。4. 从源码到跑通编译环境、对拍与性能验证代码模板写得再好如果本地不能一键编译、不能自动验证正确性到了比赛现场还是会手忙脚乱。能跑是仓库的最低标准能验证才是它超越普通笔记的地方。4.1 vscode g 环境配置关键是那几条编译参数我平时在vscode里写Ctasks.json里的编译任务长这样{ version: 2.0.0, tasks: [ { label: cpp-build, type: cppbuild, command: /usr/bin/g, args: [ -g, -O2, -stdc17, -Wall, -Wextra, ${file}, -o, ${fileDirname}/${fileBasenameNoExtension} ], group: build, problemMatcher: [$gcc] } ] }几个参数说一下背后的原因。-stdc17是竞赛代码的主流标准大部分评测机已经支持C17的语法特性。-O2是竞赛标配优化等级本地不开O2就测不出真实的运行时间。-Wall -Wextra这两个警告选项很多新手不重视但我强烈建议打开因为它们能帮你提前发现变量未初始化有符号/无符号比较这类坑。-g保留调试信息方便gdb或者vscode的调试器打断点看变量。不过要注意开了O2之后变量可能被优化掉断点不生效的情况很常见。我自己的做法是日常调试时把-O2临时去掉等要提交前再用完整参数重新编译测一次最坏情况的运行时间。4.2 输入输出重定向本地测试和在线评测的缝合竞赛代码在评测机上通过标准输入读数据但本地手敲一堆测试数据很麻烦。我习惯在源码开头用freopen从文件读#ifdef LOCAL freopen(in.txt, r, stdin); freopen(out.txt, w, stdout); #endif提交的时候注释掉#define LOCAL即可。有些选手喜欢用#ifndef ONLINE_JUDGE判断在线评测环境但这个宏并不是所有OJ都有我自己只用LOCAL宏可控性更强。4.3 对拍脚本用随机数据验证正确性比瞪眼找bug效率高得多对拍是竞赛选手人手必备的调试手段思路是写一个一定正确但可能很慢的暴力程序再写一个待验证的高效程序用随机生成的数据同时跑比较输出是否一致。我把对拍脚本放进了仓库的tools目录Python版本如下import subprocess import random for i in range(1000): # 1. 生成随机小数据 with open(in.txt, w) as f: n random.randint(1, 10) f.write(str(n) \n) f.write( .join(str(random.randint(1, 100)) for _ in range(n))) # 2. 分别运行两个程序 with open(in.txt, r) as fin: subprocess.run([./sol], stdinfin, stdoutopen(out_sol.txt, w)) with open(in.txt, r) as fin: subprocess.run([./brute], stdinfin, stdoutopen(out_brute.txt, w)) # 3. 比较输出 sol open(out_sol.txt).read().strip() brute open(out_brute.txt).read().strip() if sol ! brute: print(error at case, i) break对拍的关键是数据范围要小保证暴力程序能在瞬间跑完。找到第一个不一致的case后把它缩到最小规模比如n3、数值范围1到5再用肉眼调试。这个过程能覆盖大量你靠手推根本发现不了的边界情况比如数组越界、重复元素、空输入。我自己的体验是一道卡了很久的WA题往往在对拍跑到第几十组数据时就现出原形比对着屏幕瞪半小时强得多。4.4 性能验证开O2测一次心里才有底跑题之前还是想提醒一句时间复杂度算得再漂亮也不如本地实测一次来得放心。仓库里我建议给每个重量级算法文件都记一笔实测数据——比如dijkstra_heap.cpp的注释里我会写在10^5个点、2×10^5条边的随机图上开O2约0.3s。这样下次比赛遇到类似规模的数据你不需要重新估算直接查注释就能知道这个模板能不能扛得住。5. 维护仓库一年后我总结的三条迭代经验5.1 模板不是写一次就完了每场赛题都在给它们打补丁我最早整理的并查集只有路径压缩没有按秩合并因为觉得路径压缩已经够快。直到有一场题目的数据专门构造了一条极深的链导致性能退化才意识到自己的模板有漏洞。从那以后每场比赛遇到超时或WA我复盘的第一件事就是这是不是仓库模板的问题如果是立刻回仓库改代码、补注释。仓库里的每一个文件都记录着我踩过的坑和打过的补丁这些是买不到的实战经验。5.2 复习不是看代码而是默写代码看一遍自己的模板觉得太简单了合上屏幕才发现连merge函数里先find根节点这种基础步骤都会漏。我给自己定了一个规则每两周挑几个仓库里的高频模板凭空在编辑器里默写一遍限时10分钟。写不出来的地方就是下一步需要重点复习的地方。这个方法听起来笨但效果显著——赛场上不会有代码提示默写能力才是真正的竞争力。5.3 仓库的价值指标只有一个赛场上能不能5分钟打出来这个指标比代码行数、Star数都更诚实。如果模板还需要现场翻笔记那它还不属于你。基于这个标准我每年都会做一次仓库瘦身把一年没用到的冷门模板移到archive目录把高频模板的注释精简到一眼扫完就能理解。删掉冗余内容后仓库反而变得更顺手了。这份C算法竞赛学习仓库从第一天的一个文件夹慢慢长成了现在能覆盖绝大多数竞赛知识点的完整体系。每次打开它看到的都是自己从零到一的学习轨迹。如果你也想建一份我的建议很简单不要想着一步到位搭一个大而全的架子从你刚做过的题开始整理进去写好注释坚持一个月你一定会回来感谢当时那个愿意多花十五分钟整理代码的自己。本文还有配套的精品资源点击获取 C++算法竞赛学习仓库：从模板整理到高效实战
简介面向备战ICPC、CCPC、蓝桥杯及考研机试的算法竞赛学习者整理了一份覆盖动态规划、图论、搜索、数学、数据结构等核心专题的C代码学习仓库。资源汇总了ACWing、CodeForces、Contest Hunter等多个在线评测平台的AC代码文件命名规范并配有参与者学习笔记便于按平台、题目或算法类型快速定位参考。压缩包内共916个文件以577个cc与289个cpp源码为主同时包含少量Kotlin、Python、Java多语言实现以及md笔记、makefile和辅助脚本整体仅1.03MB文件数量虽多但体量轻、结构清晰便于按需取用。可用于刷题复盘、模板速查和赛前系统复习尤其是推箱子、数独、线段树、区间最大公约数等经典竞赛题目均可找到对应AC代码与思路注释便于梳理不同解法的优化过程。目前已有84人学习下载适合ACMer与正在构建个人题单的读者直接借鉴复用减少从零整理代码的时间。 我最早学算法竞赛的时候题解写在Markdown里代码散落在各个文件夹里文件名从1.cpp、2.cpp一路膨胀到final_v2.cpp。过了两周自己都看不下去——不是代码写得不够快而是写完就丢了。下次遇到同类题又得翻开别人的题解重新开始。后来我把整整一个学期踩过的坑沉淀成了这份基于C的算法竞赛学习仓库每一个算法都有可以直接编译运行的源码每一个模板都标注了适用场景、复杂度、易错点每一份代码都带着我在比赛环境下的实测感受。这个仓库不是手机里的收藏夹而是一本能跑起来的算法书。如果你正在准备ACM/ICPC、蓝桥杯、Codeforces或LeetCode周赛或者只是想系统地把C语法、STL和常用数据结构扎扎实实过一遍这份仓库的思路都能直接抄走。下文我会把仓库的目录结构、源码细节、编译环境和踩坑经验全部摊开讲顺带解答一个很多人没想明白的问题——为什么收藏了那么多模板赛场上你还是写不出来。1. 为什么算法竞赛选手要维护自己的C源码仓库1.1 散装笔记解决不了的问题很多人觉得学习算法竞赛就是多看题解、多刷题于是笔记软件里囤了上百篇题解GitHub上Star了一堆算法模板可真到了比赛现场遇到一个需要并查集变式的题手还是停在键盘上脑子一片空白。问题出在哪看题解是输入抄代码是肌肉记忆而比赛需要的是输出和迁移。你要能在5分钟内把模板默写出来还要能判断这道题的模型虽然长了张二分图的脸但本质是带权并查集。这个过程没有捷径只能靠反复动手。C源码仓库的作用就是给动手提供一个明确的抓手——它不是收藏夹里的一堆链接而是你亲手写过、跑过、改过、批注过的代码合集。区别在于收藏夹只会越积越厚仓库则能在每次复习中不断变薄、变精。1.2 仓库、题解合集和算法笔记的根本区别网上能找到很多算法竞赛模板库一上来就是几百个文件按知识点堆得整整齐齐。但那种仓库是别人的不是你的。我见过太多人下载了模板库之后连编译都没编译过更别说理解每一行代码为什么这么写。一份真正属于你自己的C学习仓库至少要满足三个条件每个源文件都能直接编译运行而不是贴一段不完整的片段每段代码都带着注释写清楚适用场景、时间/空间复杂度、易错点每道例题都来自你实际做过的题目记下的是当时卡壳的原因和最终的解法思路。我这份仓库最初就是从这种朴素需求出发的。那时候我每天做完题会花十几分钟把当天的代码整理进对应的目录补上注释。坚持了一个月以后效果非常明显复习的时候不用再翻几十篇散落的题解只需要对着目录按图索骥一条线拉下来知识点之间的关联反而比当初零散学习时清晰得多。2. 仓库目录怎么组织才不会被自己嫌弃三维索引法2.1 目录结构按数据结构—算法—题型分层仓库的顶层目录我最初是按刷题网站来分的比如luogu、codeforces、nowcoder各建一个文件夹。后来发现这个设计很蠢因为同一个知识点会散落在三个不同文件夹里复习的时候要三头跑。后来我把目录彻底推翻改成按计算机科学的知识体系组织效果立竿见影algorithm-notes/ ├── 00_template/ # 竞赛通用模板快读快写、调试宏 ├── 01_basic/ # 基础语法与STLstring、vector、map ├── 02_data_structure/ # 线性表、栈、队列、并查集、树状数组 │ ├── union_find.cpp │ ├── fenwick_tree.cpp │ ├── segment_tree_lazy.cpp │ └── monotonic_stack.cpp ├── 03_algorithm/ # 排序、二分、双指针、贪心、动态规划 │ ├── binary_search.cpp │ ├── dp_knapsack.cpp │ └── dp_longest_increasing_subsequence.cpp ├── 04_graph/ # 图论最短路、最小生成树、拓扑排序 │ ├── dijkstra_heap.cpp │ ├── kruskal.cpp │ └── tarjan_scc.cpp ├── 05_math/ # 数论、组合数学 │ ├── qpow.cpp │ ├── prime_sieve.cpp │ └── matrix_qpow.cpp ├── 06_string/ # 字符串算法 │ └── kmp.cpp ├── 07_geometry/ # 计算几何 ├── 08_problem_sets/ # 按比赛/专题精选题解 ├── tools/ # 对拍脚本、数据生成器、运行脚本 └── README.md这套目录用三个维度帮你定位先确定这是什么数据结构或算法范式再确定这个知识点放在哪个知识模块最后通过08_problem_sets和题目编号做交叉引用。前三个月的学习内容基本落在01和02之后逐步向04、05、06扩散。目录本身就是一张学习路线图学到哪个阶段哪个目录就开始变厚很有成就感。2.2 代码文件头部的注释模板写给未来的自己代码文件名我倾向于用英文小写加下划线比如union_find.cpp、segment_tree_lazy.cpp这样在vscode里按文件名搜索的时候非常快。真正让仓库具备学习属性的是每个文件头部的注释块。我自己的模板长这样/* * 题目编号: P3378 【模板】二叉堆 * 考点: 堆、优先队列 * 思路: 用 priority_queueint, vectorint, greaterint 实现小根堆 * 复杂度: 每次操作为 O(logn) * 易错点: * 1. pop 前要判空 * 2. 优先队列默认是大根堆小根堆要指定 greater * 变体: 对顶堆可用于求动态中位数 */这段注释里最容易被忽略但又最有价值的是易错点和变体。易错点是你自己踩过的坑写下来能防止未来的自己重蹈覆辙变体则是举一反三的入口——比赛中很少直接考模板题考的大多是模板的变式把这个字段想清楚比多刷十道同类题更管用。3. 高频模板源码对抗单调栈、并查集、快速幂里的隐藏坑这一章我挑三个仓库里最高频的模板把源码贴出来顺便把C竞赛里最容易翻车的地方一并说透。这三个模板覆盖了线性结构维护单调栈、集合关系维护并查集和数值运算优化快速幂是算法竞赛里出场率最高的三类代码。3.1 单调栈为什么栈里存的是下标而不是值单调栈的经典应用是找每个数右边第一个比它大的数。暴力的做法是两重循环复杂度O(n^2)。单调栈的思路是维护一个从栈底到栈顶单调递减的栈遍历数组时当前元素不断把栈顶那些比它小的元素弹出去弹出去的元素的答案就是当前下标。// 返回 ans[i]nums[i] 右边第一个比它大的元素的下标不存在则为 -1 vectorint nextGreater(vectorint nums) { int n nums.size(); vectorint ans(n, -1); stackint st; // 栈里存下标 for (int i 0; i n; i) { while (!st.empty() nums[st.top()] nums[i]) { ans[st.top()] i; st.pop(); } st.push(i); } return ans; }很多人第一次写单调栈会纠结栈里到底存值还是存下标我的经验是一律存下标。因为答案要写的是位置存值的话还得拿着值去原数组里反查下标多一次O(n)的遍历完全没有必要。另一个高频困惑是单调递增还是递减。这取决于题目要找的是下一个更大的数还是下一个更小的数。找更大的数时当前元素负责吃掉栈里所有比它小的元素所以从栈底到栈顶是递减的。复杂度方面每个元素最多进栈一次、出栈一次总复杂度O(n)这就是单调栈比暴力优雅的地方。3.2 并查集路径压缩和按秩合并必须一起上并查集是算法竞赛里没有之一的必备数据结构。维护集合的合并与查询均摊复杂度接近O(1)。但前提是同时做了路径压缩和按秩合并少一个都不行。const int N 100005; int fa[N], sz[N]; void init(int n) { for (int i 1; i n; i) { fa[i] i; sz[i] 1; } } int find(int x) { while (fa[x] ! x) { fa[x] fa[fa[x]]; // 路径压缩让 x 指向祖父节点 x fa[x]; } return x; } void merge(int a, int b) { a find(a); b find(b); if (a b) return; if (sz[a] sz[b]) swap(a, b); fa[b] a; sz[a] sz[b]; }这里我用了迭代版本的find而不是网上最常见的递归版本。原因有两个一是在数据规模上到10^6的时候递归深度可能接近链的长度虽然路径压缩已经把链压得很短但迭代版写起来并不复杂没有理由去赌递归安全二是迭代版的路径压缩写法fa[x] fa[fa[x]]采用的是压缩一半的策略实测在多数题里已经够用。merge函数的三个细节我要重点强调合并前必须调用find拿到两个集合的根节点然后合并根而不是合并传入的原始节点if (a b) return;必须写否则可能出现自己指向自己然后把集合大小翻倍的逻辑错误按秩合并指的是把小集合接在大集合下面。这里的秩可以用集合大小sz表示也可以用树高表示。用sz的好处是代码简单而且在路径压缩存在时sz比树高更能反映集合规模。3.3 快速幂long long 的溢出比你想的更容易翻车快速幂的原理是二进制分解指数在O(logn)时间内完成a^b的计算。C竞赛里最常见的写法如下using ll long long; ll qpow(ll a, ll b, ll mod) { ll res 1 % mod; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }这里有两个很容易踩的坑。第一res 1 % mod这个初始化形式很多人会写成res 1。如果mod恰好等于1所有数模1都是0res 1会导致返回值是1而不是0。虽然mod1这种数据很少见但出题人专门卡你的时候一行代码的差距就是AC和WA的距离。第二a a * a % mod这一步必须在乘完之后立刻取模。如果a本身已经接近10^9a * a会直接冲到10^18还在long long范围内可一旦mod接近10^18a * a就会溢出long long。这时候要么改用__int128做中间乘法要么实现快速乘用加法模拟乘法边加边取模来兜底。另外如果b是一个负数这段代码会直接出问题所以调用前务必保证b非负竞赛题里指数一般都会保证非负但自己写对拍生成数据时容易漏掉这个前提。3.4 C竞赛中我还专门写过一页避坑清单仓库的00_template目录下我放了一个cpp_pitfalls.cpp专门记录C语法层面的坑。下面这几条是从多场真实比赛中总结出来的建议你也建一个类似的文件bits/stdc.h是GCC编译器的私货Windows上的MSVC并没有它部分老在线评测系统也编译不过。我在仓库代码里一律用标准头文件列表为了跨平台省心。int溢出是最隐蔽的。题目里n和m都是10^5级别你一时大意写了int area n * m;两个int相乘直接溢出成负数答案错得莫名其妙的。凡是有乘法的地方先确认结果会不会超出int范围不行就转long long。移位运算符的优先级低于加减法。n 1 1会被解析成n (1 1)。想表达(n 1) 1括号必须打。vectorbool不是普通bool数组它是为了压内存做了bit特化的返回的元素是代理对象不是真正的bool。需要频繁修改元素或者想要bool*指针时用vectorint或者普通数组更省心。给sort写比较器时必须满足严格弱序return a b;是错的相等时必须返回false。这个错误在本地跑小数据不一定触发但到评测机大数据下就会变成段错误或者超时。4. 从源码到跑通编译环境、对拍与性能验证代码模板写得再好如果本地不能一键编译、不能自动验证正确性到了比赛现场还是会手忙脚乱。能跑是仓库的最低标准能验证才是它超越普通笔记的地方。4.1 vscode g 环境配置关键是那几条编译参数我平时在vscode里写Ctasks.json里的编译任务长这样{ version: 2.0.0, tasks: [ { label: cpp-build, type: cppbuild, command: /usr/bin/g, args: [ -g, -O2, -stdc17, -Wall, -Wextra, ${file}, -o, ${fileDirname}/${fileBasenameNoExtension} ], group: build, problemMatcher: [$gcc] } ] }几个参数说一下背后的原因。-stdc17是竞赛代码的主流标准大部分评测机已经支持C17的语法特性。-O2是竞赛标配优化等级本地不开O2就测不出真实的运行时间。-Wall -Wextra这两个警告选项很多新手不重视但我强烈建议打开因为它们能帮你提前发现变量未初始化有符号/无符号比较这类坑。-g保留调试信息方便gdb或者vscode的调试器打断点看变量。不过要注意开了O2之后变量可能被优化掉断点不生效的情况很常见。我自己的做法是日常调试时把-O2临时去掉等要提交前再用完整参数重新编译测一次最坏情况的运行时间。4.2 输入输出重定向本地测试和在线评测的缝合竞赛代码在评测机上通过标准输入读数据但本地手敲一堆测试数据很麻烦。我习惯在源码开头用freopen从文件读#ifdef LOCAL freopen(in.txt, r, stdin); freopen(out.txt, w, stdout); #endif提交的时候注释掉#define LOCAL即可。有些选手喜欢用#ifndef ONLINE_JUDGE判断在线评测环境但这个宏并不是所有OJ都有我自己只用LOCAL宏可控性更强。4.3 对拍脚本用随机数据验证正确性比瞪眼找bug效率高得多对拍是竞赛选手人手必备的调试手段思路是写一个一定正确但可能很慢的暴力程序再写一个待验证的高效程序用随机生成的数据同时跑比较输出是否一致。我把对拍脚本放进了仓库的tools目录Python版本如下import subprocess import random for i in range(1000): # 1. 生成随机小数据 with open(in.txt, w) as f: n random.randint(1, 10) f.write(str(n) \n) f.write( .join(str(random.randint(1, 100)) for _ in range(n))) # 2. 分别运行两个程序 with open(in.txt, r) as fin: subprocess.run([./sol], stdinfin, stdoutopen(out_sol.txt, w)) with open(in.txt, r) as fin: subprocess.run([./brute], stdinfin, stdoutopen(out_brute.txt, w)) # 3. 比较输出 sol open(out_sol.txt).read().strip() brute open(out_brute.txt).read().strip() if sol ! brute: print(error at case, i) break对拍的关键是数据范围要小保证暴力程序能在瞬间跑完。找到第一个不一致的case后把它缩到最小规模比如n3、数值范围1到5再用肉眼调试。这个过程能覆盖大量你靠手推根本发现不了的边界情况比如数组越界、重复元素、空输入。我自己的体验是一道卡了很久的WA题往往在对拍跑到第几十组数据时就现出原形比对着屏幕瞪半小时强得多。4.4 性能验证开O2测一次心里才有底跑题之前还是想提醒一句时间复杂度算得再漂亮也不如本地实测一次来得放心。仓库里我建议给每个重量级算法文件都记一笔实测数据——比如dijkstra_heap.cpp的注释里我会写在10^5个点、2×10^5条边的随机图上开O2约0.3s。这样下次比赛遇到类似规模的数据你不需要重新估算直接查注释就能知道这个模板能不能扛得住。5. 维护仓库一年后我总结的三条迭代经验5.1 模板不是写一次就完了每场赛题都在给它们打补丁我最早整理的并查集只有路径压缩没有按秩合并因为觉得路径压缩已经够快。直到有一场题目的数据专门构造了一条极深的链导致性能退化才意识到自己的模板有漏洞。从那以后每场比赛遇到超时或WA我复盘的第一件事就是这是不是仓库模板的问题如果是立刻回仓库改代码、补注释。仓库里的每一个文件都记录着我踩过的坑和打过的补丁这些是买不到的实战经验。5.2 复习不是看代码而是默写代码看一遍自己的模板觉得太简单了合上屏幕才发现连merge函数里先find根节点这种基础步骤都会漏。我给自己定了一个规则每两周挑几个仓库里的高频模板凭空在编辑器里默写一遍限时10分钟。写不出来的地方就是下一步需要重点复习的地方。这个方法听起来笨但效果显著——赛场上不会有代码提示默写能力才是真正的竞争力。5.3 仓库的价值指标只有一个赛场上能不能5分钟打出来这个指标比代码行数、Star数都更诚实。如果模板还需要现场翻笔记那它还不属于你。基于这个标准我每年都会做一次仓库瘦身把一年没用到的冷门模板移到archive目录把高频模板的注释精简到一眼扫完就能理解。删掉冗余内容后仓库反而变得更顺手了。这份C算法竞赛学习仓库从第一天的一个文件夹慢慢长成了现在能覆盖绝大多数竞赛知识点的完整体系。每次打开它看到的都是自己从零到一的学习轨迹。如果你也想建一份我的建议很简单不要想着一步到位搭一个大而全的架子从你刚做过的题开始整理进去写好注释坚持一个月你一定会回来感谢当时那个愿意多花十五分钟整理代码的自己。本文还有配套的精品资源点击获取