简介这份资源是面向C学习者和算法竞赛备赛者的CSES Problem Set题解代码合集针对希望系统提升算法基础与问题解决能力的程序员覆盖从入门到进阶的完整训练路径。压缩包共28个文件全部为cpp源码整体约19KB按CSES官方分类组织涵盖基础算法、动态规划、图论与树、贪心、数据结构、数学、回溯剪枝、位运算、模拟建模及编码技巧等模块目录结构清晰便于按专题检索与对照练习。已有256人学习下载适合准备ACM/ICPC、Google Code Jam等赛事或提升面试表现的读者。通过研读这些可直接编译运行的代码读者能掌握数组与字符串操作、状态转移方程设计、DFS/BFS与最小生成树、线段树与并查集、质数与GCD/LCM等数论应用以及位掩码和回溯剪枝的优化思路从而在实战中培养解决复杂问题的思维方式。1. CSES-Problem-Set从“刷完就忘”到“建模板库”的转折点如果你在算法竞赛圈待过一阵大概率听过 CSES-Problem-Set 这个名字。它是一套结构非常清晰的在线题库覆盖从入门模拟到高级图论、动态规划的完整梯度很多选手把它当作“算法能力体检表”。但真正让它在实战中产生价值的不是刷了多少题而是你有没有把每道题抽象成可复用的代码模板。我见过太多人刷完三百题遇到变体依然卡壳问题就出在“只过题、不沉淀”。这篇笔记面向两类人一是刚接触 CSES-Problem-Set、想系统建立解题框架的新手二是刷了几十题但感觉效率低、想优化流程的熟手。接下来我会把选题策略、本地环境搭建、模板化改造、调试排查和进阶技巧拆开讲每一步都落到可执行的命令和代码上。2. 把 CSES-Problem-Set 跑进本地环境、目录与自动化脚本2.1 为什么建议本地建镜像目录而不是纯在线提交在线编辑器虽然方便但有两个硬伤一是无法批量管理代码版本二是调试时看不到完整的输入输出对比。我一般会在本地建一个cses/根目录按 CSES-Problem-Set 的官方分类建子目录比如introductory/、sorting/、graph/、dp/、range_queries/。每个题目一个.cpp或.py文件文件名用题目编号加简短英文名例如1621_distinct_numbers.cpp。这样做的好处是后期用脚本批量编译、批量跑测试用例时路径规则统一不会因为命名混乱而翻车。目录结构建议如下cses/ ├── introductory/ │ ├── 1068_weird_algorithm.cpp │ └── 1083_missing_number.cpp ├── sorting/ │ ├── 1621_distinct_numbers.cpp │ └── 1640_sum_of_two_values.cpp ├── graph/ ├── dp/ ├── range_queries/ ├── tests/ │ ├── 1068_1.in │ ├── 1068_1.out │ └── ... └── run_tests.shtests/目录专门放自己构造的边界用例命名规则是题目编号_序号.in和对应的.out。这个习惯在后期做对拍时特别有用因为你可以直接用脚本把同一组输入喂给两个不同的实现快速定位差异。2.2 用 Bash 脚本批量编译与测试的最小实现下面这个run_tests.sh是我常用的最小化测试脚本支持 C 和 Python 两种语言自动匹配tests/下的输入输出文件。#!/usr/bin/env bash # 用法: ./run_tests.sh 源文件路径 题目编号 # 示例: ./run_tests.sh sorting/1621_distinct_numbers.cpp 1621 set -euo pipefail SRC$1 PROB_ID$2 BASENAME$(basename $SRC) EXT${BASENAME##*.} TMP_BIN/tmp/cses_${PROB_ID} # 根据扩展名选择编译或解释方式 if [ $EXT cpp ]; then g -stdc17 -O2 -Wall -Wextra -o $TMP_BIN $SRC RUN_CMD$TMP_BIN elif [ $EXT py ]; then RUN_CMDpython3 $SRC else echo 不支持的扩展名: $EXT exit 1 fi PASS0 FAIL0 # 遍历 tests 目录下所有匹配的输入文件 for IN_FILE in tests/${PROB_ID}_*.in; do [ -e $IN_FILE ] || continue OUT_FILE${IN_FILE%.in}.out [ -e $OUT_FILE ] || continue ACTUAL$($RUN_CMD $IN_FILE) EXPECTED$(cat $OUT_FILE) if [ $ACTUAL $EXPECTED ]; then echo [PASS] $IN_FILE PASS$((PASS 1)) else echo [FAIL] $IN_FILE echo 期望: $EXPECTED echo 实际: $ACTUAL FAIL$((FAIL 1)) fi done echo 通过 $PASS 个失败 $FAIL 个 [ $FAIL -eq 0 ]逻辑说明脚本先根据文件扩展名决定用g编译还是用python3直接运行。-stdc17 -O2 -Wall -Wextra是竞赛常用编译参数-Wall -Wextra能提前暴露未初始化变量、类型截断等问题。测试环节遍历tests/下所有匹配题目编号的.in文件自动找同名.out做逐行字符串比对。注意这里用的是字符串完全匹配如果题目要求忽略行末空格需要把比对逻辑改成diff (echo $ACTUAL) (echo $EXPECTED)并加-b参数。参数调整建议如果题目涉及浮点数输出字符串比对会失效此时应改用python3 -c做数值容差比较容差一般设1e-6。另外TMP_BIN放在/tmp下可以避免污染工作目录但如果你在 Windows 的 WSL 里跑建议改成./.build/并加入.gitignore。2.3 用 Python 做输入生成与对拍的最小框架当题目逻辑复杂、手造用例覆盖不全时对拍是最高效的排查手段。下面是一个生成随机输入并调用两个程序做比对的 Python 脚本骨架。import random import subprocess import sys def gen_input(seed): 根据题目约束生成随机输入seed 保证可复现 random.seed(seed) n random.randint(1, 1000) arr [random.randint(1, 10**9) for _ in range(n)] return f{n}\n{ .join(map(str, arr))}\n def run_program(cmd, input_data): 运行指定命令返回标准输出 result subprocess.run( cmd, inputinput_data, textTrue, capture_outputTrue, timeout5 ) if result.returncode ! 0: raise RuntimeError(f程序异常退出: {result.stderr}) return result.stdout.strip() def main(): for seed in range(200): inp gen_input(seed) out_a run_program([./solution_a], inp) out_b run_program([./solution_b], inp) if out_a ! out_b: print(f发现差异seed{seed}) print(输入:) print(inp) print(f方案A输出: {out_a}) print(f方案B输出: {out_b}) sys.exit(1) print(200 组随机测试全部一致) if __name__ __main__: main()逻辑说明gen_input负责按题目数据范围生成随机用例seed参数保证每次运行可复现同一组数据。run_program用subprocess.run带超时调用可执行文件超时设 5 秒可以捕获死循环。主循环跑 200 组一旦发现输出不一致就打印输入和双方输出并退出。这个框架的关键在于gen_input要覆盖边界最小值、最大值、全相同元素、已排序、逆序等。我一般会写多个生成函数用random.choice随机切换。参数调整timeout5对大多数 CSES 题目够用但如果你的暴力实现复杂度是 O(n²) 且 n2×10⁵可能需要调到 10 秒。另外capture_outputTrue会捕获 stderr如果程序有大量调试输出建议在最终对拍时关掉调试打印。3. 从 AC 到模板把 CSES-Problem-Set 题目抽象成可复用代码块3.1 哪些题型值得沉淀成模板不是每道题都值得建模板。我的判断标准是如果一道题的解法在后续题目中重复出现三次以上就值得抽象。CSES-Problem-Set 里最值得沉淀的几类包括二分查找的上下界写法、前缀和与差分、并查集、Dijkstra 与 Bellman-Ford、树状数组、线段树、背包问题的一维滚动数组、LIS 的 O(n log n) 写法。这些模板一旦写熟遇到变体只需要改参数和边界条件不需要重新推导。以sorting/1621_distinct_numbers为例题目本身只是去重计数但它背后的排序加双指针思路在sum_of_two_values、sum_of_three_values里反复出现。我一般会把“排序后双指针找目标和”写成一个独立函数输入是数组和目标值输出是下标对或布尔值。这样在后续题目里直接调用减少重复思考。3.2 用 C 模板类封装并查集与树状数组下面是一个我常用的并查集模板带路径压缩和按秩合并直接放在templates/dsu.hpp里。#pragma once #include vector #include numeric class DSU { public: explicit DSU(int n) : parent(n 1), rank_(n 1, 0) { std::iota(parent.begin(), parent.end(), 0); } // 查找根节点带路径压缩 int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } // 合并两个集合返回是否发生了合并 bool unite(int a, int b) { int ra find(a), rb find(b); if (ra rb) return false; if (rank_[ra] rank_[rb]) std::swap(ra, rb); parent[rb] ra; if (rank_[ra] rank_[rb]) rank_[ra]; return true; } // 判断两个元素是否在同一集合 bool same(int a, int b) { return find(a) find(b); } private: std::vectorint parent; std::vectorint rank_; };逻辑说明构造函数用std::iota把每个元素的父节点初始化为自身。find递归实现路径压缩把查询路径上所有节点直接挂到根上。unite先找根如果相同则返回false否则按秩合并秩小的挂到秩大的下面秩相等时合并后秩加一。same是对find的简单封装。这个模板在 CSES 的graph/1676_round_trip、graph/1671_shortest_routes_i等题里可以直接复用。参数注意n 1的大小是为了支持 1-based 下标CSES 题目大多用 1-based 编号。如果你的题目是 0-based把构造函数改成DSU(int n) : parent(n), rank_(n, 0)并调整iota起始值即可。3.3 树状数组模板与 CSES 动态求和场景的对接树状数组在 CSES 的range_queries分类里出现频率极高。下面这个模板支持单点加和区间求和。#pragma once #include vector class Fenwick { public: explicit Fenwick(int n) : tree(n 1, 0), n_(n) {} // 在位置 i 上加 deltai 从 1 开始 void add(int i, long long delta) { for (; i n_; i i (-i)) tree[i] delta; } // 求前缀和 [1, i] long long prefix_sum(int i) const { long long s 0; for (; i 0; i - i (-i)) s tree[i]; return s; } // 求区间和 [l, r] long long range_sum(int l, int r) const { return prefix_sum(r) - prefix_sum(l - 1); } private: std::vectorlong long tree; int n_; };逻辑说明add沿i i (-i)向上更新所有覆盖该位置的节点。prefix_sum沿i - i (-i)向下累加。range_sum用两个前缀和相减。注意tree用long long存储因为 CSES 的求和题数值可能超过int范围。n_保存数组长度避免每次调用都传。参数注意如果题目需要区间加、单点查可以把add的逻辑反过来用差分思想实现。如果同时需要区间加和区间查需要两个树状数组配合这个进阶写法在 CSES 的range_queries/1735_range_updates_and_sums里会用到。4. 避坑与排查CSES-Problem-Set 刷题中最容易翻车的五个点4.1 输入格式误判导致本地全过、提交全错现象本地测试用例全部通过提交后返回 WA 或 RE。原因通常是 CSES 的输入格式和你在本地构造的不一致比如题目说“第一行一个整数 n接下来 n 行每行一个整数”但你本地生成的是所有数字在同一行。CSES 的输入解析对空白字符不敏感但如果你用scanf(%d\n, n)这种带换行的格式串在某些环境下会吞掉后续字符。解决统一用cin 或scanf(%d, n)不要手动在格式串里加\n。另外CSES 的题目编号和实际输入规模要仔细核对有些题 n 到 2×10⁵你本地只测了 n10提交后 TLE 或数组越界。4.2 递归深度过大导致栈溢出现象本地小数据通过提交大数据时 RE错误信息可能是段错误。原因CSES 的图论题节点数可达 10⁵用递归 DFS 时系统栈默认只有 8MB 左右深度超过 10⁴ 就可能溢出。解决把递归改成显式栈的迭代写法或者在本地编译时加-Wl,-stack_size,0x10000000macOS或ulimit -s unlimitedLinux。更稳妥的做法是直接写迭代版 DFS下面是一个示例。// 迭代版 DFS避免递归栈溢出 void dfs_iterative(int start, const std::vectorstd::vectorint adj, std::vectorbool visited) { std::vectorint stack {start}; visited[start] true; while (!stack.empty()) { int u stack.back(); stack.pop_back(); for (int v : adj[u]) { if (!visited[v]) { visited[v] true; stack.push_back(v); } } } }逻辑说明用std::vectorint模拟栈每次取栈顶元素把未访问的邻居标记后压栈。注意这里压栈顺序和递归版相反但遍历结果集合相同。如果题目要求按特定顺序输出需要在压栈前对邻居排序或调整压栈顺序。4.3 整数溢出与 long long 的取舍现象求和类题目结果对不上或者出现负数。原因CSES 的求和题数值范围经常到 10⁹n 到 2×10⁵乘积可达 2×10¹⁴超出int的 2×10⁹ 上限。解决所有涉及累加、乘积的变量一律用long long。但要注意long long的printf格式符是%lldcin/cout不需要改。另外如果题目要求输出对 10⁹7 取模中间乘法也要用long long并在每步取模避免溢出。4.4 多测清空不彻底导致答案串题现象单组数据正确多组数据时第二组开始出错。原因全局数组、vector、visited标记没有在每组数据前重置。解决把每组数据的处理封装成函数所有状态在函数内定义如果必须用全局变量写一个reset()函数在每组开始前调用。CSES 大多数题是单组输入但如果你在本地做多组对拍这个问题会频繁出现。4.5 浮点数比较用等号导致 WA现象涉及浮点输出的题目本地看着一样提交后 WA。原因浮点运算有精度误差直接用比较两个浮点数几乎必然失败。解决用fabs(a - b) 1e-6或1e-9做容差比较。如果题目要求输出固定小数位用printf(%.6f\n, ans)并注意四舍五入。CSES 里浮点题不多但一旦遇到这个坑几乎人人踩过。5. 进阶技巧用 CSES-Problem-Set 做能力矩阵与复盘5.1 建立题目难度与知识点二维矩阵刷到一定量后单纯按分类刷会陷入舒适区。我一般会建一个二维表横轴是 CSES 的官方分类纵轴是难度自评1 到 5每道题标记实际耗时和是否独立完成。这样能直观看出哪些分类的哪些难度层是薄弱点。比如你发现dp分类里难度 3 的题平均耗时是其他分类的两倍那下一步就集中刷这个区间的题。分类难度1难度2难度3难度4难度5introductory5题3题1题0题0题sorting2题4题3题1题0题graph1题3题5题2题1题dp0题2题4题3题1题表格里的数字是你实际完成的题数不是题目总数。通过对比完成度和耗时可以决定下一周的训练重点。我一般每周日晚上花 20 分钟更新这个表然后定下周的刷题计划。5.2 用“三遍法”复盘一道 CSES 题第一遍限时独立做卡住超过 40 分钟就看题解但只看思路不看代码。第二遍关掉题解自己实现写完和题解对比时间复杂度和边界处理。第三遍一周后重新做一遍如果还能独立写出最优解这道题才算真正掌握。这个方法听起来笨但对付 CSES 里那些“看起来会、写起来错”的题特别有效。我自己的经验是图论和 DP 的题至少要走完三遍否则过两周就只剩模糊印象。5.3 把模板库做成可检索的本地文档模板多了以后找起来也麻烦。我一般用grep加注释关键词来检索。比如每个模板文件头部写一行注释// tags: dsu, union-find, path-compression需要时用grep -r tags:.*dsu templates/快速定位。另外每个模板文件里保留一个最小可运行示例方便直接复制出来改。这个习惯坚持半年后你会发现遇到新题时第一反应不是“这题怎么做”而是“这题能用哪个模板改”。最后说一个我自己的教训早期刷 CSES-Problem-Set 时我追求 AC 数量刷完 150 题后回头一看能独立写出来的不到三分之一。后来改成每道题必须沉淀模板或写复盘笔记速度慢了一半但三个月后遇到变体题的反应速度明显提升。刷题的价值不在数量而在你能否把每道题变成自己工具箱里的一把刀。希望帮到你。本文还有配套的精品资源点击获取
