简介：《CSES Problem Set详解》配套的C++解题源码包，面向准备编程竞赛（如ACM/ICPC）或强化算法基础的学习者。题解将CSES题集中入门到进阶的练习按主题拆解，涵盖数组/字符串基础、排序与搜索、动态规划（如背包、硬币兑换）、图论与树（如最小生成树、最短路径）、贪心算法、线段树与并查集、数论与组合、回溯剪枝、位运算及模拟等核心算法方向，每个题目对应一个独立cpp文件，便于对照题面理解解题思路与实现细节。压缩包共28个C++源文件，整体仅19KB，体积轻量、按题号组织，适合配合官方题集逐题练习或赛后复盘。目前已有254人学习使用，无论是系统刷题、准备机试面试，还是补强特定算法模块，都能从这套题解中获得直接可运行的参考代码与清晰的实现逻辑，代码风格简洁，适合作为竞赛模板复用。

1. CSES Problem Set：一套把算法训练拉回地面的 300 题题库

刷 LeetCode 刷到一百题时我一度很膨胀，觉得自己什么套路都见过。直到去面试被问了一道需要自己设计状态转移的题，才发现自己只会套模板，换个壳就懵。后来一个打 ICPC 的朋友甩给我一个链接，说把这套题刷完再来聊算法。那套题就是 CSES Problem Set——赫尔辛基大学维护的一个算法题库，三百道题按专题排好，从入门到劝退一气呵成，没有会员墙，没有按通过率隐藏题目的机制，每一道都是裸题，不给业务场景包装，逼你直面算法本身。适合准备竞赛、面试前想系统过一遍数据结构和算法、以及被花哨题面惯坏了想回归底子的人。这篇我把它的专题结构、提交流程、核心专题的代码套路和最容易翻车的几个坑都拆一遍。

2. 本地环境与提交流程：C++17 编译选项和三分钟跑通第一题

2.1 为什么选 C++：CSES 的时限设计偏向编译型语言

CSES 的大部分题目时限是 1 秒，内存限制 512 MB。这个时限对 Python 很不友好，尤其是 Sorting and Searching 和 Graph Algorithms 里那些卡常数的题，Python 用同样的复杂度也经常超时。C++17 是题库默认支持最完整的语言标准，用bits/stdc++.h头文件可以省掉一堆 include 的琐事。如果你只打算用 Python 刷，前面二三十道入门题没问题，到了 Creating Strings 这类全排列题目就开始难受了。

我一般会在本地建一个干净的模板文件，编译选项固定为：

g++ -std=c++17 -O2 -pipe -static solution.cpp -o solution

-O2是必须的，CSES 的测评机开了 O2 优化，本地不开 O2 测出来的时间没有参考价值。-pipe加快编译速度，-static静态链接可以避免测评环境缺动态库，但如果你用的是较新版本的 GCC，-static可能链接失败，这时候去掉-static就行了。编译通过后先用样例测一遍，再跑你自己构造的边界数据。

2.2 跑通 Weird Algorithm：提交格式、输入输出和编译参数

CSES 的提交页长得很朴素，左边选语言，右边粘贴代码，下面一个提交按钮。第一题 Weird Algorithm 的题意是：给一个正整数 n，如果它是偶数就除以 2，是奇数就乘以 3 加 1，把整个序列输出。这题刁钻的地方在于 n 最大可以到 10^6，序列长度会很长，你必须在每两个数字之间输出空格，结尾换行。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n; cin >> n; while (n != 1) { cout << n << ' '; if (n % 2 == 0) n /= 2; else n = 3 * n + 1; } cout << 1 << '\n'; return 0; }

这里用long long是必须的，虽然输入 n 只有 10^6，但 Collatz 序列在迭代过程中可能冲到很大，用int会溢出变成负数，然后陷入死循环。ios::sync_with_stdio(false)和cin.tie(nullptr)这两行是给 cin/cout 提速的，如果你混用printf和cin就千万别关同步，否则输出顺序会错乱。提交时语言选 "GNU C++17"，不要选 C++11 或 C++14，因为有些题的数据结构实现在旧标准下编译不过。

2.3 你的本地测试模板：从文件读入到对拍脚本

CSES 的题目输入输出都在 stdin/stdout 上，本地测试最方便的方式是建一个test.sh脚本，把样例存成sample_in.txt，把输出重定向到文件再对比：

