简介：CSES Problem Set 题解代码包面向准备算法竞赛、技术面试或系统训练C++编程能力的学习者，围绕CSES官方题集整理可运行的解题实现，覆盖入门模拟、排序与搜索、图论、动态规划、数学、字符串等常见专题，难度从基础到进阶。压缩包为zip格式，共28个cpp源文件，整体约19KB，体积轻便，适合按专题查阅、本地编译与调试。现有257人学习，说明其在算法练习群体中具有一定参考价值。代码按题集模块组织，读者可对照题目理解状态设计、边界处理与复杂度取舍，并借助现成实现复盘贪心、回溯、位运算等思路，也可用于赛前限时训练后的答案核对与查漏补缺。对需要准备ACM/ICPC、编程竞赛或工程师面试的人群，这份代码包能提供较清晰的C++实现参照，便于逐步搭建自己的算法知识框架。

1. 一份被低估的 C++ 训练清单：CSES Problem Set 不是题解仓库

CSES Problem Set 在算法圈子里属于那种「听说过、没系统刷过」的存在。它把三百来道题按知识模块切成十个区，从入门模拟一直铺到树上启发式合并，每道题都有明确的数据范围和判定标准。这份资源的价值不在题面本身，而在于它提供了一套可以直接编译、可以对拍、可以按模块逐块啃下来的 C++ 实现集合。适合两类人：一类是语法已经过关、想找结构化题库把算法骨架搭起来的；另一类是打过不少场次，但图论、树、区间查询这三块总是断片，需要回头补课。它不承诺让你变强，只承诺每道题的边界条件都写死在那里，跑不过就是跑不过。

2. 题库的十层结构：先认地图，再决定 C++ 怎么写

很多人拿到这类资源的第一反应是打开第一题开始敲，敲到 Dynamic Programming 就卡死。原因不在能力，在于没先看清模块之间的先修关系。CSES Problem Set 的十个分区不是平行排列的，它们有明确的前置依赖：Sorting and Searching 里的双指针和二分答案，是 Range Queries 的前置；Graph Algorithms 里的 DFS 序和子树概念，是 Tree Algorithms 的前置。跳过前置直接冲后面，得到的不是进度，是一堆抄来的、自己都解释不清的代码。

2.1 十个模块的梯度与先修关系

我一般会先把下面这张表贴在显示器边上，每刷完一个模块划掉一行。它的作用是让你在卡住的时候能立刻判断：是这一块本身难，还是前面某块没打牢。

从表里能看出一个规律：越靠后的模块，代码量越小但思维密度越高。Graph Algorithms 的一道题可能要写八十行建图和遍历，Advanced Techniques 的题往往三十行就写完，但那三十行得想半小时。所以刷这套题的节奏应该是「前四块练手感，中间三块练结构，最后三块练取舍」。手感靠重复，结构靠模板，取舍靠对数据范围的敏感度。

还有一个容易被忽略的点：Introductory 里那些看起来幼稚的题，恰恰是后面所有模块的地基。比如循环里用int累加一个上界接近2e9的量，在入门题里就会翻车；这个习惯不改，到了 Range Queries 里做前缀和照样翻。很多人觉得入门题浪费时间，其实是在给自己省后悔药。

2.2 一份可复用的 C++ 骨架

这套题的输入规模普遍不小，Sorting and Searching和Range Queries里常见n = 2e5配q = 2e5的查询量，用默认的cin/cout在某些环境下会明显拖慢。我习惯在每个解法文件里带一份轻量读取和一份树状数组，前者解决 I/O，后者解决 80% 的动态前缀问题。

