简介：CSES-Problem-Set 是一套面向算法初学者、竞赛选手与面试备赛者的 C++ 练习代码集，围绕 CSES 在线题库中的经典题型组织，适合用于夯实数据结构与算法基础、对照题目开展实现训练，也可作为专题刷题的参考材料。压缩包共 28 个文件，全部为 cpp 源文件，整体约 19KB，内容覆盖入门模拟、排序查找、字符串处理、图论与树、数学、动态规划等模块，目录按题型归类，便于按主题检索和逐题复盘。已有 257 人学习，说明它对于刷题入门和查漏补缺具有一定参考价值。读者可从中查看具体题目的 C++ 实现思路，结合数组、二分、深度优先搜索、广度优先搜索、贪心、数论与位运算等知识点理解代码结构、边界处理与复杂度取舍，并依据分类目录安排练习顺序，逐步提升独立解题、代码调试和面试编码能力。

1. 看起来最没技术含量的一道题，最容易出错

CSES Problem Set 里最被低估的一道题是区间求和：思路三秒就能说完，但把它写成能过全部测试点的 C++ 代码，第一次提交就 Wrong Answer 的人不在少数。这套题库真正考的不是你知不知道前缀和，而是你会不会在 1 秒时限、长整型边界、1-index 与 0-index 混用这些细节上出错。三百道上下的题按入门、排序与查找、动态规划、图论、区间查询、树、数学、字符串等分区排开，从简单到很难，难度跨度很大。它适合已经能写基本语法、想在机试和笔试里稳定拿分的人，不适合还在纠结for循环怎么写的人。

2. 考点分布：十个分区各自对应哪类笔试题

很多人第一次打开 CSES 的题目列表，反应是“怎么这么多”。三百道题摆在一起确实吓人，但它的分区本身已经把考点切得很干净，你要做的是先看清每个分区在考什么、在你的目标考试里占多少分，再决定投入。这一章把分区和笔试题型对上的目的很简单：让你在有限时间里，把复习时间花在最容易提高分数的地方，而不是从第一题开始老老实实往下做。

2.1 十个分区与笔试题型的对应关系

下面这张表是经验值，不是官方权重，但用来做取舍足够准。分区名是题库自带的，题量占比和对应题型是我按常见机试结构给的估计。

看这张表要抓住一个判断：排序与查找、动态规划、图论这三块加起来接近六成，它们属于“不会就肯定丢分，会了就能稳定拿分”的区域；区间查询和树是性价比最高的提分区，代码模板固定、思维方式统一；几何和进阶技巧属于“有时间再说”，除非你明确知道目标考试会出。

2.2 时间有限时的取舍：先学哪三块，后啃哪两块

按照题目顺序从入门题开始做，大概率会卡在入门区后面几道构造题上，一天做不了几道，还会产生“我不适合搞算法”的错觉。更合理的路径是三条线并行推进。

第一条线是排序与查找。这个分区的题面通常很短，判定逻辑清楚，适合用来建立“读完题能立刻动手”的手感。做完十来道，你对二分答案的判定函数会形成肌肉记忆。

第二条线是区间查询。前缀和、树状数组、线段树这三件套的代码结构高度相似，写完一道静态区间求和，再写动态区间求和，改动量只有几十行。这是所有分区里投入产出比最高的一块，建议尽早拿下。

第三条线是图论的基础部分。连通块、网格 BFS、单源最短路、拓扑排序，这四类题的模板几乎是固定的，背下来就能套。CSES 的图论分区里，真正难的是那些需要组合两三种技巧的题，基础题反而很友好。

后两块的“难区”是动态规划后半段和树上问题。DP 的题量最大，状态定义千变万化，硬啃容易受挫，建议在完成前三条线之后，用“一天两道、做完必须写状态转移方程”的节奏推进。树上问题如果递归写不顺手，就先用迭代方式把子树统计做熟，再回头补 LCA 之类的结构。

2.3 一道入门题的完整判题流程：以 Missing Number 为例

拿最经典的 Missing Number 走一遍完整流程：给出 n，再给出 1 到 n 中缺了一个数的 n−1 个数，求缺的那个。题面一句话，但它刚好把“读题、看数据范围、选类型、想边界、算复杂度”这五步都覆盖了。

#include <bits/stdc++.h> using namespace std; int main() { long long n; scanf("%lld", &n); // 先读 n，别急着开数组 long long sum = n * (n + 1) / 2; // 先乘后除，避免 (n/2)*(n+1) 的整除误差 for (long long i = 0, x; i < n - 1; ++i) { scanf("%lld", &x); sum -= x; // 边读边减，O(1) 额外空间 } printf("%lld\n", sum); return 0; }