#!/bin/bash g++ -std=c++17 -O2 solution.cpp -o solution ./solution < sample_in.txt > my_out.txt diff my_out.txt sample_out.txt

diff没有输出就代表样例过了。但这个流程只验证样例，样例外全是坑。我通常对拍时用 Python 写一个暴力解，再写一个小数据生成器，交替跑暴力解和正解，几百组数据跑完没问题才敢提交。生成器的关键是数据要小、要偏，比如生成一个 1000 以内的随机数组，专门喂边界值：0、1、最大值、两个相同元素。对拍脚本的写法很固定：

#!/bin/bash for i in $(seq 1 1000); do python3 gen.py > input.txt ./solution < input.txt > out1.txt python3 force.py < input.txt > out2.txt if ! diff -q out1.txt out2.txt; then echo "WA on test $i" break fi done

注意gen.py里每次要重新生成数据，不要在循环外层固定种子，否则对拍的覆盖范围很窄。如果你的正解本身是 Python 写的，对拍就把前两行里./solution换成python3 solution.py就行。

3. 入门与排序专题：先吃掉送分题，再谈优化

3.1 Missing Number 与 Repetitions：输入处理的两个常见反模式

Introductory Problems 前几题是给新手找自信的，但越简单的题越能看出代码习惯。Missing Number 的题意是：1 到 n 里缺了一个数，给你剩下的 n-1 个数，找出缺的那个。标准做法是求和相减，但有个反模式是存数组再排序找缝隙，n 最大到 2×10^5 这样干也能过，但排序多出的 O(n log n) 完全没有必要。

long long n, sum = 0, x; cin >> n; for (int i = 0; i < n - 1; i++) { cin >> x; sum += x; } cout << n * (n + 1) / 2 - sum << '\n';

n * (n + 1) / 2这里要注意乘法顺序，n 最大 2×10^5，乘积是 2×10^10，必须用long long接收。sum也必须是long long，用int会在累加过程中溢出，WA 得很隐蔽，因为你的输出是一个看起来完全合理的小数字。

Repetitions 是求字符串里最长连续相同字符段，n 最大 10^6，O(n) 一遍扫过。这道题真正想考察的是你有没有养成读入字符串后立刻遍历的习惯，而不是调find之类的函数。一个常见的坑是有人会用getline(cin, s)读字符串，如果前面用cin读过整数，残留的换行符会被getline读到，得到空串。用cin >> s可以避免这个问题，因为它会自动跳过前导空白。

3.2 排序专题：从收集数字到电影院排队的贪心直感

Sorting and Searching 是 CSES 里题量最大的专题之一，三十多道题，从二分到摩尔投票都有。其中 Collecting Numbers 这道题很有意思：给你一个 1 到 n 的排列，你可以反复执行一个操作，每次从头到尾扫一遍，收集当前能收集的数字（必须按递增顺序），问最少扫几轮。直觉解法是记录每个数字的位置，然后遍历 1 到 n，每次看数字 i 和 i-1 的位置关系，如果 i 的位置在 i-1 前面，就说明需要新开一轮。

int n; cin >> n; vector<int> pos(n + 1); for (int i = 1; i <= n; i++) { int x; cin >> x; pos[x] = i; } int rounds = 1; for (int i = 2; i <= n; i++) { if (pos[i] < pos[i - 1]) rounds++; } cout << rounds << '\n';

这里pos数组的含义是「数字 x 在排列中的位置」，建立这个反向映射是这题的题眼。你要是直接模拟扫描过程，复杂度是 O(n^2)，n 到 2×10^5 就超时。这个专题里很多题都是「正向模拟不可行，建立索引/映射后贪心」的套路，遇到排序专题的题，先想想能不能用一个数组记录某种位置信息，再想递推。

电影院排队那道 Movie Festival 是经典的区间调度贪心：按结束时间排序，然后能选就选。这个思路在 CSES 的 Sorting and Searching 里反复出现，比如求最多不相交区间、最少需要删掉多少区间来让剩余区间不重叠，都是同一个模板。贪心的证明你可以不看，但边界条件必须记住：排序按结束时间升序，如果结束时间相同再按开始时间升序。

3.3 数论入门的边界：Counting Divisors 的试除与素数筛分界线

Mathematics 专题里 Counting Divisors 是道典型的边界题：给 q 个查询，每个查询一个整数 x，x 最大 10^6，求 x 的因子个数。有个解法是预处理出 1 到 10^6 每个数的因子个数，用类似埃氏筛的思路：