#include <bits/stdc++.h> using namespace std; // 轻量整数读取：跳过非数字字符，支持负数 static inline int readInt() { int c = getchar(), x = 0, f = 1; while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); } while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); } return x * f; } // 树状数组：单点加、前缀和、区间和，下标从 1 开始 struct Fenwick { int n; vector<long long> t; explicit Fenwick(int n = 0) : n(n), t(n + 1, 0) {} void add(int i, long long v) { for (; i <= n; i += i & -i) t[i] += v; } long long sum(int i) const { long long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } long long range(int l, int r) const { return sum(r) - sum(l - 1); } }; int main() { int n = readInt(), q = readInt(); Fenwick fw(n); for (int i = 1; i <= n; ++i) fw.add(i, readInt()); while (q--) { int op = readInt(), a = readInt(), b = readInt(); if (op == 1) fw.add(a, b - fw.range(a, a)); // 改成把 a 位置设置成 b else printf("%lld\n", fw.range(a, b)); } return 0; }

这段代码里几个决定成败的细节。readInt用getchar而不是cin >>，在百万级整数读入时差距明显；如果确定运行环境是 Linux 且只读非负整数，可以换成getchar_unlocked，但要记得它在部分平台上不可用。Fenwick的下标体系严格从 1 开始，add的循环条件是i <= n而不是i < n，这一处写错会导致最后一个元素永远更新不到，而且小数据测不出来。t用long long而不是int，是因为前缀和很容易超过2^31，这类题目的数据范围通常就在这个位置设卡。

参数上还要注意range(l, r)内部调用了两次sum，如果查询量特别大且常数敏感，可以手写双循环减少函数调用开销，但在2e5量级下通常没必要。真正需要优化的是add里的i & -i，这是树状数组的全部精髓，它取的是i的最低位 1，写反成i & (i - 1)就变成了降幂，行为完全不同。

2.3 用数据范围反推算法，而不是用算法去套题

这套题最值得学的一个习惯是：先看数据范围，再决定写什么。下面这张对照表我几乎每道题都会扫一眼，它能挡掉大部分「思路对了但复杂度超了」的情况。

举个例子，一道题给出n ≤ 2e5且要求「区间内不同值的个数」，如果你第一反应是每次查询扫一遍区间，复杂度是O(nq)，直接出局；正确方向是离线排序加树状数组，把问题转成「每个值只保留最后一次出现」。反过来，如果一道题n ≤ 20，你写了个线段树也能过，但那是浪费，而且容易在细节上翻车。

这套题还有个隐性的训练点：它不会告诉你该用什么算法。题面只给场景和数据范围，选型全靠自己判断。这跟真实工程里的技术选型是同一种思维模式，只不过反馈周期从「上线后出问题」压缩到了「提交后红字」。

3. 把解法在本地跑起来：编译参数、目录组织与第一版对拍

资源拿到手，第一件事不是读代码，是让代码能在你机器上跑起来。这一步看着枯燥，但它决定了后面所有调试的效率。我见过太多人卡在「编译报错找不到头文件」或者「本地过了提交挂」，本质都是环境没对齐。

3.1 目录组织与一条能反复用的编译命令

我习惯按模块建目录，文件名跟题目语义对齐，而不是用题号。题号会变，语义不会。

# 目录结构：一个模块一个文件夹，模板单独放 mkdir -p cses/{intro,sorting,dp,graph,range,tree,math,string,geo,advanced,_tpl} # 统一编译脚本，放在仓库根目录，命名为 build.sh cat > build.sh <<'EOF' #!/usr/bin/env bash # 用法: ./build.sh graph/dijkstra.cpp set -e src="$1" out="${src%.cpp}" g++ -O2 -std=c++17 -Wall -Wextra -Wshadow -o "$out" "$src" echo "built: $out" EOF chmod +x build.sh

关键参数逐个说清楚。-O2是必须的，不带优化的情况下，2e5级别的堆优化最短路可能慢三到五倍，本地测出来的时间完全没有参考价值。-std=c++17是因为代码里用到了结构化绑定和if constexpr之类的特性，用c++11编译会直接报错。-Wall -Wextra打开常见警告，-Wshadow专门抓「内层变量遮蔽外层变量」这种玄学 bug——它救过我至少三次，都是循环变量和全局数组重名导致结果莫名其妙。