这段代码里三个点值得单独说。第一是long long：当 n 到 2×10⁵ 量级时，1 到 n 的和已经到 2×10¹⁰，超出 32 位有符号整数的范围，用int存和必然溢出，而且溢出后结果看起来“很像对的”，非常难查。第二是n * (n + 1) / 2的书写顺序，先乘后除永远比先除后乘安全。第三是“边读边减”，它省掉了一个长度为 n 的数组，也顺便避开了下标从 0 还是从 1 开始的纠结。

复杂度是 O(n) 时间、O(1) 空间，在 1 秒时限下毫无压力。这道题在笔试题里最常见的变形是“给 n 个数，其中只有一个出现两次，其余出现一次，求它”，解法换成异或；还有“给 n−2 个数，缺两个”，解法是分组异或或者解方程。变形的外壳在变，内核都是“用整体信息减掉已知信息”。

3. 高频考点：前缀和、二分答案、双指针的固定打法

如果只看三个模块，排序与查找和区间查询这两个分区值得你反复刷。原因不是它们简单，而是它们的解法结构高度收敛：一旦你掌握了判定函数怎么设计、下标怎么对齐，剩下的就是体力活。这一章把三类最高频的题拆开讲，每类都给出能直接背下来的代码骨架。

3.1 前缀和与差分：区间查询分区的四道基础题共用一套模板

静态区间求和是这类题的原型：给一个长度 n 的数组和 q 次询问，每次问区间 [a,b] 的元素和。朴素做法每次累加是 O(nq)，前缀和把它压到 O(1)。

#include <bits/stdc++.h> using namespace std; const int N = 200005; long long pre[N]; // 前缀和数组必须 long long int main() { int n, q; scanf("%d %d", &n, &q); for (int i = 1; i <= n; ++i) { long long x; scanf("%lld", &x); pre[i] = pre[i - 1] + x; // 1-index，pre[0] = 0 当哨兵 } while (q--) { int a, b; scanf("%d %d", &a, &b); printf("%lld\n", pre[b] - pre[a - 1]); // 闭区间 [a,b] 减的是 a-1 } return 0; }

三个细节决定了这道题能不能一次过。下标用 1-index，pre[0]作为哨兵，这样pre[a-1]在 a=1 时也不会越界；查询是闭区间，减的是a-1而不是a，写成pre[b]-pre[a]在样例上可能碰巧对，但边界全错；求和用long long，因为 n 和元素值乘起来很容易超 32 位。

前缀和管“静态”，一旦题目加上“单点修改 + 区间查询”，就得换树状数组。它的代码短到可以背：

