CSES-Problem-Set 高效刷题指南：从300道中精选80道提升算法能力

简介：这份资源是面向C++学习者和算法竞赛备赛者的CSES Problem Set题解代码合集，针对希望系统提升算法基础与问题解决能力的程序员，覆盖从入门到进阶的完整训练路径。压缩包共28个文件，全部为cpp源码，整体约19KB，按CSES官方分类组织，涵盖基础算法、动态规划、图论与树、贪心、数据结构、数学、回溯剪枝、位运算、模拟建模及编码技巧等模块，如背包、硬币兑换、最小生成树、线段树、并查集、质数判断等经典题目均有对应实现。目录结构清晰，便于按专题检索与对照学习。目前已有256人学习下载，适合准备ACM/ICPC、Google Code Jam等编程比赛或提升面试表现的人群，通过研读这些代码可快速掌握状态转移、DFS/BFS、贪心策略与位运算等核心技巧，并培养解决复杂问题的思维方式。

1. CSES-Problem-Set 到底练什么：从 300 道题里挑出真正提升算法能力的那 80 道

如果你刷过一段时间算法题，大概率听过 CSES-Problem-Set 这个名字。它是一套结构化的算法练习题集，覆盖从入门模拟到动态规划、图论、数论、字符串等十几个专题，题目总量在 300 道左右。很多人第一次打开它的目录会觉得“怎么这么朴素”，没有花哨的界面，没有排行榜，也没有题解社区，但恰恰是这种极简结构，让它成为检验自己算法基本功的试金石。

它解决的问题很具体：你可能刷了不少题，但知识点是散的，遇到新题不知道往哪个方向想。CSES-Problem-Set 按专题分组，每个专题内部难度递进，能帮你把“会做一道题”变成“会做一类题”。适合谁？适合已经掌握一门编程语言基础语法、想系统补算法短板的人，也适合准备技术面试但不想被碎片化题单牵着走的开发者。常见做法是把它当作主线，配合自己的弱项专题做针对性突破，而不是从头到尾无脑刷完。

2. 把 CSES-Problem-Set 跑起来：环境、输入输出与本地判题的最小闭环

2.1 为什么本地判题比在线提交更值得先做

在线判题平台当然方便，但 CSES-Problem-Set 的题目输入输出格式非常规整，几乎每道题都是“读入若干行，输出一个结果”。这意味着你完全可以在本地搭一个最小判题脚本，用自己的测试数据反复验证。这样做的好处是：调试时不受网络影响，能打印中间变量，能构造边界用例，能对比暴力解和优化解的输出差异。我一般会建议先本地跑通 5 到 10 道题，把输入输出习惯固定下来，再去在线提交，效率会高很多。

2.2 用 Python 搭一个最小本地判题脚本

下面这个脚本假设你把每道题的输入文件命名为in.txt，期望输出命名为out.txt，自己的解法保存为solution.py。脚本会运行解法，对比输出，并给出差异提示。