不要加-O3和-march=native，这两个会让本地行为和判题环境不一致，本地跑 200ms 提交 TLE 的情况多半就是这么来的。也不要加-g之外的调试符号，除非你确实要上 gdb。

3.2 输入输出：先解决速度，再解决正确性

cin/cout慢是个老话题，但很多人只知道ios::sync_with_stdio(false)，不知道它和printf混用会出问题。

int main() { // 关闭 C 与 C++ 流的同步，加速 cin/cout ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int &x : a) cin >> x; // 注意：此后不能再混用 printf / scanf，否则输出顺序会乱 for (int x : a) cout << x << ' '; cout << '\n'; return 0; }

sync_with_stdio(false)的作用是解除iostream与 C 标准库的绑定，代价是两者不能混用。如果你习惯在调试时插一句printf，那这个开关就是陷阱：输出顺序会错乱，而且在小数据下可能看不出来。cin.tie(nullptr)解除的是cin与cout的绑定，避免每次读入前强制刷新输出缓冲，在多测场景下影响明显。

如果题目输入量到了1e6级别，或者涉及大量浮点数，上面这套还是不够，这时候才需要手写读取。我的判断标准很简单：本地用chrono量一次，I/O 占总时间超过 20% 就换手写读取，否则不值得为它牺牲可读性。

3.3 对数器：写一个不骗自己的随机数据生成器

「本地过了，提交挂」的绝大多数原因是本地测试数据太弱。对数器的做法是：写一份暴力解法（哪怕是指数级），再写一份随机数据生成器，让两者对跑几百轮，任何一轮结果不一致就停下来看数据。这条路子慢，但它是唯一能让你在提交前放心的办法。

// gen.cpp：生成随机数据，参数用命令行传，方便脚本循环 #include <bits/stdc++.h> using namespace std; int main(int argc, char** argv) { int seed = argc > 1 ? atoi(argv[1]) : 1; int n = argc > 2 ? atoi(argv[2]) : 10; mt19937 rng(seed); // 固定种子，出问题能复现 uniform_int_distribution<int> val(1, 1000); printf("%d\n", n); for (int i = 0; i < n; ++i) printf("%d%c", val(rng), " \n"[i + 1 == n]); return 0; }

生成器有两个要点。第一，种子必须能从外部传入，否则出了不一致的数据你没法重放，只能靠肉眼猜。第二，规模要分档：先跑n ≤ 10的小数据，把逻辑错误暴露出来，再跑n ≤ 1000的中等数据，抓边界和溢出。一上来就生成大数据，程序崩了你也看不出是哪一步错的。

配对上暴力解法之后，跑一轮完整的对拍大概是这样：

#!/usr/bin/env bash # 用法: ./stress.sh sorting/subarray_sums set -e src="$1" g++ -O2 -std=c++17 -o /tmp/fast "$src.cpp" g++ -O2 -std=c++17 -o /tmp/slow "${src}_brute.cpp" g++ -O2 -std=c++17 -o /tmp/gen gen.cpp for i in $(seq 1 300); do n=$((RANDOM % 9 + 2)) /tmp/gen "$i" "$n" > /tmp/in.txt /tmp/fast < /tmp/in.txt > /tmp/out_fast.txt /tmp/slow < /tmp/in.txt > /tmp/out_slow.txt if ! diff -q /tmp/out_fast.txt /tmp/out_slow.txt > /dev/null; then echo "mismatch at seed=$i n=$n" cat /tmp/in.txt exit 1 fi done echo "all passed"

set -e让脚本在任何一步失败时立刻退出，避免错误被吞掉。seq 1 300的轮数不是随便定的，小数据下 300 轮基本能覆盖所有边界组合；如果题目涉及多组测试，轮数要再翻倍，因为多测不清空的问题只在特定组合下暴露。

4. 按模块攻坚：图论、树、区间查询三条主线的最小可复现路径

十个模块里，最容易劝退的是这三块：图论代码长、树结构绕、区间查询模板多。它们的共同点是「模板会背但不会用」。下面三条路径是我反复用过的，从最小可运行单元开始，再往上叠。

4.1 图论主线：从 BFS 到堆优化 Dijkstra 的复用结构

图论题的代码量主要集中在建图上，一旦建图结构固定下来，换算法只是替换中间那一段。我习惯用vector<vector<pair<int,int>>>存带权图，用vector<vector<int>>存无权图，两者都不需要手动管理内存。

#include <bits/stdc++.h> using namespace std; const long long INF = 0x3f3f3f3f3f3f3f3fLL; // 约 4.6e18，加法不会立刻溢出 int main() { int n, m; scanf("%d %d", &n, &m); vector<vector<pair<int,int>>> adj(n + 1); for (int i = 0; i < m; ++i) { int a, b, w; scanf("%d %d %d", &a, &b, &w); adj[a].push_back({b, w}); // 有向图只加一条；无向图补 adj[b].push_back({a, w}) } vector<long long> dist(n + 1, INF); // 小根堆：priority_queue 默认大根堆，必须传 greater 并显式指定底层容器 priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq; dist[1] = 0; pq.push({0, 1}); while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (d != dist[u]) continue; // 懒惰删除：跳过已过期的旧条目 for (auto [v, w] : adj[u]) { if (dist[v] > d + w) { dist[v] = d + w; pq.push({dist[v], v}); } } } for (int i = 1; i <= n; ++i) printf("%lld ", dist[i] == INF ? -1 : dist[i]); return 0; }

三个参数值得单独说。INF用0x3f3f3f3f3f3f3f3fLL而不是LLONG_MAX，因为后者加上任何正数都会溢出成负数，一旦某条边被松弛就会得到错误结果，而且这种错误在部分数据下不会触发，属于典型的埋伏型 bug。if (d != dist[u]) continue;是惰性删除，省掉了 STL 堆不支持修改键值的问题；去掉这一行程序仍然正确，但会多处理很多过期条目，稠密图上性能差一截。greater<>后面的空尖括号是 C++14 起的写法，用 C++11 得写完整的greater<pair<long long,int>>。

建图方向也是一坑。题目说「道路」默认是无向，说「航线」「单向通行」是有向，这层语义必须从题面读出来。加错方向的典型表现是：样例能过，因为样例往往只有一条路径；一提交就在大数据上挂掉一半。

4.2 树算法主线：把递归 DFS 换成显式栈

Tree Algorithms 里的树最深可以到2e5层，写成递归 DFS 基本必爆栈。这不是玄学，是每个栈帧几百字节乘以二十万，超出默认栈上限。解决办法有两条：调大栈限制，或者改成迭代。调限制在本地有效，提交环境不认；所以我一般直接写迭代版。

// 用 BFS 序建立父指针，再逆序累加，等价于后序 DFS，但不会爆栈 int n; vector<vector<int>> adj; vector<int> parent_, order_, sz; void build(int root) { parent_.assign(n + 1, 0); order_.clear(); order_.reserve(n); parent_[root] = -1; order_.push_back(root); // 用下标遍历代替队列，省掉 queue 的额外开销 for (size_t i = 0; i < order_.size(); ++i) { int u = order_[i]; for (int v : adj[u]) { if (v == parent_[u]) continue; // 无向图里唯一需要防的就是回头边 parent_[v] = u; order_.push_back(v); } } sz.assign(n + 1, 1); for (int i = (int)order_.size() - 1; i > 0; --i) { int u = order_[i]; sz[parent_[u]] += sz[u]; // 逆序遍历保证子节点先算完 } }

这段代码的核心思路是把「递归的前序展开」和「后序归并」拆成两步：先用一个不断增长的order_数组做前序遍历，再用它的逆序做自底向上的累加。order_用vector而不是queue，是因为后面要按下标逆序访问，队列没有这个能力。if (v == parent_[u]) continue;是无向图建树的唯一判重条件，多写一个visited数组也能过，但多一份状态就多一个出错点。

sz[parent_[u]] += sz[u]这一行的前提是order_里父节点一定排在子节点前面，这个性质由前序扩展保证。如果哪天你把这段改成 DFS 递归再取逆序，性质就不成立了，结果会错得很隐蔽。

4.3 区间查询主线：前缀和、树状数组、线段树的取舍

这三个东西功能重叠，选错的代价是代码量翻三倍。我的判断顺序是：静态且不带修改，用前缀和；带单点修改、只需要区间和，用树状数组；需要区间最值、区间赋值、或者维护的信息不满足可减性，才上线段树。

线段树的模板网上很多，但大多数人抄完之后不会改。真正需要理解的是下推标记的时机：

struct SegTree { int n; vector<long long> t, lazy; SegTree(int n) : n(n), t(4 * n, 0), lazy(4 * n, 0) {} void apply(int p, long long v, int len) { t[p] += v * len; lazy[p] += v; } void push(int p, int len) { if (!lazy[p]) return; // 无标记直接返回，减少无谓递归 apply(p << 1, lazy[p], len - len / 2); apply(p << 1 | 1, lazy[p], len / 2); lazy[p] = 0; } void update(int p, int l, int r, int ql, int qr, long long v) { if (qr < l || r < ql) return; if (ql <= l && r <= qr) { apply(p, v, r - l + 1); return; } push(p, r - l + 1); int m = l + (r - l) / 2; update(p << 1, l, m, ql, qr, v); update(p << 1 | 1, m + 1, r, ql, qr, v); t[p] = t[p << 1] + t[p << 1 | 1]; } long long query(int p, int l, int r, int ql, int qr) { if (qr < l || r < ql) return 0; if (ql <= l && r <= qr) return t[p]; push(p, r - l + 1); int m = l + (r - l) / 2; return query(p << 1, l, m, ql, qr) + query(p << 1 | 1, m + 1, r, ql, qr); } };

push里的len - len / 2和len / 2是左右子树长度，不能都写成len / 2，否则奇数长度会少算一个，表现为「区间加之后查询结果偏小」。t和lazy开4 * n是因为线段树在最坏情况下节点数接近4n，开2n在部分区间划分下会越界。apply里t[p] += v * len的前提是节点维护的信息是「和」，如果维护的是最值，这一行要换成t[p] += v，因为加一个常数对最值的影响不是乘长度。这个差异是抄模板最容易翻车的地方。

5. 避坑与排查：五条血泪现场

下面这五条都是我自己踩过的，每一条都符合「样例能过、提交挂掉」的特征。它们不是理论问题，是实打实会让你在一道题上耗掉两小时的东西。

5.1 五条高频翻车记录

现象：一道求和的题，小数据全对，n = 2e5的数据输出负数。原因：累加变量用了int，2e5个1e9之和远超2^31，溢出成负值。这类题的数据范围经常故意卡在int上限附近。解决：所有参与累加、乘法、前缀和的变量一律用long long，包括中间变量；n * (n + 1) / 2这种式子里，n是int的话乘法会先溢出再赋值，必须写成1LL * n * (n + 1) / 2。

现象：树上的题，本地跑小数据正常，大数据直接段错误。原因：递归 DFS 在深度2e5的链状树上爆栈。默认栈大小通常在 8MB 左右，每层递归几百字节，二十万层必然超。解决：改成 4.2 节的迭代写法，或者用 BFS 序建父指针再逆序累加。不要指望调栈限制，提交环境不认这个。

现象：多组测试的题，第一组对，第二组开始结果全错。原因：全局数组或vector没在每组测试前清空，上一组的数据污染了这一组。解决：把每组数据的状态封装进函数局部变量；如果为了性能必须用全局数组，在每组开头显式fill一遍，并且只清「用到的前 n 个位置」而不是整个数组，避免清零本身成为瓶颈。

现象：unordered_map写起来很顺手，但某道题一直 TLE，换了map反而过了。原因：unordered_map的哈希函数对某些整数序列会退化成链，单次操作从O(1)变成O(n)。构造这类数据不需要恶意，题目自带的测试点就够触发。解决：要么换成map接受O(log n)，要么给unordered_map传一个自定义哈希打乱输入，要么干脆用排序加二分代替。

现象：用multiset存了一堆值，调用erase(x)想删掉一个，结果同值的元素全没了。原因：multiset::erase(value)删除的是所有等于该值的元素，只有erase(iterator)才删单个。解决：先用find(x)拿到迭代器再erase(it)，并且记得判it != end()，否则删空迭代器是未定义行为，本地可能不崩，提交环境可能直接挂。

5.2 提交前的自检清单

写完之后别急着交，按顺序过一遍下面几项，能挡掉八成以上的低级错误。

这张表我贴在编辑器侧边，写完一道题就从头到尾扫一遍。刚开始会觉得繁琐，两周之后就变成肌肉记忆了。

6. 进阶：用对拍脚本和计时器把「能过」变成「敢交」

到了这个阶段，题目本身已经不是障碍，障碍是「我不确定自己写对了」。这时候需要的不是更多题量，而是一套能给出确定性反馈的验证流程。我在 3.3 节给了对拍的基本框架，真正要用起来还得补两块：循环化和计时代。

先看计时。很多人对复杂度的判断停留在纸面，实际跑起来才发现常数大得离谱。加一段计时不需要改逻辑，只要在main的首尾各插一行。

#include <chrono> int main() { auto t0 = std::chrono::steady_clock::now(); // ... 原有逻辑 ... auto t1 = std::chrono::steady_clock::now(); // 输出到 stderr，避免污染标准输出的答案 fprintf(stderr, "elapsed: %.1f ms\n", std::chrono::duration<double, std::milli>(t1 - t0).count()); return 0; }

用steady_clock而不是system_clock，因为后者会被系统时间调整影响，测出来的数不可信。结果写到stderr，这样对拍脚本重定向stdout时不会把计时信息混进答案里。判断标准也很明确：如果某道题理论复杂度是O(n log n)、n = 2e5，本地跑到 300ms 以上，那大概率是常数太大或者算法实际退化成了O(n sqrt n)，得回头看。

对拍的循环化是在 3.3 节基础上再加一层：把规模从小到大分档跑。

#!/usr/bin/env bash # 分档对拍：先小后大，小规模多轮，大规模少轮 for round in 1 2 3; do case $round in 1) maxn=10; times=300 ;; # 小数据抓逻辑错误 2) maxn=200; times=100 ;; # 中数据抓边界和溢出 3) maxn=2000; times=20 ;; # 大数据抓性能退化 esac for i in $(seq 1 $times); do /tmp/gen "$i" "$((RANDOM % maxn + 1))" > /tmp/in.txt /tmp/fast < /tmp/in.txt > /tmp/a.txt 2>/dev/null /tmp/slow < /tmp/in.txt > /tmp/b.txt 2>/dev/null diff -q /tmp/a.txt /tmp/b.txt > /dev/null || { echo "fail: round=$round seed=$i"; exit 1; } done echo "round $round passed ($times cases, maxn=$maxn)" done

分档的意义在于定位。小数据挂了，说明是逻辑写错，比如初始化、循环边界；中数据挂了，多半是溢出或者下标越界；只有大数据挂，才轮到性能和递归深度的问题。三档混在一起跑，出错了你不知道往哪个方向查，白白浪费时间。

还有一个容易被忽略的技巧：把slow版本故意写成朴素解法，而不是照着fast的思路写一遍。两份代码思路相同的话，同一种误解会在两边同时出现，对拍就失去了意义。暴力解法要按定义硬写，慢没关系，正确性优先。

这套流程跑顺之后，我改掉了一个毛病：不再靠「感觉对了」就提交。每道题写完，先跑小规模 300 轮，再跑中规模 100 轮，最后看一眼计时。这套动作花不了五分钟，但省下来的罚时和心态成本远不止五分钟。从那以后我每次动树状数组或者线段树的下标之前，都会先把自检清单和分档对拍强制走一遍，不管题目看着多简单。希望帮到你。

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