const int MAX = 1000000; vector<int> divCnt(MAX + 1, 0); for (int i = 1; i <= MAX; i++) { for (int j = i; j <= MAX; j += i) { divCnt[j]++; } }

这段代码的复杂度是调和级数 O(n log n)，对 10^6 的量级来说约 1400 万次操作，1 秒时限内能过。j += i这一步是精髓，它保证每个数只在它所有因子的循环里被加一次，而不是对每个数做一次 O(sqrt(x)) 的试除。这道题很多人拿到就直接对每个查询做for (int i = 1; i * i <= x; i++)试除，q 到 10^5 时总操作量超过 10^8，就会超时。

如果你要试除，也有一点可以优化：只枚举到sqrt(x)，每找到一个因子 i，就把 i 和 x/i 一并处理。但要注意完全平方数，比如 x=36，i=6 时因子 6 会被算两次。这种细节在 CSES 的数学题里出现频率极高，WA 的经典原因就是忘了判i * i != x。从这题开始，CSES 会把你对复杂度的直觉从「能跑就行」纠正到「必须精确估算操作次数」。

4. 动态规划与图论：CSES 里最值得啃的两个硬骨头

4.1 DP 专题的递推顺序问题：从 Dice Combinations 到 Book Shop

DP 专题是 CSES 的核心资产，二十多道题把背包、区间 DP、状压 DP、概率 DP 全过了一遍。Dice Combinations 是开门题：你有无限个 1 到 6 的骰子面，问凑出 n（n 最大 10^6）有几种方式，模 10^9+7。递推式是dp[i] = dp[i-1] + ... + dp[i-6]，但很多人第一次写会搞错枚举方向。

vector<long long> dp(n + 1); dp[0] = 1; for (int i = 1; i <= n; i++) { for (int d = 1; d <= 6; d++) { if (i - d >= 0) { dp[i] = (dp[i] + dp[i - d]) % MOD; } } }

这里外层枚举的是和 i，内层枚举骰子面 d，表示「最后一步投出 d 来凑到 i」。如果把内外层颠倒，变成外层枚举骰子，就变成组合数而不是排列数了，结果会错。这个「外层目标和、内层选择项」的顺序是许多 DP 的通用骨架，在 Coin Combinations I 和 II 两题里被单独拿出来考。

Book Shop 是 0/1 背包，n 本书，每本有价格和页数，预算 m 内求最大页数。这题要是跟 Coin Combinations 一样用二维数组会内存吃紧，n 和 m 都是 10^5，二维数组 10^10 直接爆内存。必须用滚动数组，而且内层要倒序枚举容量：

vector<int> dp(m + 1, 0); for (int i = 0; i < n; i++) { for (int j = m; j >= price[i]; j--) { dp[j] = max(dp[j], dp[j - price[i]] + pages[i]); } }

j从大到小枚举是为了保证每个物品只被取一次，因为dp[j - price[i]]访问的是上一层的状态，倒序更新时它还没被这一层的当前物品污染。你要是写成正序枚举，就变成完全背包了，这是 0/1 背包和完全背包唯一代码层面的区别，也是 DP 专题里最容易 WA 的地方。数组下标从price[i]开始而不是从 0 开始，是省掉一个if判断的小技巧。

4.2 图论的输入坑：无向图、自环与多边在邻接表里的处理

Graph Algorithms 专题有一半的题不卡算法卡输入处理。最典型的是 Building Roads：给定 n 个城市和 m 条已建成的路，问最少还要修几条路才能让所有城市连通。这题本质是求连通分量个数减一，用 BFS 或 DSU 都能做。但图的输入不是一棵树，会有自环和重边，如果你用邻接矩阵存储，n 到 10^5 直接 MLE；用邻接表必须把无向边存两次。

vector<vector<int>> adj(n + 1); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); }

自环的情况是a == b，这时候adj[a].push_back(b)会把自己存进去，遍历时 BFS 可能重复入队，但访问标记能挡住，不会死循环。重边的问题是邻接表里同一个邻居出现多次，BFS 时每次都要走一遍这条边，最坏情况多条重边会让复杂度从 O(n+m) 退化到 O(n+m^2)，在稠密图上会超时。我的习惯是无脑加一个unordered_set<pair>判重，但注意自定义类型作为 key 需要自己写哈希函数，不如直接用二维数组存边集然后转邻接表，或者干脆在插入前查重。