struct BIT { int n; vector<long long> t; BIT(int n) : n(n), t(n + 1, 0) {} void add(int i, long long v) { // 单点加，向上跳 lowbit for (; i <= n; i += i & -i) t[i] += v; } long long sum(int i) { // 前缀和，向下跳 lowbit long long s = 0; for (; i > 0; i -= i & -i) s += t[i]; return s; } long long range(int l, int r) { return sum(r) - sum(l - 1); } };

i & -i取的是最低位的 1，它决定了每层管多长一段。新手最常犯的错是把下标写成 0 开始，0 & -0等于 0，循环直接死掉，所以树状数组的下标一律从 1 开始。

差分的思路正好相反：如果题目是“区间加、最后统一查询”，就对差分数组做单点修改，最后做一遍前缀和还原。CSES 区间查询分区里有些题看似复杂，本质上就是判断该用前缀和、差分还是树状数组，选对结构，代码量差不了几十行。

3.2 二分答案：判定函数怎么设计，边界怎么不写错

二分答案的题有个共同特征：题目问“最小的最大值”或者“最早能完成的时间”，而验证一个候选答案是否可行，比直接求解容易得多。典型代表是 Array Division：把数组切成 k 段连续子数组，让“最大段和”尽可能小。

// 判断：每段和不超过 limit 时，能否用不超过 k 段装下所有元素 bool check(long long limit, const vector<int>& a, int k) { long long cur = 0; int cnt = 1; // 至少一段 for (int x : a) { if (x > limit) return false; // 单个元素就超，直接不可行 if (cur + x > limit) { ++cnt; cur = x; } else cur += x; } return cnt <= k; } long long solve(const vector<int>& a, int k) { long long lo = *max_element(a.begin(), a.end()); // 下界：最大元素 long long hi = accumulate(a.begin(), a.end(), 0LL); // 上界：只切一段 while (lo < hi) { long long mid = lo + (hi - lo) / 2; if (check(mid, a, k)) hi = mid; // 可行就收紧上界 else lo = mid + 1; } return lo; }

判定函数的设计要点是“贪心 + 单调”：从左往右能塞就塞，塞不下就开新段，这样得到的段数是在该 limit 下的最小值。如果这个最小值都不超过 k，说明 limit 可行。单调性保证了“可行之后一直可行”，二分才成立。

边界是这类题最容易出错的地方。下界不能取 0，因为段和至少要装得下最大元素，取max_element最稳；上界取总和，对应“整段不切”的情况。循环写while (lo < hi)配hi = mid和lo = mid + 1，返回lo，这套组合不会死循环。反过来写成lo = mid又没有正确收缩，就会出现两个元素时 mid 永远等于 lo 的死循环。

同类型的题还有 Factory Machines（n 台机器，每台生产一件需要给定时间，求生产 t 件的最短时间），判定函数换成“统计总产量是否达到 t”，二分的上下界换成 0 和min_time * t。题面换，骨架不变。

3.3 双指针与排序：两数之和、区间调度中的通用套路

第三类高频题是“排序之后用两个指针从两端往中间夹”。Sum of Two Values 是代表：给一个数组和目标值 x，找两个不同位置使它们的和等于 x，输出下标。

vector<int> idx(n); iota(idx.begin(), idx.end(), 0); // 保存原始下标 sort(idx.begin(), idx.end(), [&](int i, int j) { return a[i] < a[j]; }); int l = 0, r = n - 1; while (l < r) { long long s = (long long)a[idx[l]] + a[idx[r]]; // 相加前先转 long long if (s == x) { /* 输出 idx[l]+1, idx[r]+1，注意 1-index */ break; } else if (s < x) ++l; // 太小，左指针右移 else --r; // 太大，右指针左移 }

这套写法的正确性依赖排序后的单调性：左指针右移一定让和变大，右指针左移一定让和变小，所以不会漏解。两个坑要注意：一是题目要输出原始下标，排序时必须带着下标一起排，不能只排值；二是两个数相加之前先转成 64 位，元素接近 10⁹ 时两个数一加就溢出。

同一套思路还能解 Apartments（给申请人需求面积和公寓面积，求最多匹配数）和 Movie Festival（区间调度，按右端点排序后贪心选不重叠的区间）。这两个题一个用双指针做匹配，一个用排序后单指针扫，判定逻辑不同，但“先排序、再线性扫一遍”的思维是一致的。

4. 攻坚区：动态规划与图论的状态设计与模板选择

DP 和图论是拉分的地方，也是很多人复习到一半就放弃的地方。放弃的原因通常不是不会写代码，而是不知道该把“状态”定义成什么。这一章不铺开讲所有模型，只讲三类在 CSES 里反复出现、并且在机试里最容易变形考的形式。

4.1 计数型 DP：状态定义和循环顺序决定答案对不对

Dice Combinations 是最直观的入门题：掷骰子，每步可以走 1 到 6 步，问走到 n 有多少种走法。状态定义dp[i]表示走到 i 的方案数，转移是dp[i] = dp[i-1] + ... + dp[i-6]，初始条件dp[0] = 1（站在起点算一种方案）。

这个dp[0] = 1是最容易被写成 0 的地方。写成 0 之后所有答案都变成 0，因为后面每个状态都从它推出来。记住一句话：计数问题里的“空方案”算一种，最优化问题里的“空方案”通常算零或无穷。

真正拉开差距的是“组合还是排列”。Coin Combinations 系列给一组面额，问凑出 x 的方案数，两个版本的差别只在外层循环：

const int MOD = 1e9 + 7; // 组合数：1+2 和 2+1 算同一种 —— 物品在外层 vector<long long> dp(x + 1, 0); dp[0] = 1; for (int c : coins) for (int s = c; s <= x; ++s) dp[s] = (dp[s] + dp[s - c]) % MOD; // 排列数：1+2 和 2+1 算两种 —— 容量在外层 vector<long long> dp2(x + 1, 0); dp2[0] = 1; for (int s = 1; s <= x; ++s) for (int c : coins) if (s >= c) dp2[s] = (dp2[s] + dp2[s - c]) % MOD;

为什么物品在外层就是组合？因为外层固定了“当前只考虑前几种面额”，每种面额只会被加入一次，顺序被强制成面额表里的顺序，所以不会重复计数。容量在外层时，每一步都可以任选一种面额，顺序自由，得到的是排列数。这个区别在机试里考过太多次，看到“方案数”三个字，先问自己一句“顺序算不算不同”。

4.2 图论的四件事：连通块、最短路、判环、并查集

图论分区看上去题多，实际上落在四个模板上。

连通块和网格搜索用 DFS 或 BFS 都行，Counting Rooms 是典型：给一张由.和#组成的网格，数出有多少个连通的.区域。写法上要注意边界判断和访问标记合并，别在出队时才发现越界。

单源最短路用优先队列优化的 Dijkstra，模板固定，坑集中在“过期条目”的处理上：

vector<long long> dist(n + 1, LLONG_MAX); 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] : g[u]) { if (dist[u] + w < dist[v]) { // 松弛成功才入队 dist[v] = dist[u] + w; pq.push({dist[v], v}); } } }

if (d != dist[u]) continue;这一行不能省。没有它，同一个点会被反复处理，复杂度退化，在稠密图上直接超时。另外greater<>让堆变成小根堆，写成默认的priority_queue就是大根堆，取出来的永远是最远的点，结果全错。

判环用拓扑排序：统计入度，入度为 0 的进队，出队时把邻居入度减一，最后如果出队数量小于节点总数，说明有环。CSES 里那道课表题就是这个模型，输出任意一个合法顺序，无解时输出特定标记。

并查集用来处理“动态加边、问连通性”，模板两行核心：路径压缩加按大小合并。写的时候注意初始化parent[i] = i，以及合并前先判是否已经在同一集合。

4.3 树上问题：DFS 序把子树变成一段连续区间

树上题的思维转换点在于：一棵子树在 DFS 序里是一段连续的区间。一旦接受这件事，子树统计、子树修改、子树查询全都变成了区间问题，前面学的树状数组可以直接搬过来。

以 Subordinates 为例，给一棵以 1 为根的树，求每个节点有多少个下属。最直接的写法是递归求子树大小再减一，但 CSES 的节点数能到 2×10⁵，递归深度在链状数据上同样能到 2×10⁵，栈空间不一定够。稳妥的写法是显式栈：

vector<int> order; order.reserve(n); vector<int> parent(n + 1, 0); stack<int> st; st.push(1); while (!st.empty()) { int u = st.top(); st.pop(); order.push_back(u); for (int v : g[u]) if (v != parent[u]) { parent[v] = u; st.push(v); } } vector<int> sz(n + 1, 1); for (int i = (int)order.size() - 1; i >= 0; --i) { // 逆序累加，等价于后序 int u = order[i]; if (parent[u]) sz[parent[u]] += sz[u]; } // 节点 u 的下属数量 = sz[u] - 1

这段代码的关键在逆序遍历：DFS 序的逆序保证了“子节点一定排在父节点后面被处理”，所以累加子树大小时父节点拿到的是已经算完的子节点值。这个技巧在树上 DP 里通用，学会了之后，所有“先算子节点再算父节点”的题都可以用迭代写，彻底绕开栈溢出的问题。

5. 易错点：五个把 AC 变成 WA 的坏习惯

这一章的五条，全都是我在别人的提交记录和自己提交记录里反复见到的。它们的共同点不是“知识点没学会”，而是“学会了但写错了”，这类失分最不值。

5.1 错在数据类型：int存和，溢出之后连调试都找不到

错在哪：求最大子段和时，用int存当前和与答案，样例过，提交 WA。

为什么错：元素值本身就是 10⁹ 量级，加几次就超过 2.1×10⁹，溢出后变成负数，最大值判断直接失效。更致命的是这种错误在小数据上完全看不出来，本地测样例永远是对的。

怎么答对：凡是“求和”“乘积”“最大子段和”“路径长度”，默认开long long，不要犹豫。判断依据很简单：把数据范围的上界乘一下，超过 2×10⁹ 就必须换类型。写 C++ 时还有个习惯可以养成——累加变量和答案变量统一用long long，只在明确安全的地方用int。

5.2 错在边界：二分死循环、空区间、单元素数组

错在哪：二分写成while (lo <= hi)配lo = mid，两个元素时卡死；或者区间查询忘了处理a > b的情况。

为什么错：mid = (lo + hi) / 2向下取整，当区间长度为 2 时 mid 恒等于 lo，如果判定为真还执行lo = mid，区间不收缩，循环永远不会结束。空区间的问题则更隐蔽，某些题的询问可能给出逆序端点，直接套前缀和会算出负数。

怎么答对：二分统一记一套骨架：while (lo < hi)+mid = lo + (hi - lo) / 2+ 可行则hi = mid、不可行则lo = mid + 1，返回lo。这套写法覆盖“最小化可行解”的所有场景，不会死循环。区间类题目在函数入口加一句交换保证a <= b，代价是一次比较，收益是再也不出这类错。

5.3 错在递归深度：树上 DFS 在链状数据上直接运行错误

错在哪：树上统计用递归写 DFS，本地小数据跑得好好的，提交后在某些测试点报运行错误。

为什么错：链状树的深度等于节点数，2×10⁵ 层递归需要的栈空间远超默认值，程序直接崩。报错信息通常只写“运行时错误”，看不出是栈的问题，很多人会以为是数组越界，白找半小时。

怎么答对：节点数超过 10⁵ 的树题，一律用显式栈或 BFS 序代替递归，再配合逆序累加。如果确实想保留递归的写法，至少把递归函数体压到最小，别在栈帧里开大数组。这条属于经验，踩过一次就再也不会忘。

5.4 错在全局数组没清空：多组数据一来就错

错在哪：把题解代码直接套到多组测试数据的笔试环境里，第一组过，第二组开始答案偏大。

为什么错：CSES 的绝大多数题是单组输入，习惯了一次性全局数组之后，换到多组数据的题目里忘了清空，上一组的数据残留下来被重复统计。这类错误在本地单组测试里永远复现不了。

怎么答对：写多组数据的题时，把“读入组数”和“清空状态”绑成一个固定动作，读完T立刻清空所有会被累加的数组。更省事的办法是用vector在每组数据内部重新构造，用作用域代替手动清空。另外注意计数器、答案变量、邻接表这几类最容易漏。

5.5 错在取模时机：减法没加 MOD，乘法先溢出再取模

错在哪：计数 DP 里写dp[i] = (dp[i] - dp[j]) % MOD;，或者写dp[i] = dp[j] * dp[k] % MOD;但两个因子都是int。

为什么错：C++ 的取模对负数返回负值，减法结果为负时答案变成负数，输出直接错。乘法的问题在溢出，两个 10⁹ 量级的数相乘超过int范围，先溢出再取模得到的是垃圾值。

怎么答对：减法统一写(a - b + MOD) % MOD，加一个 MOD 把负数拉回正区间。乘法先把至少一个因子转成long long，再取模。这两个写法建议直接背成肌肉记忆，考试时没时间推导。

6. 答题技巧：四步复盘法，把刷过的题变成考场上的分

刷题和得分之间隔着一层东西，叫复盘。同一道题做三遍不复盘，第三遍还是会卡在同一个地方；做一遍认真复盘，下次遇到变形能直接认出来。我自己用的是四步，每道有价值的题都走一遍，平均花十分钟。

第一步最容易敷衍。写“考二分”没有价值，写“考二分答案，判定函数是贪心统计段数，上下界取最大元素和总和”才有价值，因为下次遇到同类题，你调用的就是这个完整模板，而不是从零开始想。

第二步是关键。很多人的错题本记的是“这题不会”，这种记录等于没记。要记到行号级别：是int该换long long，还是下标该减 1，还是循环条件写反了。错因越具体，第二次犯同样错误的概率越低。我自己有一段时间连续三道区间题错在同一个a-1上，把这条写进笔记之后，再没犯过。

第三步是拉开差距的地方。CSES 的题面很干净，正因为干净，才容易让人做完就翻篇。养成“想想出题人会怎么改”的习惯：把静态改成动态，把单组改成多组，把求和改成求最大值，把无权图改成带权图。这四个方向能覆盖大部分变形，想多了之后，考场上看到陌生题面也能迅速归类。

第四步是验收。看懂题解和自己写出来之间有一道鸿沟，隔一天重写是最便宜的检验方式。写不出来不是坏事，说明复盘的前三步没做到位，回头补。

最后说一个习惯。我每次提交之前都会强制走一遍三个检查：所有可能溢出的变量是不是 64 位、数组下标从几开始、递归和循环的终止条件在边界上对不对。这三项检查花不到一分钟，但能挡掉我八成以上的 WA。CSES 这套题库的价值就在这里——它用三百道题的密度，把这几个检查项反复撞进你的条件反射里，撞到你在考场上不用想就会去看。按分区推进、按上面四步复盘、把易错点当清单逐条排掉，这套流程走完一遍，机试那部分基本就稳了。题库我按分区整理好了，配上这份复盘表用效果最好。希望帮到你。

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