简介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 十个模块的梯度与先修关系我一般会先把下面这张表贴在显示器边上每刷完一个模块划掉一行。它的作用是让你在卡住的时候能立刻判断是这一块本身难还是前面某块没打牢。模块核心考点建议先修常见卡点Introductory模拟、循环、基础数学C 语法与输入输出边界、整数溢出Sorting and Searching双指针、二分答案、前缀和、贪心排序、二分查找二分边界写错Dynamic Programming线性 DP、背包、区间 DP、状压递推思想状态定义含糊Graph AlgorithmsBFS/DFS、最短路、最小生成树、拓扑、强连通邻接表建图稠密图选错算法Range Queries前缀和、树状数组、线段树、稀疏表递归、树形结构下标体系混用Tree Algorithms子树统计、LCA、树上差分、直径DFS 与图论基础递归爆栈Mathematics快速幂、逆元、组合数、博弈 SG数论基础取模位置写错String Algorithms哈希、Z 函数、KMP、Trie字符串基础哈希冲突Geometry叉积、凸包、扫描线向量运算浮点与整型混用Advanced Techniques折半搜索、离线处理、树套树、bitset前九个模块复杂度估算失误从表里能看出一个规律越靠后的模块代码量越小但思维密度越高。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; vectorlong 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 ≤ 20O(2^n · n)状压 DP、枚举子集n ≤ 40O(2^(n/2))折半搜索n ≤ 500O(n^3)区间 DP、Floydn ≤ 5000O(n^2)朴素 DP、二维前缀和n ≤ 2e5O(n log n)排序、树状数组、线段树、堆优化最短路n ≤ 1e6O(n) 或 O(n α(n))线性筛、并查集、单调栈举个例子一道题给出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 -stdc17 -Wall -Wextra -Wshadow -o $out $src echo built: $out EOF chmod x build.sh关键参数逐个说清楚。-O2是必须的不带优化的情况下2e5级别的堆优化最短路可能慢三到五倍本地测出来的时间完全没有参考价值。-stdc17是因为代码里用到了结构化绑定和if constexpr之类的特性用c11编译会直接报错。-Wall -Wextra打开常见警告-Wshadow专门抓「内层变量遮蔽外层变量」这种玄学 bug——它救过我至少三次都是循环变量和全局数组重名导致结果莫名其妙。不要加-O3和-marchnative这两个会让本地行为和判题环境不一致本地跑 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; vectorint 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_distributionint 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 -stdc17 -o /tmp/fast $src.cpp g -O2 -stdc17 -o /tmp/slow ${src}_brute.cpp g -O2 -stdc17 -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 passedset -e让脚本在任何一步失败时立刻退出避免错误被吞掉。seq 1 300的轮数不是随便定的小数据下 300 轮基本能覆盖所有边界组合如果题目涉及多组测试轮数要再翻倍因为多测不清空的问题只在特定组合下暴露。4. 按模块攻坚图论、树、区间查询三条主线的最小可复现路径十个模块里最容易劝退的是这三块图论代码长、树结构绕、区间查询模板多。它们的共同点是「模板会背但不会用」。下面三条路径是我反复用过的从最小可运行单元开始再往上叠。4.1 图论主线从 BFS 到堆优化 Dijkstra 的复用结构图论题的代码量主要集中在建图上一旦建图结构固定下来换算法只是替换中间那一段。我习惯用vectorvectorpairint,int存带权图用vectorvectorint存无权图两者都不需要手动管理内存。#include bits/stdc.h using namespace std; const long long INF 0x3f3f3f3f3f3f3f3fLL; // 约 4.6e18加法不会立刻溢出 int main() { int n, m; scanf(%d %d, n, m); vectorvectorpairint,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}) } vectorlong long dist(n 1, INF); // 小根堆priority_queue 默认大根堆必须传 greater 并显式指定底层容器 priority_queuepairlong long,int, vectorpairlong 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后面的空尖括号是 C14 起的写法用 C11 得写完整的greaterpairlong long,int。建图方向也是一坑。题目说「道路」默认是无向说「航线」「单向通行」是有向这层语义必须从题面读出来。加错方向的典型表现是样例能过因为样例往往只有一条路径一提交就在大数据上挂掉一半。4.2 树算法主线把递归 DFS 换成显式栈Tree Algorithms 里的树最深可以到2e5层写成递归 DFS 基本必爆栈。这不是玄学是每个栈帧几百字节乘以二十万超出默认栈上限。解决办法有两条调大栈限制或者改成迭代。调限制在本地有效提交环境不认所以我一般直接写迭代版。// 用 BFS 序建立父指针再逆序累加等价于后序 DFS但不会爆栈 int n; vectorvectorint adj; vectorint 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; vectorlong 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的数据输出负数。原因累加变量用了int2e5个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 提交前的自检清单写完之后别急着交按顺序过一遍下面几项能挡掉八成以上的低级错误。检查项具体动作溢出所有累加、乘法、前缀和变量是否为long long下标树状数组、线段树、并查集是否从 1 开始数组是否开到n 1边界n 1、单元素区间、空区间、全相同元素是否测过多测每组测试前状态是否清空输出是否为每组一行递归深度是否可能到1e5以上是否需要改迭代复杂度用 2.3 节的对照表反推一遍确认不会超时这张表我贴在编辑器侧边写完一道题就从头到尾扫一遍。刚开始会觉得繁琐两周之后就变成肌肉记忆了。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::durationdouble, 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) maxn10; times300 ;; # 小数据抓逻辑错误 2) maxn200; times100 ;; # 中数据抓边界和溢出 3) maxn2000; times20 ;; # 大数据抓性能退化 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 轮最后看一眼计时。这套动作花不了五分钟但省下来的罚时和心态成本远不止五分钟。从那以后我每次动树状数组或者线段树的下标之前都会先把自检清单和分档对拍强制走一遍不管题目看着多简单。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/31 5:26:26 · 阅读 1.2k CSES Problem Set：C++算法训练与对拍自检
简介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 十个模块的梯度与先修关系我一般会先把下面这张表贴在显示器边上每刷完一个模块划掉一行。它的作用是让你在卡住的时候能立刻判断是这一块本身难还是前面某块没打牢。模块核心考点建议先修常见卡点Introductory模拟、循环、基础数学C 语法与输入输出边界、整数溢出Sorting and Searching双指针、二分答案、前缀和、贪心排序、二分查找二分边界写错Dynamic Programming线性 DP、背包、区间 DP、状压递推思想状态定义含糊Graph AlgorithmsBFS/DFS、最短路、最小生成树、拓扑、强连通邻接表建图稠密图选错算法Range Queries前缀和、树状数组、线段树、稀疏表递归、树形结构下标体系混用Tree Algorithms子树统计、LCA、树上差分、直径DFS 与图论基础递归爆栈Mathematics快速幂、逆元、组合数、博弈 SG数论基础取模位置写错String Algorithms哈希、Z 函数、KMP、Trie字符串基础哈希冲突Geometry叉积、凸包、扫描线向量运算浮点与整型混用Advanced Techniques折半搜索、离线处理、树套树、bitset前九个模块复杂度估算失误从表里能看出一个规律越靠后的模块代码量越小但思维密度越高。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; vectorlong 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 ≤ 20O(2^n · n)状压 DP、枚举子集n ≤ 40O(2^(n/2))折半搜索n ≤ 500O(n^3)区间 DP、Floydn ≤ 5000O(n^2)朴素 DP、二维前缀和n ≤ 2e5O(n log n)排序、树状数组、线段树、堆优化最短路n ≤ 1e6O(n) 或 O(n α(n))线性筛、并查集、单调栈举个例子一道题给出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 -stdc17 -Wall -Wextra -Wshadow -o $out $src echo built: $out EOF chmod x build.sh关键参数逐个说清楚。-O2是必须的不带优化的情况下2e5级别的堆优化最短路可能慢三到五倍本地测出来的时间完全没有参考价值。-stdc17是因为代码里用到了结构化绑定和if constexpr之类的特性用c11编译会直接报错。-Wall -Wextra打开常见警告-Wshadow专门抓「内层变量遮蔽外层变量」这种玄学 bug——它救过我至少三次都是循环变量和全局数组重名导致结果莫名其妙。不要加-O3和-marchnative这两个会让本地行为和判题环境不一致本地跑 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; vectorint 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_distributionint 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 -stdc17 -o /tmp/fast $src.cpp g -O2 -stdc17 -o /tmp/slow ${src}_brute.cpp g -O2 -stdc17 -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 passedset -e让脚本在任何一步失败时立刻退出避免错误被吞掉。seq 1 300的轮数不是随便定的小数据下 300 轮基本能覆盖所有边界组合如果题目涉及多组测试轮数要再翻倍因为多测不清空的问题只在特定组合下暴露。4. 按模块攻坚图论、树、区间查询三条主线的最小可复现路径十个模块里最容易劝退的是这三块图论代码长、树结构绕、区间查询模板多。它们的共同点是「模板会背但不会用」。下面三条路径是我反复用过的从最小可运行单元开始再往上叠。4.1 图论主线从 BFS 到堆优化 Dijkstra 的复用结构图论题的代码量主要集中在建图上一旦建图结构固定下来换算法只是替换中间那一段。我习惯用vectorvectorpairint,int存带权图用vectorvectorint存无权图两者都不需要手动管理内存。#include bits/stdc.h using namespace std; const long long INF 0x3f3f3f3f3f3f3f3fLL; // 约 4.6e18加法不会立刻溢出 int main() { int n, m; scanf(%d %d, n, m); vectorvectorpairint,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}) } vectorlong long dist(n 1, INF); // 小根堆priority_queue 默认大根堆必须传 greater 并显式指定底层容器 priority_queuepairlong long,int, vectorpairlong 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后面的空尖括号是 C14 起的写法用 C11 得写完整的greaterpairlong long,int。建图方向也是一坑。题目说「道路」默认是无向说「航线」「单向通行」是有向这层语义必须从题面读出来。加错方向的典型表现是样例能过因为样例往往只有一条路径一提交就在大数据上挂掉一半。4.2 树算法主线把递归 DFS 换成显式栈Tree Algorithms 里的树最深可以到2e5层写成递归 DFS 基本必爆栈。这不是玄学是每个栈帧几百字节乘以二十万超出默认栈上限。解决办法有两条调大栈限制或者改成迭代。调限制在本地有效提交环境不认所以我一般直接写迭代版。// 用 BFS 序建立父指针再逆序累加等价于后序 DFS但不会爆栈 int n; vectorvectorint adj; vectorint 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; vectorlong 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的数据输出负数。原因累加变量用了int2e5个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 提交前的自检清单写完之后别急着交按顺序过一遍下面几项能挡掉八成以上的低级错误。检查项具体动作溢出所有累加、乘法、前缀和变量是否为long long下标树状数组、线段树、并查集是否从 1 开始数组是否开到n 1边界n 1、单元素区间、空区间、全相同元素是否测过多测每组测试前状态是否清空输出是否为每组一行递归深度是否可能到1e5以上是否需要改迭代复杂度用 2.3 节的对照表反推一遍确认不会超时这张表我贴在编辑器侧边写完一道题就从头到尾扫一遍。刚开始会觉得繁琐两周之后就变成肌肉记忆了。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::durationdouble, 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) maxn10; times300 ;; # 小数据抓逻辑错误 2) maxn200; times100 ;; # 中数据抓边界和溢出 3) maxn2000; times20 ;; # 大数据抓性能退化 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 轮最后看一眼计时。这套动作花不了五分钟但省下来的罚时和心态成本远不止五分钟。从那以后我每次动树状数组或者线段树的下标之前都会先把自检清单和分档对拍强制走一遍不管题目看着多简单。希望帮到你。本文还有配套的精品资源点击获取