图论专题里用vector<vector<int>>是最直观的，但遇到 n 到 2×10^5 时大量使用嵌套 vector 会因为内存不连续而慢，换成链式前向星会快不少，但代码复杂度上去了。我的权衡是：n 小于 10^5 用邻接表，n 更大或者需要卡常数时用前向星。

4.3 从 Grid 到最短路：用题目列表给自己画训练地图

CSES 的 Graph Algorithms 专题里有一部分是网格图上的 BFS，比如 Labyrinth 求最短路径并输出路径。这类题跟普通图 BFS 的区别是：状态不只包含节点编号，还包含坐标和方向。BFS 求最短路的正确性是建立在边权都等于 1 的基础上，网格图上四个方向的移动代价都是 1，所以 BFS 第一次访问到终点就是最短路。

int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; vector<vector<char>> grid(n, vector<char>(m)); vector<vector<int>> dist(n, vector<int>(m, -1)); queue<pair<int, int>> q; dist[sx][sy] = 0; q.push({sx, sy}); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int nx = x + dx[d], ny = y + dy[d]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (grid[nx][ny] == '#' || dist[nx][ny] != -1) continue; dist[nx][ny] = dist[x][y] + 1; q.push({nx, ny}); } }

dist数组初始化为 -1 一举两得，既当访问标记又存距离。越界检查和墙壁检查的顺序是先越界再访问，不要反过来，因为越界坐标访问grid会触发未定义行为，本地可能崩溃，测评机上可能随机 WA。输出路径时要在 BFS 过程中维护一个pre数组记录每个格子是从哪个方向来的，然后用反向回溯拼路径，注意回溯的顺序是终点的上一个、上上个……最后反转字符串。

Range Queries 和 Tree Algorithms 也是两个大专题，线段树、树状数组、LCA、树形 DP 都有覆盖。我的建议是：DP 专题和 Graph 专题先刷透，Range Queries 可以往后放，因为线段树的代码量适合在状态好时精刷，不适合赶进度。

5. 避坑指南：CSES 提交中最常见的七个翻车现场

5.1 翻车一：long long 缺失导致的大数溢出

现象：本地样例全过，提交后 WA 在 Test 3 或更后的测试点，而且输出看起来很合理。

原因：CSES 的很多题目明面上给了 10^5 或 10^6 的限制，但中间计算会超过 32 位有符号整数的范围。比如 2×10^5 个数求中位数，排序没问题，但求前缀和时中间值可能到 2×10^10。凡是题目里包含「求和」「乘积」「n*(n+1)/2」这类模式，你要默认它需要long long。

解决：把int全部换成long long，只需要在思路里确认哪个变量有平方或者累加的含义，不需要追求精确到每个变量，统一用long long是最省心也最稳的。如果担心long long也不够，题目里一般会给出模数，模 10^9+7 的题所有中间结果都必须先模再加。

5.2 翻车二：输入输出同步关闭后的混用

现象：用了ios::sync_with_stdio(false)之后，又调用了printf或者puts，输出的顺序不对，或者某些输出直接丢掉。

原因：sync_with_stdio(false)会切断 C 和 C++ 两套 I/O 流的同步，混用之后缓冲区刷新时机不可控，输出顺序会乱。

解决：要么完全用cin/cout，要么完全用scanf/printf。我自己用 C++ 刷 CSES 时只允许cin/cout，并且所有输出统一用cout << x << '\n'，不要这一行用endl下一行用'\n'。endl会强制刷新缓冲区，实际执行时频繁 flush 会让 IO 慢好几倍。

5.3 翻车三：vector<bool>的性能陷阱

现象：用vector<bool> visited做 BFS，n 到 10^6 时超时，但复杂度算起来应该能过。

原因：vector<bool>是 C++ 里出了名的特化，每个元素只占 1 bit，读取时要经过位运算代理对象，写入时会整字节重写，频繁随机访问时比裸bool数组慢一个数量级。

解决：BFS、DFS 的访问标记用vector<char>或者直接用 C 数组bool vis[n]。vector<char>虽然每个元素占一个字节，但访问是直接内存寻址，速度最快。这道坑在 n 到 10^6 的图论题里几乎必踩，开了 O2 也救不回来。

5.4 翻车四：递归深度爆栈

