简介这份ACM训练题集汇总面向备战国际大学生程序设计竞赛的选手及算法学习者系统整理了竞赛常见题型与解题源码覆盖从基础算法到高级数据结构的完整知识链路。压缩包共281个文件约870.44MB以cpp源码文件为核心辅以Visual Studio工程配置与缓存文件便于直接编译调试与本地复现。内容涉及排序查找、链表栈队列、树与图结构、DFS/BFS、最短路径、最小生成树、动态规划、字符串匹配、数论组合、贪心、回溯与分支限界、位运算等高频考点每类问题均配有可运行的参考实现。已有877人学习下载读者可通过阅读源码理解状态转移、剪枝优化与边界处理技巧对照题目归纳解题模板逐步建立自己的算法工具箱为竞赛实战和后续软件开发打下扎实基础。1. 从一份 ACM 题集说起为什么刷题十年的人还在整理题单ACM 题集、ACM 训练题集、超多 ACM 题集汇总、解题源码这四个词放在一起指向的其实是一件很朴素的事把散落在各处的算法竞赛题按知识点和难度重新组织再配上能跑通的参考实现。我见过太多人刷题刷到瓶颈不是脑子不够用而是题单是乱的——今天做一道并查集明天跳去线段树后天又回头补最短路结果每个专题都停在“见过”的层面。一份好的 ACM 训练题集本质上是把“学什么、按什么顺序学、拿什么验证”这三件事一次性定下来。它适合两类人一是刚打完语法基础、准备系统训练的新手需要一条不绕路的题单二是带训练队的教练或学长需要一套能直接分发的题目汇总和解题源码。接下来的内容我会按“题集怎么组织、源码怎么归档、本地怎么跑通、坑在哪里”这条线把一份可复用的 ACM 题集从零搭出来。2. 题集的组织逻辑从知识点树到难度梯度2.1 为什么按知识点分类比按比赛年份更有效很多人整理题集的第一反应是按比赛年份或比赛名称建文件夹比如“某年区域赛”“某年省赛”。这种做法在归档上没问题但在训练上几乎没用。原因很简单同一场比赛的题目难度跨度极大且知识点分布随机你没法用一套连续的训练路径去覆盖它。按知识点分类则不同它把题目挂在一棵可扩展的树上每个节点代表一个可独立训练的能力单元。我一般会把知识点树分成四层。第一层是基础数据结构数组、链表、栈、队列、哈希表。第二层是基础算法排序、二分、前缀和、差分、双指针、递归。第三层是进阶数据结构并查集、堆、线段树、树状数组、平衡树。第四层是进阶算法动态规划、图论、数论、计算几何、字符串。每一层内部再按难度细分比如动态规划下面可以拆成线性 DP、区间 DP、背包、树形 DP、状压 DP、数位 DP。这样拆的好处是任何一个题目都能被唯一地挂到一个叶节点上训练时只需要沿着叶节点逐个攻克。难度梯度不能只靠“简单、中等、困难”三个标签。我的做法是给每个叶节点内的题目打两个维度思维难度和实现难度各分 1 到 5 级。思维难度指想出解法的难易实现难度指代码写对的难易。一道题可能思维 4 实现 2也可能思维 2 实现 5。训练时优先做思维难度递增、实现难度不超过当前编码能力的题避免卡在“想得出写不出”的挫败感里。2.2 用一份 YAML 清单描述整个题集题集的核心不是题目文件本身而是一份描述清单。我习惯用 YAML 来写因为它既能被人读也能被脚本解析。下面是一个最小可用的清单结构每个题目条目包含编号、标题、知识点路径、两个难度维度和源码文件名。# acm_problems.yaml # 题集描述清单每个条目对应一道题 problems: - id: DS-UNION-001 title: 亲戚关系判定 topic: 数据结构/并查集/路径压缩 thinking_level: 2 # 思维难度 1-5 coding_level: 2 # 实现难度 1-5 source_file: union_find_001.cpp tags: [并查集, 路径压缩, 模板题] - id: DP-KNAP-003 title: 背包容量最大化 topic: 动态规划/背包/01背包 thinking_level: 3 coding_level: 2 source_file: knapsack_003.cpp tags: [01背包, 一维优化, 边界处理] - id: GRAPH-SP-002 title: 单源最短路计数 topic: 图论/最短路/Dijkstra thinking_level: 4 coding_level: 4 source_file: dijkstra_002.cpp tags: [Dijkstra, 优先队列, 计数去重]这份清单的逻辑说明id是全局唯一标识前缀对应知识点缩写方便排序和检索。topic用斜杠分隔的路径直接映射到知识点树。thinking_level和coding_level分开记录训练时可以用脚本筛选出“思维 3 以下、实现 3 以下”的题目作为热身。source_file指向同目录下的源码文件保证清单和代码一一对应。tags是自由标签用于跨知识点检索比如所有带“边界处理”标签的题可以集中复习。参数说明thinking_level和coding_level的取值范围建议固定为 1 到 5不要用 1 到 10粒度太细反而难以判断。topic的层级深度建议不超过四层超过四层说明拆分过细训练时容易迷失。source_file的命名规则建议用“知识点缩写_序号.cpp”避免中文文件名在跨平台时出现编码问题。2.3 从清单生成训练计划的最小脚本有了清单之后下一步是让它能自动生成每日训练计划。下面这个 Python 脚本读取 YAML按知识点分组并输出一个按难度排序的题目列表。它不依赖任何第三方库只用标准库和 PyYAML。# generate_plan.py # 读取题集清单按知识点分组并生成训练顺序 import yaml from collections import defaultdict def load_problems(path): with open(path, r, encodingutf-8) as f: data yaml.safe_load(f) return data[problems] def group_by_topic(problems): groups defaultdict(list) for p in problems: # 取 topic 的前两层作为分组键避免过细 parts p[topic].split(/) key /.join(parts[:2]) if len(parts) 2 else parts[0] groups[key].append(p) return groups def sort_by_difficulty(problems): # 先按思维难度再按实现难度升序排列 return sorted(problems, keylambda x: (x[thinking_level], x[coding_level])) if __name__ __main__: problems load_problems(acm_problems.yaml) groups group_by_topic(problems) for topic, items in groups.items(): print(f {topic} ) for p in sort_by_difficulty(items): print(f [{p[id]}] {p[title]} f(思维{p[thinking_level]}/实现{p[coding_level]}))逻辑说明load_problems负责读取 YAML 并返回题目列表。group_by_topic用defaultdict按 topic 的前两层分组这样“动态规划/背包”和“动态规划/区间”会分到不同组但“动态规划/背包/01背包”和“动态规划/背包/完全背包”会合并到同一组避免分组过细。sort_by_difficulty先按思维难度升序再按实现难度升序保证同组内先做“想得出来也写得出来”的题。参数说明parts[:2]中的数字 2 可以根据题集规模调整题量少时取 1题量多时取 3。排序键的顺序也可以改如果你更在意实现难度可以把coding_level放在前面。脚本输出的是纯文本可以直接重定向到文件作为每日任务清单。3. 解题源码的归档与验证让每份代码都能独立跑通3.1 源码目录结构与命名约定题集里的解题源码最怕两件事一是文件名混乱二是代码依赖外部输入却不知道输入格式。我的做法是给每道题建一个独立目录目录名就是题目 ID里面至少包含三个文件源码文件、输入样例文件、输出样例文件。目录结构如下acm_solutions/ DS-UNION-001/ union_find_001.cpp input_001.txt output_001.txt DP-KNAP-003/ knapsack_003.cpp input_003.txt output_003.txt GRAPH-SP-002/ dijkstra_002.cpp input_002.txt output_002.txt这种结构的逻辑是每道题自包含不依赖其他题目的文件。输入输出样例文件用题目 ID 的后三位命名避免和源码文件重名。源码文件里不写死任何路径所有输入从标准输入读输出到标准输出这样既能在本地用重定向测试也能直接提交到在线评测系统。命名约定上我坚持三条源码文件用英文小写加下划线不用中文输入输出文件用.txt后缀不用.in和.out因为有些编辑器对后者的语法高亮支持不好目录名用题目 ID不用题目标题因为标题可能包含空格和特殊字符。3.2 用脚本批量验证源码的正确性归档之后必须验证每份源码都能在给定输入下产生正确输出。手动一个个跑不现实下面这个 Bash 脚本遍历所有题目目录编译源码运行并比对输出。#!/bin/bash # verify_all.sh # 遍历 acm_solutions 下所有题目目录编译并验证输出 set -e BASE_DIRacm_solutions PASS0 FAIL0 for dir in $BASE_DIR/*/; do id$(basename $dir) src$(find $dir -name *.cpp | head -n 1) input$dir/input_$(echo $id | cut -d- -f3).txt expected$dir/output_$(echo $id | cut -d- -f3).txt actual/tmp/${id}_actual.txt if [ ! -f $src ] || [ ! -f $input ] || [ ! -f $expected ]; then echo [SKIP] $id 缺少文件 continue fi # 编译输出到临时可执行文件 if ! g -stdc17 -O2 -o /tmp/${id}_bin $src 2/tmp/${id}_compile.log; then echo [FAIL] $id 编译失败 cat /tmp/${id}_compile.log FAIL$((FAIL1)) continue fi # 运行并比对 /tmp/${id}_bin $input $actual if diff -q $actual $expected /dev/null; then echo [PASS] $id PASS$((PASS1)) else echo [FAIL] $id 输出不一致 diff $actual $expected | head -n 10 FAIL$((FAIL1)) fi done echo 通过: $PASS, 失败: $FAIL逻辑说明脚本用find定位每个目录下的第一个.cpp文件用题目 ID 的第三段比如DS-UNION-001的001拼接输入输出文件名。编译用g -stdc17 -O2这是竞赛常用配置。运行结果写到/tmp下的临时文件再用diff比对。如果编译失败打印编译日志的前几行如果输出不一致打印差异的前十行。参数说明-stdc17可以根据题目需要改成c14或c20但建议整个题集统一标准。-O2是优化级别验证时开不开都行但开了更接近在线评测环境。head -n 10限制差异输出行数避免输出爆炸。脚本开头的set -e会让脚本在遇到未捕获错误时退出但这里因为用了if判断实际不会触发。3.3 源码里必须保留的注释和边界处理解题源码不是写完就扔的草稿它要能被别人读懂也要能提醒自己当时的思路。我要求每份源码开头有一段注释块包含题目 ID、知识点、思路概述和时间复杂度。下面是一个并查集的示例。// DS-UNION-001 亲戚关系判定 // 知识点并查集/路径压缩 // 思路用 parent 数组维护每个元素的父节点find 时路径压缩 // union 时按秩合并。查询两个元素是否同集合只需比较根节点。 // 时间复杂度近似 O(1) 每次操作 #include bits/stdc.h using namespace std; const int MAXN 100005; int parent[MAXN], rnk[MAXN]; // 初始化每个元素自成一个集合 void init(int n) { for (int i 1; i n; i) { parent[i] i; rnk[i] 0; } } // 查找根节点带路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩路径 } return parent[x]; } // 合并两个集合按秩合并 void unite(int x, int y) { int rx find(x), ry find(y); if (rx ry) return; if (rnk[rx] rnk[ry]) { parent[rx] ry; } else if (rnk[rx] rnk[ry]) { parent[ry] rx; } else { parent[ry] rx; rnk[rx]; } } int main() { int n, m; scanf(%d %d, n, m); init(n); while (m--) { int op, x, y; scanf(%d %d %d, op, x, y); if (op 1) { unite(x, y); } else { printf(%s\n, find(x) find(y) ? Yes : No); } } return 0; }逻辑说明init把每个元素的父节点设为自己秩设为 0。find用递归实现路径压缩把沿途所有节点的父节点直接指向根。unite先找两个根如果相同就返回否则按秩合并秩小的挂到秩大的下面秩相同时任意挂并增加新根的秩。main读入 n 和 m然后处理 m 次操作op 为 1 时合并否则查询。参数说明MAXN取 100005比题目可能的最大 n 多 5防止越界。rnk数组初始为 0表示单节点树的秩。scanf和printf比cin和cout快适合大数据量。路径压缩用递归写法简洁但如果 n 很大导致递归深度过深可以改成迭代写法。4. 本地跑通与批量测试从单题验证到全量回归4.1 单题调试的三种输入方式本地跑一道题输入方式有三种手动输入、文件重定向、管道。手动输入适合小数据量调试比如并查集那道题你可以直接在终端敲几行操作。文件重定向适合用样例文件验证命令是./union_find_001 input_001.txt。管道适合把生成的数据直接喂给程序比如python gen.py | ./union_find_001。我一般先用文件重定向跑一遍样例确认输出和预期一致再用管道跑随机数据做压力测试。压力测试的关键是写一个数据生成器下面是一个生成并查集随机操作的 Python 脚本。# gen_union.py # 生成并查集的随机测试数据 import random import sys n int(sys.argv[1]) if len(sys.argv) 1 else 100 m int(sys.argv[2]) if len(sys.argv) 2 else 200 print(n, m) for _ in range(m): op random.randint(1, 2) x random.randint(1, n) y random.randint(1, n) print(op, x, y)逻辑说明脚本从命令行参数读取 n 和 m默认 n100、m200。然后循环 m 次每次随机生成操作类型和两个操作数。输出格式和题目输入格式一致可以直接通过管道传给可执行文件。参数说明sys.argv[1]和sys.argv[2]分别对应 n 和 m不传时用默认值。random.randint(1, n)生成闭区间内的整数保证 x 和 y 在合法范围内。如果要测试极端情况可以把 op 固定为 1 或 2或者让 x 和 y 总是相等。4.2 用对拍脚本发现隐藏错误单题验证只能证明样例通过不能证明逻辑正确。对拍是发现隐藏错误的有效手段写一个暴力解法用随机数据同时跑暴力解法和优化解法比对输出。下面是对拍脚本的框架。#!/bin/bash # duipai.sh # 对拍暴力解法 vs 优化解法 for i in $(seq 1 1000); do python gen_union.py 50 100 /tmp/duipai_input.txt ./brute_force /tmp/duipai_input.txt /tmp/duipai_brute.txt ./union_find_001 /tmp/duipai_input.txt /tmp/duipai_fast.txt if ! diff -q /tmp/duipai_brute.txt /tmp/duipai_fast.txt /dev/null; then echo 发现差异输入已保存到 /tmp/duipai_input.txt diff /tmp/duipai_brute.txt /tmp/duipai_fast.txt | head -n 20 exit 1 fi done echo 1000 次对拍全部通过逻辑说明循环 1000 次每次生成一组随机输入分别跑暴力解法和优化解法比对输出。如果发现差异保存输入并打印差异的前二十行然后退出。如果全部通过打印通过信息。参数说明seq 1 1000控制对拍次数次数越多越可能发现边界错误但耗时也越长。gen_union.py 50 100生成 n50、m100 的小数据小数据更容易触发边界条件。暴力解法需要自己实现通常用最朴素的算法比如并查集暴力解法可以不用路径压缩和按秩合并。4.3 全量回归与性能基准题集规模大了之后每次修改公共代码或调整编译选项都需要跑一次全量回归。全量回归就是第 3 章里的verify_all.sh但它只验证正确性不验证性能。性能基准需要单独做对每道题记录运行时间和预期的时间复杂度对比。我一般用/usr/bin/time来测运行时间命令是/usr/bin/time -f %e秒 %MKB ./union_find_001 input_001.txt。%e是实际耗时%M是最大内存占用。把结果记录到一个 CSV 文件里格式是题目 ID、耗时、内存、数据规模。这样当某道题耗时突然变大时能快速定位是数据规模变了还是代码退化了。性能基准的阈值设定要合理。对于 n100000 的并查集路径压缩加按秩合并的耗时通常在 0.05 秒以内如果超过 0.2 秒就说明有问题。对于 Dijkstran100000、m200000 的耗时通常在 0.3 秒以内超过 1 秒就需要检查优先队列的实现。这些阈值不是绝对的但能帮你快速筛出异常。5. 避坑与常见问题题集维护中的血泪经验5.1 编译通过但运行崩溃数组越界和栈溢出现象源码在本地编译没问题但运行到某个测试用例时直接段错误。原因通常是数组开小了或者递归深度过大导致栈溢出。解决方法是把数组大小开到题目上限的 1.5 倍递归改迭代或者在编译时加-Wl,-stack_size,0x10000000增大栈空间。我一般会在源码开头用const int MAXN ...统一定义上限避免散落的魔数。5.2 样例通过但提交报错输入格式和输出格式的坑现象本地用样例文件跑输出完全一致但提交到评测系统就是 Wrong Answer。原因可能是输入格式没处理干净比如多组数据没有循环读取或者输出末尾多了空格。解决方法是仔细读题目的输入输出描述多组数据用while (scanf(...) ! EOF)或while (cin n)输出严格按题目要求不要多打空格或换行。我习惯在本地用diff比对时加-Z忽略行尾空格但提交前一定手动检查一遍。5.3 对拍通过但隐藏用例挂掉随机数据覆盖不到边界现象对拍跑了 1000 次全部通过但提交后还是挂在一个隐藏用例上。原因是随机数据生成器没有覆盖边界情况比如 n1、m0、所有操作都是查询、所有操作都是合并。解决方法是在对拍脚本里加入边界数据生成或者手动构造几组极端数据单独测试。我一般会准备一个edge_cases目录里面放 n1、n2、全查询、全合并等固定输入每次修改代码后先跑这些边界用例。5.4 源码文件丢失或版本混乱没有版本控制现象改了一版代码发现改错了想回退但旧版本已经被覆盖。原因是源码目录没有用版本控制。解决方法是给整个题集目录初始化 Git 仓库每次修改后提交提交信息写清楚改了哪道题、为什么改。如果不想用 Git至少每周做一次全量备份备份文件名带日期。我见过有人把源码放在网盘同步目录里结果同步冲突导致文件损坏这种坑一次就够了。5.5 题集清单和源码不同步ID 对不上现象清单里有一道题但源码目录里找不到对应文件或者源码文件名和清单里的source_file不一致。原因是手动维护清单时漏改或改错。解决方法是写一个校验脚本遍历清单里的每个条目检查source_file是否存在同时遍历源码目录检查每个源码文件是否在清单里有对应条目。这个脚本可以并入verify_all.sh每次全量回归时自动跑。6. 进阶技巧把题集变成可检索的本地知识库题集做到一定规模后最大的痛点不是题目不够而是找不到想要的题。比如你想找“所有涉及区间合并的线段树题且思维难度不超过 3”靠翻文件夹效率极低。我的做法是把 YAML 清单导入 SQLite用 SQL 做检索。下面是一个建表和查询的示例。-- 建表题目表 CREATE TABLE problems ( id TEXT PRIMARY KEY, title TEXT NOT NULL, topic TEXT NOT NULL, thinking_level INTEGER CHECK(thinking_level BETWEEN 1 AND 5), coding_level INTEGER CHECK(coding_level BETWEEN 1 AND 5), source_file TEXT NOT NULL ); -- 建表标签表多对多关系 CREATE TABLE tags ( problem_id TEXT, tag TEXT, FOREIGN KEY (problem_id) REFERENCES problems(id) ); -- 查询思维难度不超过 3 且包含“线段树”标签的题 SELECT p.id, p.title, p.topic FROM problems p JOIN tags t ON p.id t.problem_id WHERE t.tag 线段树 AND p.thinking_level 3 ORDER BY p.thinking_level, p.coding_level;逻辑说明problems表存题目基本信息tags表存标签通过problem_id关联。查询时用JOIN把两张表连起来筛选标签和难度条件最后按难度排序。这种结构比纯文本检索灵活得多你可以随时加新的查询条件比如按知识点路径模糊匹配、按源码文件是否存在筛选。参数说明CHECK约束保证难度值在 1 到 5 之间防止录入错误。FOREIGN KEY保证标签不会挂到不存在的题目上。如果题集规模不大也可以不用 SQLite直接用 Python 的pandas读 YAML 后做筛选但 SQLite 的优势是持久化和并发查询。导入脚本可以用 Python 的sqlite3模块读取 YAML 后逐条插入。我一般会在导入前先清空表避免重复数据。导入后跑一遍verify_all.sh确保清单和源码仍然一致。最后一个技巧是关于题集的持续更新。我习惯每周花半小时做三件事把新做的题按格式加入清单和源码目录跑一次全量回归用 SQL 查一下有没有知识点覆盖的空白区域。比如发现“数位 DP”下面只有两道题就专门去找几道补上。这样题集不是一次性整理完就扔在那里而是随着训练不断生长。我自己坚持这个习惯两年多最大的教训是不要等到题集乱了才去整理每次做完题就顺手归档比攒一个月再整理轻松十倍。希望帮到你。本文还有配套的精品资源点击获取