import subprocess import sys import os def run_solution(sol_path, input_data): """运行解法文件，传入输入字符串，返回标准输出""" result = subprocess.run( [sys.executable, sol_path], input=input_data, text=True, capture_output=True, timeout=5 # 单题超时 5 秒，防止死循环 ) if result.returncode != 0: print("运行错误：", result.stderr) return None return result.stdout.strip() def judge(sol_path, in_file, out_file): """对比解法输出与期望输出""" with open(in_file, 'r') as f: input_data = f.read() with open(out_file, 'r') as f: expected = f.read().strip() actual = run_solution(sol_path, input_data) if actual is None: return False if actual == expected: print("通过") return True else: print("未通过") print("期望输出：", expected[:200]) print("实际输出：", actual[:200]) return False if __name__ == "__main__": # 用法：python judge.py solution.py in.txt out.txt sol = sys.argv[1] in_f = sys.argv[2] out_f = sys.argv[3] judge(sol, in_f, out_f)

逻辑说明：subprocess.run把输入数据喂给解法进程，capture_output=True捕获标准输出和错误，timeout=5防止死循环拖死本地机器。对比时先strip()去掉首尾空白，避免因为换行符差异误判。参数方面，超时时间可以根据题目复杂度调整，图论题可以放宽到 10 秒；输入文件建议用题目自带的样例，再自己补 2 到 3 个边界用例。

2.3 输入输出加速：别让 I/O 成为你的瓶颈

CSES-Problem-Set 里有不少题目输入量在 10^5 行以上，用 Python 的input()逐行读会明显拖慢速度。常见做法是改用sys.stdin.read().split()一次性读入，再按需解析。下面是一个模板：

import sys def main(): data = sys.stdin.read().split() # data 是一个字符串列表，按空白字符切分 n = int(data[0]) arr = list(map(int, data[1:1+n])) # 后续处理 print(sum(arr)) if __name__ == "__main__": main()

逻辑说明：sys.stdin.read()把整个输入读成一个字符串，.split()按空白切分，避免了逐行调用的开销。参数方面，如果题目输入包含多组测试用例，需要自己维护一个索引指针，按顺序取用。注意：这种方法不适合输入中包含空行或需要保留行结构的题目，遇到那种情况再换回逐行读取。

3. 专题突破路线：动态规划、图论、数论各自怎么刷才不白刷

3.1 动态规划：从记忆化搜索过渡到递推

CSES-Problem-Set 的动态规划专题大约有 20 多道题，难度从一维状态到区间 DP、树形 DP 都有。很多人卡在“想不到状态定义”上。我的建议是：先写记忆化搜索，把递归结构和状态转移写清楚，再改写成递推。这样做的好处是，递归版本更贴近人类思维，容易验证正确性；递推版本则能帮你理解状态依赖顺序和空间优化。

以“骰子组合”类问题为例，状态定义是dp[i]表示凑出总和i的方案数，转移是dp[i] = sum(dp[i-k])，其中k是骰子面数。记忆化版本直接递归加缓存，递推版本则从小到大填表。参数方面，注意取模运算的位置，通常是在每次加法后取模，避免整数溢出。Python 里整数不会溢出，但取模能控制数值大小，加快运算。

3.2 图论：先把建图模板固定下来

图论专题覆盖最短路、最小生成树、拓扑排序、强连通分量等。题目输入格式通常是“先给节点数和边数，然后每行一条边”。我一般会准备一个建图模板，用邻接表存储，需要时再切换成邻接矩阵或边列表。

from collections import defaultdict def build_graph(n, edges, directed=False): """n: 节点数，edges: [(u, v, w), ...]""" graph = defaultdict(list) for u, v, w in edges: graph[u].append((v, w)) if not directed: graph[v].append((u, w)) return graph

逻辑说明：defaultdict(list)避免了对每个节点初始化空列表的麻烦。参数方面，directed控制是否有向图；如果边权都是 1，可以省略权重字段，直接用graph[u].append(v)。注意：节点编号通常从 1 开始，用字典存储时不需要减一，但如果用列表数组，记得开n+1的大小。

3.3 数论：筛法、快速幂和模逆元是三大件

数论专题里出现频率最高的是质数筛、快速幂和模逆元。CSES-Problem-Set 的题目往往把这些基础工具组合起来考。比如“计数约数”需要筛法预处理，“大数幂取模”需要快速幂，“组合数取模”需要预计算阶乘和逆元。我一般会准备一个数论工具模块，随用随取。

def sieve(n): """返回 1 到 n 的质数列表""" is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False for i in range(2, int(n**0.5) + 1): if is_prime[i]: for j in range(i*i, n + 1, i): is_prime[j] = False return [i for i in range(2, n + 1) if is_prime[i]] def fast_pow(base, exp, mod): """计算 base^exp % mod""" result = 1 base %= mod while exp > 0: if exp & 1: result = (result * base) % mod base = (base * base) % mod exp >>= 1 return result

逻辑说明：筛法用埃拉托斯特尼筛，时间复杂度 O(n log log n)，适合 n 在 10^6 以内。快速幂用二进制拆分指数，时间复杂度 O(log exp)。参数方面，mod通常是 10^9+7 或 10^9+9，题目会明确给出。注意：筛法里i*i可能溢出，Python 里不用担心，但 C++ 里需要用long long。

4. 避坑与排查：CSES-Problem-Set 刷题时最容易翻车的 5 个地方

4.1 现象：本地样例通过，在线提交却报错

原因：最常见的是输入输出格式差异。CSES-Problem-Set 的题目通常要求输出末尾有换行，但有些题目对空格敏感。另外，Python 的print默认换行，但如果你用sys.stdout.write就要自己加\n。解决：提交前用repr()打印自己的输出，检查末尾是否有不可见字符；对比题目样例的精确格式，必要时手动补换行。

4.2 现象：递归解法在深递归时崩溃

原因：Python 默认递归深度限制是 1000，图论或树形 DP 的递归深度可能超过这个值。解决：在代码开头加sys.setrecursionlimit(300000)，同时注意递归层数过多可能导致栈内存不足，能改递推就改递推。参数方面，300000 是常见上限，再大可能触发系统限制。

4.3 现象：动态规划数组开小了导致越界

原因：状态维度或取值范围估计不足。比如题目说总和不超过 10^5，但你没注意到中间状态可能超过这个值。解决：先读清楚题目约束，把数组大小开到约束上限再加 10 的余量。Python 列表越界会直接报错，C++ 则可能静默出错，更危险。

4.4 现象：图论题用 BFS 却超时

原因：没有标记已访问节点，导致重复入队。解决：BFS 必须维护visited集合或数组，入队时立即标记，而不是出队时标记。参数方面，visited可以用布尔列表或集合，列表更快但需要知道节点范围。

4.5 现象：数论题结果对不上，差一个模数

原因：取模运算的时机不对，或者用了负数取模。解决：统一在每次加法、乘法后取模；Python 的%对负数返回正数，但其他语言可能不同。如果题目要求输出模 10^9+7 的结果，所有中间结果都要在这个模下计算，不要最后才取模。

5. 从刷完到内化：用错题回溯和限时模拟把 CSES-Problem-Set 变成自己的东西

刷完 CSES-Problem-Set 的 300 道题不等于掌握，真正内化需要两步：错题回溯和限时模拟。错题回溯是指每道做错或卡住的题，隔三天再写一遍，如果还是卡，就去看别人的思路，然后关掉题解自己重写。限时模拟是指挑一个专题，给自己 2 小时，模拟比赛环境，不查资料，不调试太久，逼自己在压力下做决策。

我自己的习惯是维护一个错题表格，记录题目编号、错误原因、正确思路的关键词。下面是一个示例表格结构：

这个表格不需要很复杂，关键是重做日期要真的执行。另外，限时模拟时建议用本地判题脚本，提前准备好输入文件，避免在在线平台上等待提交结果浪费时间。参数方面，2 小时是常见模拟时长，可以按专题难度调整到 1.5 或 3 小时。

还有一个技巧：把 CSES-Problem-Set 的题目按“暴力解 → 优化解”两版都写一遍。暴力解用来验证正确性，优化解用来满足时间限制。这样你能清楚看到优化点在哪里，是空间换时间，还是数据结构升级。我一般会在暴力解通过后，先分析时间复杂度瓶颈，再决定用前缀和、二分、线段树还是其他结构。这个习惯让我在遇到新题时，能更快定位到可能的优化方向。

最后说一个血泪经验：不要为了刷题数量跳过难题。CSES-Problem-Set 里那些让你卡住两小时的题，恰恰是能力边界所在。卡住时先自己想 30 分钟，再去看题解，看完关掉题解自己重写，写完再对比差异。这个过程很痛苦，但效果比刷十道简单题好得多。希望帮到你。

本文还有配套的精品资源，点击获取