C++算法竞赛学习仓库：可编译的工程化训练场与模板库

简介这是一份面向算法竞赛学习者与ACMer的C代码仓库适合正在备战ACWing、CodeForces等在线评测平台、希望系统积累题解与模板的初中级选手。压缩包共916个文件约1.03MB以577个.cc与289个.cpp源码为主体另含少量Kotlin、Python、Java实现以及Markdown笔记、图片、脚本和构建配置覆盖动态规划、图论、搜索、数学、数据结构等方向。仓库按统一命名规范组织题目代码并附有参与者的学习笔记与经典算法模板便于按专题查阅、对照思路和快速复用。目前已有86人学习。读者可从中获得多平台赛题的AC代码参考、可复用的算法模板、分专题的解题笔记以及规范的目录组织方式适合作为日常训练与查漏补缺的代码库。1. 算法竞赛学习仓库一份能直接编译的 C 训练场很多人第一次打开算法竞赛的 C 仓库看到的是几十个.cpp文件散落在根目录没有 CMake没有测试用例连main函数都长得不一样。这份基于 C 的算法竞赛学习仓库解决的就是这个问题——它把散落的题解、模板、数据结构实现收进一个可编译、可增量构建的工程里。适合两类人刚学完 C 语法、想通过刷题把 STL 和算法用熟的新手以及需要一套本地模板库、不想每次比赛前重新手写快排和并查集的熟手。仓库本身不绑定任何在线判题平台所有代码在本地就能跑通这对网络环境不稳定或者想离线调试的人来说比在线编辑器靠谱得多。2. 仓库结构与编译链路从 clone 到第一个可执行文件2.1 目录布局与文件职责拿到压缩包解压后先别急着点开.sln或CMakeLists.txt。我一般会先跑一遍tree或者find把目录结构看清楚。这类学习仓库通常按算法主题分目录而不是按题目来源分。一个典型的布局是这样的algorithm-competition/ ├── CMakeLists.txt ├── include/ │ ├── graph/ │ │ ├── dijkstra.h │ │ └── union_find.h │ ├── dp/ │ │ └── knapsack.h │ └── string/ │ └── kmp.h ├── src/ │ ├── graph/ │ │ └── dijkstra_test.cpp │ └── dp/ │ └── knapsack_test.cpp └── third_party/ └── gtest/include/放的是头文件形式的模板实现src/放的是对应的测试或调用入口。这种分离方式的好处是你写新题的时候只需要在src/下加一个.cpp然后#include对应的头文件不用把整个模板复制一遍。third_party/里如果有 gtest说明仓库作者是认真在做单元测试的不是随手扔几个main函数上去。2.2 CMake 构建一次配置增量编译这类仓库最常见的构建方式是 CMake。如果你在 Windows 上用 Visual Studio可以直接打开根目录的CMakeLists.txtVS 会自动识别并生成工程。但更通用的做法是在命令行里走一遍# 在仓库根目录执行 mkdir build cd build cmake .. -DCMAKE_BUILD_TYPERelease cmake --build . --config Release -j 8第一行创建独立的构建目录避免编译产物污染源码树。第二行生成构建系统-DCMAKE_BUILD_TYPERelease指定优化级别算法竞赛代码对性能敏感Debug 模式下 STL 的迭代器检查会拖慢速度测性能的时候必须用 Release。第三行执行编译-j 8表示用 8 个线程并行编译具体数字按你机器的核心数改一般设成核心数或者核心数加一。编译完成后可执行文件通常在build/src/或者build/bin/下面。如果你在CMakeLists.txt里看到add_executable(dijkstra_test src/graph/dijkstra_test.cpp)那对应的二进制就叫dijkstra_test。直接运行它如果输出了一组测试结果或者打印了最短路径长度说明工具链没问题。提示Windows 上如果cmake命令找不到先确认 CMake 是否加入了系统 PATH。Visual Studio 安装时自带 CMake但默认不加入 PATH需要手动在「Visual Studio Installer」里勾选「用于 Windows 的 C CMake 工具」。2.3 单文件编译不想用 CMake 的备选方案有些仓库的CMakeLists.txt写得比较粗糙或者你只想快速验证某一个文件。这时候可以直接用 g 编译单个.cpp# 编译单个文件指定 C17 标准开启 O2 优化 g -stdc17 -O2 -Wall -Wextra -o dijkstra_test src/graph/dijkstra_test.cpp -I include-stdc17是因为很多竞赛模板用了auto推导、结构化绑定、if constexpr这些特性C11 编译不过。-O2是竞赛常用的优化级别比-O3更稳定不容易触发某些编译器的激进优化 bug。-Wall -Wextra打开所有警告算法竞赛代码里常见的「有符号和无符号比较」「变量未使用」都能提前发现。-I include告诉编译器头文件搜索路径不然#include graph/dijkstra.h会找不到。如果你在 Windows 上用 MSVC对应的命令是cl /std:c17 /O2 /I include src\graph\dijkstra_test.cpp。注意 MSVC 的/O2和 g 的-O2不是完全等价但在这个场景下够用。3. 核心算法模块拆解从并查集到 Dijkstra 的工程化写法3.1 并查集路径压缩与按秩合并的取舍并查集是算法竞赛里出现频率最高的数据结构之一但很多人的实现只写了路径压缩没写按秩合并。这份仓库里的union_find.h两个都实现了而且把选择权留给了调用者。先看代码// include/graph/union_find.h #pragma once #include vector class UnionFind { public: explicit UnionFind(int n) : parent_(n), rank_(n, 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]; } bool unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return false; // 按秩合并把矮树挂到高树下 if (rank_[rx] rank_[ry]) std::swap(rx, ry); parent_[ry] rx; if (rank_[rx] rank_[ry]) rank_[rx]; return true; } private: std::vectorint parent_; std::vectorint rank_; };find用了递归路径压缩代码短但如果你在竞赛里遇到链式结构特别深的情况递归层数可能达到几万层栈空间不够就会崩。我一般会改成迭代写法int find(int x) { int root x; while (parent_[root] ! root) root parent_[root]; while (parent_[x] ! x) { int next parent_[x]; parent_[x] root; x next; } return root; }迭代版本多了一个循环但不会爆栈。unite里的按秩合并保证了树高是 O(log n)即使不做路径压缩单次操作也不会退化到 O(n)。两个优化一起用均摊复杂度接近 O(α(n))α 是反阿克曼函数在实际数据规模下不超过 4。注意如果你的题目只需要判断连通性不需要动态合并用 BFS 或者 DFS 染色更简单。并查集的价值在于「边合并边查询」的场景比如 Kruskal 最小生成树。3.2 Dijkstra优先队列实现与负权边处理Dijkstra 的模板很多人背得出来但工程实现里有两个坑一是优先队列里存的是pairint,int默认按 first 排序如果 first 存的是节点编号而不是距离就会出错二是没有处理重边和自环。仓库里的dijkstra.h是这样写的// include/graph/dijkstra.h #pragma once #include vector #include queue #include limits struct Edge { int to; int weight; }; std::vectorint dijkstra(const std::vectorstd::vectorEdge graph, int start) { const int INF std::numeric_limitsint::max() / 2; int n static_castint(graph.size()); std::vectorint dist(n, INF); // 小根堆pair距离, 节点 using P std::pairint, int; std::priority_queueP, std::vectorP, std::greaterP pq; dist[start] 0; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); // 过期条目直接跳过 if (d dist[u]) continue; for (const auto e : graph[u]) { if (dist[u] e.weight dist[e.to]) { dist[e.to] dist[u] e.weight; pq.push({dist[e.to], e.to}); } } } return dist; }std::greaterP让优先队列变成小根堆每次弹出距离最小的节点。if (d dist[u]) continue;这行是必须的因为同一个节点可能被多次入队只有距离等于当前最短距离的那次才有效。INF取INT_MAX / 2而不是INT_MAX是为了防止dist[u] e.weight溢出。如果你把INF设成INT_MAX加法直接变成负数整个结果就错了。这个实现不支持负权边。如果图里有负权边Dijkstra 的贪心策略失效必须换 Bellman-Ford 或者 SPFA。仓库里如果有bellman_ford.h那说明作者考虑到了这个边界。没有的话遇到负权边题目就得自己补。3.3 动态规划背包问题的空间优化背包问题是 DP 入门的经典但很多人写 01 背包的时候内层循环方向搞反导致物品被重复使用。仓库里的knapsack.h把 01 背包和完全背包放在一起对比// include/dp/knapsack.h #pragma once #include vector #include algorithm // 01 背包每个物品最多选一次 int knapsack01(const std::vectorint weights, const std::vectorint values, int capacity) { std::vectorint dp(capacity 1, 0); for (size_t i 0; i weights.size(); i) { // 逆序遍历保证每个物品只被选一次 for (int j capacity; j weights[i]; --j) { dp[j] std::max(dp[j], dp[j - weights[i]] values[i]); } } return dp[capacity]; } // 完全背包每个物品可以选无限次 int knapsackComplete(const std::vectorint weights, const std::vectorint values, int capacity) { std::vectorint dp(capacity 1, 0); for (size_t i 0; i weights.size(); i) { // 正序遍历允许同一物品被多次选取 for (int j weights[i]; j capacity; j) { dp[j] std::max(dp[j], dp[j - weights[i]] values[i]); } } return dp[capacity]; }两个函数的唯一区别是内层循环方向。01 背包逆序是因为dp[j]依赖的是上一轮物品的dp[j - weights[i]]逆序保证这个值还没被当前物品更新过。完全背包正序是因为它允许当前物品被重复选取dp[j - weights[i]]可以是本轮已经更新过的值。这个细节如果记混了01 背包会变成完全背包完全背包会变成 01 背包结果全错。提示如果容量特别大比如 1e9但物品数量少这种一维 DP 数组开不下。常见做法是换成「价值维度」的 DP或者用 meet-in-the-middle。仓库里如果有knapsack_meet_in_middle.h那就是针对这种场景的。4. 避坑与排查编译通过但结果不对的五个血泪经验4.1 现象本地编译通过提交到判题系统报编译错误原因通常是编译器版本差异。本地用 g 13 支持 C20 的std::ranges但判题系统可能还在用 g 7 或者 clang 6只支持到 C14。仓库里的代码如果用了auto [a, b] ...这种结构化绑定在 C14 下直接编译失败。解决在CMakeLists.txt里把CMAKE_CXX_STANDARD设成 14 或者 17不要设 20。如果某个文件必须用 C17单独给它加set_source_files_properties(... PROPERTIES CXX_STANDARD 17)。提交之前用g -stdc14 -fsyntax-only跑一遍只做语法检查不生成二进制速度快。4.2 现象Dijkstra 跑出来的距离全是 INF原因通常是图没有正确建边。检查graph的初始化std::vectorstd::vectorEdge graph(n);这里的n是节点数如果你写成了n 1但节点编号从 0 开始多出来的那个空 vector 不影响结果。但如果写成了n而节点编号从 1 开始graph[1]就越界了行为未定义。解决统一节点编号从 0 开始或者统一从 1 开始并在初始化时开n 1大小。我一般会在main函数开头加一行assert(graph.size() n);把问题提前暴露出来。4.3 现象并查集find递归爆栈原因路径压缩的递归写法在链式结构下递归深度等于链长。如果数据是 1e5 个节点依次合并成一条链递归深度就是 1e5默认栈空间 8MB 不够用。解决改成迭代版本或者加#pragma comment(linker, /STACK:1024000000)仅 MSVC。更通用的做法是在CMakeLists.txt里给可执行文件加链接选项-Wl,-stack_size,0x10000000macOS或者-Wl,-z,stacksize0x10000000Linux。但最省事的还是写迭代。4.4 现象Release 模式下结果和 Debug 不一样原因未定义行为。比如数组越界写、有符号整数溢出、使用未初始化的变量。Debug 模式下编译器可能恰好给了你一个「看起来对」的结果Release 模式下优化器把代码重排了结果就变了。解决用-fsanitizeaddress,undefined编译一遍跑同样的测试数据。ASan 会检测越界和内存泄漏UBSan 会检测整数溢出和空指针解引用。这两个工具在本地开发时开着提交时关掉。g -stdc17 -g -fsanitizeaddress,undefined -o dijkstra_test src/graph/dijkstra_test.cpp -I include ./dijkstra_test如果 ASan 报了heap-buffer-overflow顺着堆栈找到越界的那一行基本都是数组大小开错了。4.5 现象std::priority_queue自定义比较器写反了原因std::priority_queue默认是大根堆传入std::greaterT变成小根堆。但如果你自己写仿函数operator()返回true表示第一个参数优先级低于第二个参数。很多人把return a b;和return a b;搞反导致堆序颠倒。解决记住一个口诀——priority_queue的top()是「优先级最高」的元素。对于小根堆优先级最高的是最小值所以比较器应该返回a ba 比 b 大时a 优先级低。如果记不住直接用std::greaterT别自己写。5. 进阶用法把仓库变成个人模板库的自动化脚本仓库用久了你会积累一批自己写的模板。如果每次都手动复制到比赛环境容易漏文件、漏依赖。我一般会写一个打包脚本把include/下所有头文件合并成一个template.cpp比赛时直接粘贴。#!/bin/bash # merge_templates.sh把 include 下的头文件合并成单文件模板 OUTPUTtemplate.cpp echo // Auto-generated template. Do not edit manually. $OUTPUT echo #include bits/stdc.h $OUTPUT echo using namespace std; $OUTPUT # 按目录顺序合并保证依赖关系正确 for dir in graph dp string math; do if [ -d include/$dir ]; then for file in include/$dir/*.h; do # 去掉 #pragma once 和 #include 指令避免重复 grep -v #pragma once $file | grep -v #include $OUTPUT echo $OUTPUT done fi done echo // Merge complete. Lines: $(wc -l $OUTPUT)这个脚本做了三件事先写入bits/stdc.h和using namespace std;这是竞赛代码的标配然后按graph、dp、string、math的顺序遍历目录保证被依赖的头文件先合并最后过滤掉#pragma once和#include指令避免合并后重复包含。合并完成后输出行数方便你确认没有漏文件。参数方面dir列表需要根据你仓库的实际目录名调整。如果某个头文件之间有依赖比如dijkstra.h用到了union_find.h里的结构那union_find.h必须排在前面。我一般会在include/下建一个deps.txt手动维护顺序脚本读这个文件而不是硬编码目录列表。验证合并结果是否可用用g -stdc17 -fsyntax-only template.cpp跑一遍语法检查。如果报错说某个类型未定义说明合并顺序错了调整deps.txt里的顺序即可。从那以后我每次打比赛前都会先跑一遍这个脚本确认template.cpp能通过语法检查再把它复制到比赛环境的编辑器里。这个习惯帮我省掉了至少三次「比赛开始十分钟还在手忙脚乱拼模板」的翻车经历。希望帮到你。本文还有配套的精品资源点击获取