简介《CSES Problem Set详解》配套的C解题源码包面向准备编程竞赛如ACM/ICPC或强化算法基础的学习者。题解将CSES题集中入门到进阶的练习按主题拆解涵盖数组/字符串基础、排序与搜索、动态规划如背包、硬币兑换、图论与树如最小生成树、最短路径、贪心算法、线段树与并查集、数论与组合、回溯剪枝、位运算及模拟等核心算法方向每个题目对应一个独立cpp文件便于对照题面理解解题思路与实现细节。压缩包共28个C源文件整体仅19KB体积轻量、按题号组织适合配合官方题集逐题练习或赛后复盘。目前已有254人学习使用无论是系统刷题、准备机试面试还是补强特定算法模块都能从这套题解中获得直接可运行的参考代码与清晰的实现逻辑代码风格简洁适合作为竞赛模板复用。1. CSES Problem Set一套把算法训练拉回地面的 300 题题库刷 LeetCode 刷到一百题时我一度很膨胀觉得自己什么套路都见过。直到去面试被问了一道需要自己设计状态转移的题才发现自己只会套模板换个壳就懵。后来一个打 ICPC 的朋友甩给我一个链接说把这套题刷完再来聊算法。那套题就是 CSES Problem Set——赫尔辛基大学维护的一个算法题库三百道题按专题排好从入门到劝退一气呵成没有会员墙没有按通过率隐藏题目的机制每一道都是裸题不给业务场景包装逼你直面算法本身。适合准备竞赛、面试前想系统过一遍数据结构和算法、以及被花哨题面惯坏了想回归底子的人。这篇我把它的专题结构、提交流程、核心专题的代码套路和最容易翻车的几个坑都拆一遍。2. 本地环境与提交流程C17 编译选项和三分钟跑通第一题2.1 为什么选 CCSES 的时限设计偏向编译型语言CSES 的大部分题目时限是 1 秒内存限制 512 MB。这个时限对 Python 很不友好尤其是 Sorting and Searching 和 Graph Algorithms 里那些卡常数的题Python 用同样的复杂度也经常超时。C17 是题库默认支持最完整的语言标准用bits/stdc.h头文件可以省掉一堆 include 的琐事。如果你只打算用 Python 刷前面二三十道入门题没问题到了 Creating Strings 这类全排列题目就开始难受了。我一般会在本地建一个干净的模板文件编译选项固定为g -stdc17 -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 C17不要选 C11 或 C14因为有些题的数据结构实现在旧标准下编译不过。2.3 你的本地测试模板从文件读入到对拍脚本CSES 的题目输入输出都在 stdin/stdout 上本地测试最方便的方式是建一个test.sh脚本把样例存成sample_in.txt把输出重定向到文件再对比#!/bin/bash g -stdc17 -O2 solution.cpp -o solution ./solution sample_in.txt my_out.txt diff my_out.txt sample_out.txtdiff没有输出就代表样例过了。但这个流程只验证样例样例外全是坑。我通常对拍时用 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^6O(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; vectorint 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 个查询每个查询一个整数 xx 最大 10^6求 x 的因子个数。有个解法是预处理出 1 到 10^6 每个数的因子个数用类似埃氏筛的思路const int MAX 1000000; vectorint 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 一并处理。但要注意完全平方数比如 x36i6 时因子 6 会被算两次。这种细节在 CSES 的数学题里出现频率极高WA 的经典原因就是忘了判i * i ! x。从这题开始CSES 会把你对复杂度的直觉从「能跑就行」纠正到「必须精确估算操作次数」。4. 动态规划与图论CSES 里最值得啃的两个硬骨头4.1 DP 专题的递推顺序问题从 Dice Combinations 到 Book ShopDP 专题是 CSES 的核心资产二十多道题把背包、区间 DP、状压 DP、概率 DP 全过了一遍。Dice Combinations 是开门题你有无限个 1 到 6 的骰子面问凑出 nn 最大 10^6有几种方式模 10^97。递推式是dp[i] dp[i-1] ... dp[i-6]但很多人第一次写会搞错枚举方向。vectorlong 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 直接爆内存。必须用滚动数组而且内层要倒序枚举容量vectorint 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用邻接表必须把无向边存两次。vectorvectorint 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(nm) 退化到 O(nm^2)在稠密图上会超时。我的习惯是无脑加一个unordered_setpair判重但注意自定义类型作为 key 需要自己写哈希函数不如直接用二维数组存边集然后转邻接表或者干脆在插入前查重。图论专题里用vectorvectorint是最直观的但遇到 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}; vectorvectorchar grid(n, vectorchar(m)); vectorvectorint dist(n, vectorint(m, -1)); queuepairint, 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*(n1)/2」这类模式你要默认它需要long long。解决把int全部换成long long只需要在思路里确认哪个变量有平方或者累加的含义不需要追求精确到每个变量统一用long long是最省心也最稳的。如果担心long long也不够题目里一般会给出模数模 10^97 的题所有中间结果都必须先模再加。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 翻车三vectorbool的性能陷阱现象用vectorbool visited做 BFSn 到 10^6 时超时但复杂度算起来应该能过。原因vectorbool是 C 里出了名的特化每个元素只占 1 bit读取时要经过位运算代理对象写入时会整字节重写频繁随机访问时比裸bool数组慢一个数量级。解决BFS、DFS 的访问标记用vectorchar或者直接用 C 数组bool vis[n]。vectorchar虽然每个元素占一个字节但访问是直接内存寻址速度最快。这道坑在 n 到 10^6 的图论题里几乎必踩开了 O2 也救不回来。5.4 翻车四递归深度爆栈现象图论题用 DFS 递归遍历一棵链状的树n 到 10^5 直接崩溃返回Runtime Error或者Segmentation fault。原因默认栈空间在 Linux 上约 8 MBDFS 深度到 10^5 时每层递归的栈帧累积瞬间超过栈上限。解决方案一是在编译选项里加-Wl,--stack268435456来扩大栈空间但这只对你本地有效CSES 的测评机仍然会爆方案二是改成手写栈的迭代 DFS方案三是把 DFS 改成 BFS图论题里大部分 DFS 能做的 BFS 也能做。我通常把图论的递归dfs全部改成迭代 stackint入栈时标记访问而不是出栈时标记避免重复入栈。5.5 翻车五DP 数组维度顺序影响缓存命中现象二维 DP 用dp[i][j]和dp[j][i]的遍历方向写反了小数据全对大数据超时。原因C 的二维数组在内层是按行连续存储的如果你外层枚举列、内层枚举行每次访问都要跨一大段内存跳跃缓存命中率骤降。解决写 DP 时把内层循环的下标放在数组的第二个维度。比如 0/1 背包dp[i][j]的 i 是物品、j 是容量那么循环应该外层 i 内层 j因为dp是vectorvectorint dp(n1, vectorint(m1))j是第二个维度访问连续内存。如果状态定义强制你外层枚举 j那就把数组转置成dp[j][i]效果一样但快得多。5.6 翻车六map 做 DP 导致的无谓慢现象用unordered_mapint, int存储 DP 状态n 到 10^5 时跑得很慢甚至超时。原因CSES 的测评机器对unordered_map的哈希函数处理不够快而且哈希表在扩容时会有全量 rehash频繁插入耗时。解决优先用 vector 数组做 DP只有当状态值域很大或者状态本身是pair才用 map。比如 Longest Increasing Subsequence 用二分 lower_bound时我直接在vectorint 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 状态、核心手法、复杂度。比如题号专题核心手法时间复杂度我的坑1621Sorting排序后相邻判重O(n log n)忘了先排序1634DP完全背包O(nm)内外层顺序反了1667GraphBFS 求最短路O(nm)忘了标记起点表格信息不是为了给别人看是为了让我自己隔一个月扫一眼就能想起这题考的是什么。复杂度那栏尤其重要——CSES 的题基本不会考你一个「理论上能跑」的算法而是精确到操作次数能不能在 1 秒内完成。我算复杂度时统一按 5×10^8 次简单操作作为一个时限 1 秒的安全上限超过就换思路。最后说一个我直到现在都在用的习惯每道题提交前先跑一遍自己构造的边界用例——输入最大值、最小值、重复元素、单元素、完全逆序。这个动作花不了三十秒但它帮我挡下了至少二十次 WA。有一回我在 Graph 题里用邻接表存图构造了一个 n1、m0 的用例立刻发现 BFS 从 1 出发会越界访问空节点当场修掉省了一轮评测。从那以后我每次提交前都强制走一遍这个流程CSES 刷完三百题后我已经不需要评测机告诉我哪里错了。希望帮到你。本文还有配套的精品资源点击获取