现象：图论题用 DFS 递归遍历一棵链状的树，n 到 10^5 直接崩溃，返回Runtime Error或者Segmentation fault。

原因：默认栈空间在 Linux 上约 8 MB，DFS 深度到 10^5 时每层递归的栈帧累积，瞬间超过栈上限。

解决：方案一是在编译选项里加-Wl,--stack=268435456来扩大栈空间，但这只对你本地有效，CSES 的测评机仍然会爆；方案二是改成手写栈的迭代 DFS；方案三是把 DFS 改成 BFS，图论题里大部分 DFS 能做的 BFS 也能做。我通常把图论的递归dfs全部改成迭代 +stack<int>，入栈时标记访问而不是出栈时标记，避免重复入栈。

5.5 翻车五：DP 数组维度顺序影响缓存命中

现象：二维 DP 用dp[i][j]和dp[j][i]的遍历方向写反了，小数据全对，大数据超时。

原因：C++ 的二维数组在内层是按行连续存储的，如果你外层枚举列、内层枚举行，每次访问都要跨一大段内存跳跃，缓存命中率骤降。

解决：写 DP 时把内层循环的下标放在数组的第二个维度。比如 0/1 背包dp[i][j]的 i 是物品、j 是容量，那么循环应该外层 i 内层 j，因为dp是vector<vector<int>> dp(n+1, vector<int>(m+1))，j是第二个维度，访问连续内存。如果状态定义强制你外层枚举 j，那就把数组转置成dp[j][i]，效果一样但快得多。

5.6 翻车六：map 做 DP 导致的无谓慢

现象：用unordered_map<int, int>存储 DP 状态，n 到 10^5 时跑得很慢，甚至超时。

原因：CSES 的测评机器对unordered_map的哈希函数处理不够快，而且哈希表在扩容时会有全量 rehash，频繁插入耗时。

解决：优先用 vector 数组做 DP，只有当状态值域很大或者状态本身是pair才用 map。比如 Longest Increasing Subsequence 用二分 +lower_bound时，我直接在vector<int> tails上操作，完全不需要 map。

5.7 翻车七：还有一类 WA 与 read/scanf 的返回值有关

现象：输入的测试数据里每行数字之间有多个空格或换行，scanf和cin都能自动跳过，但如果你用了scanf("%d", &x)且不加返回值检查，在文件末尾多一个换行时可能读到垃圾值。

原因：scanf返回成功匹配的项数，如果读到EOF返回EOF。这个问题在 CSES 上不多见，因为它的输入格式规整，但养成了检查返回值的习惯，至少在自己造数据时不会翻车。

解决：用while (cin >> x)或者while (scanf("%d", &x) != EOF)处理不定长的输入，不要用for循环固定次数。

6. 从 AC 到理解：用「三遍法」和复杂度记录表把 CSES 吃透

我刷 CSES 刷到一百题左右时出现了一个危险信号：很多 DP 题我看一眼知道思路，但让手写时总有几步卡壳。后来我给自己定了一套「三遍法」：第一遍不看题解独立 AC；第二遍过一周重写同一题，要求一次通过且运行时间不超过第一次的 130%；第三遍在月度复盘时只写伪代码和复杂度分析，不写完整实现。这个习惯帮我克服了「看懂了等于会了」的幻觉。

另一个很实用的工具是给每道题建一行记录，格式很简单：题号、专题、我的第一遍耗时、AC 状态、核心手法、复杂度。比如：

表格信息不是为了给别人看，是为了让我自己隔一个月扫一眼就能想起这题考的是什么。复杂度那栏尤其重要——CSES 的题基本不会考你一个「理论上能跑」的算法，而是精确到操作次数能不能在 1 秒内完成。我算复杂度时统一按 5×10^8 次简单操作作为一个时限 1 秒的安全上限，超过就换思路。

最后说一个我直到现在都在用的习惯：每道题提交前先跑一遍自己构造的边界用例——输入最大值、最小值、重复元素、单元素、完全逆序。这个动作花不了三十秒，但它帮我挡下了至少二十次 WA。有一回我在 Graph 题里用邻接表存图，构造了一个 n=1、m=0 的用例，立刻发现 BFS 从 1 出发会越界访问空节点，当场修掉，省了一轮评测。从那以后我每次提交前都强制走一遍这个流程，CSES 刷完三百题后我已经不需要评测机告诉我哪里错了。希望帮到你。

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