简介：面向准备编程竞赛与算法面试的学习者，CSES-Problem-Set 以 C++ 源码形式整理了 CSES 在线题库的常见题型，覆盖入门模拟、排序与搜索、图论、字符串、数学等专题，适合用来打牢数据结构与算法基础，也可作为专题刷题后的代码对照材料。压缩包共 28 个文件，均为 cpp 源码，整体约 19KB，体量轻便，目录按入门、排序与搜索、图论、字符串、数学等模块划分，便于逐题检索与研读。资源已有 257 人学习，在算法练习群体中具有一定参考价值。读者可从中获得基础算法、动态规划、贪心、树与图搜索、并查集与线段树、数论、回溯剪枝及位运算等典型问题的 C++ 实现，结合代码理解状态转移、搜索剪枝、边界处理与输入输出细节，进而提升独立解题和面试编码能力。

1. 先别急着从第一题开始做

这份算法题单约 300 道题、每题 1 分、按专题排成十块，看上去像一份循序渐进的教程，实际上它更像十个互不重叠的考点区——你从第一题顺着做，前 40 题会顺得让人飘，做到图论突然被输入规模和递归深度按住。用 C++ 刷这份题单的人，翻车点几乎从来不是"不会算法"，而是"知道该用 BFS，但读入用了 cin 又没关同步，2×10^5 的数据直接 T 掉"。所以真正决定你能不能把它吃干净的只有三件事：清楚每个专题对应用人单位问什么、清楚自己的实现会在哪个量级崩、清楚哪几类题必须背成肌肉记忆。下面的内容按"考什么—高频考点—怎么答"的顺序推，适合已经能写循环、数组、结构体，打算拿这份题单打底的人。

2. 考点分布：约 300 题怎么摊到十个专题上

这份题单每题 1 分，没有难度系数，也没有官方推荐顺序，十个专题之间几乎不存在知识依赖。这个设计带来一个后果：按顺序刷完 300 题和按考点刷完 100 题，面试效果可能完全反过来。先把十块内容跟面试问法的映射关系摆出来，你才知道哪几块值得二刷、哪几块做一遍留个印象就够。

2.1 十个专题与面试追问的对应关系

表格里最右侧那一列才是关键。面试官问"有负权边怎么办"，考的不是你会不会写最短路，而是你知不知道 Dijkstra 的贪心前提是边权非负；问"带单点修改还适用吗"，考的是你能不能区分静态前缀和与动态树状数组。这类追问在原题里不会出现，但它是从原题直接长出来的，所以做每道题时都值得停十秒钟想一遍：如果条件改一个字，我的解法还成立吗。

几何和进阶技巧这两块在常规面试里出现概率很低，但在笔试、机试、竞赛保研的机考里恰恰是分水岭。如果你只冲面试，这两块可以放到最后；如果目标是机试拿分，进阶技巧里的状压和折半枚举必须过一遍，因为它们的题面辨识度极高，看到"n ≤ 20"就该条件反射。

2.2 一分一题的账：推进顺序决定你两个月能走多远

把 300 分分成三档看：60 分对应"能应付大多数笔试的选择和填空"，150 分对应"现场手写中等难度题不慌"，250 分以上才是"面试官临时加一道偏题也能接住"。绝大多数人卡在 60 到 120 之间，原因不是题做得少，而是顺序错了。

推荐的推进顺序是：入门题 → 排序与查找 → 动态规划 → 图算法 → 树算法 → 区间查询，前六块走完大约 140 题，剩下的数学、字符串、几何、进阶按目标挑着做。这个顺序的理由很实在：排序与查找里的前缀和、双指针、二分答案是后面所有专题的地基，动态规划教会你定义状态，图算法把"状态 + 转移"具象成搜索，树算法是图算法的特例但多了递归深度这个坑，区间查询则是在前缀和的基础上做动态化。反过来先啃数学或者几何，很容易做成背公式，做完一遍什么都没留下。

每天三到五题是可持续的节奏，超过八题基本就是抄答案。每道题做完留一个标记：独立做出来的打勾，看了提示的打三角，直接看题解的打叉。一周后只重做三角和叉的题，三角的题如果第二次还是卡，就降级成叉。这套流程听起来笨，但它能保证你不是在"刷题数"，而是在"补漏洞"。

2.3 先自测：三道题定位你该从哪一档开始

别凭感觉判断自己水平，用下面三道题现场推一遍，三十秒内说不出思路的就是你的起点。

第一道：给一个长度不超过 2×10^5 的整数数组（元素可正可负）和一个目标值 k，求有多少个子数组的元素和恰好等于 k。这类题通常这么答：不能用滑动窗口，因为元素有负数，窗口右移时和不一定增大。正确做法是维护前缀和，把"以 i 结尾、和为 k 的子数组个数"转化成"前面有多少个位置的前缀和等于 pre[i] - k"，用一个哈希表边扫边计数。面试官最想听的是你先否掉滑动窗口的那句话，那说明你在判断适用条件，而不是背模板。这道题答不出，回去补排序与查找。

第二道：n 个城市、m 条单向道路，每条路代价相同，求 1 号城市到 n 号城市最少经过几条路。这类题通常这么答：边权相同的最短路就是 BFS，一层一层扩，第一次访问到目标点时距离就是答案。追问通常会落在"如果边权不同呢"，答案是换成优先队列的 Dijkstra，并且要点明它要求边权非负。这道题答不出，回去补图算法。

第三道：给一棵 n 个点的树，q 次询问，每次问以 u 为根的子树上共有多少个点。这类题通常这么答：先一次 DFS 求出每个点的子树大小，询问就是 O(1) 查表，总复杂度 O(n + q)；如果询问变成"子树里权值大于 x 的点有多少个"，就升级成欧拉序 + 树状数组。这道题答不出，说明树和区间查询两块都没通，先补树。

3. 高频考点：C++ 写这份题单绕不开的四个实现细节

算法思路对了但过不了，八成栽在语言层面。这部分内容在任何一本算法书里都排在很后面，但在实际做题时的复现率极高，几乎每个专题都会撞上一次。四条按踩坑频率从高到低排。

3.1 输入规模决定写法：什么时候该上快读

先记住量级：读入数据在 10^5 以内，cin 关掉同步就够；到 10^6，要开始考虑 scanf；超过 10^6 且时间限制在 1 秒，才需要手写快读。很多人第一题就上快读，其实是浪费时间，真正该做的是先看一眼题面最后一行给的 n 上界。

// 手写快读：适用于 n 在 1e6 以上、cin 关同步仍超时的情况 static inline int readInt() { int x = 0, f = 1; char c = getchar(); 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; }

这段函数只处理整数，遇到非数字字符就停，返回时带上符号。参数上没有玄机，关键在于它跳过了 cin 的格式解析和虚拟函数开销，纯 getchar 的吞吐在本地能跑到每秒千万级。写的时候注意两点：一是负数要先读符号再读数字，别把 '-' 当成数字算进去；二是如果输入里有 long long，x 的类型必须同步改成 long long，否则读进来就溢出了。竞赛里常见的做法是写两个版本，readInt 和 readLong，别图省事共用一个。

还有一个容易被忽略的写法：ios::sync_with_stdio(false); cin.tie(nullptr);这两句必须写在 main 的第一行，写在读入之后没有任何作用。血泪经验是有人把它写在循环里，然后疑惑为什么还是超时。

3.2 溢出与取模：最高频的丢分点不在算法在类型

只要题目出现"答案对 10^9+7 取模"，就必须假设中间结果会炸 int。int 上限约 2.1×10^9，两个模数相乘就是 10^18 量级，直接溢出成负数，而负数取模在 C++ 里结果仍为负，最后输出一个莫名其妙的负值。

const long long MOD = 1000000007LL; // 乘法：先转 long long 再取模，a、b 都小于 MOD 时乘积不会溢出 long long mul(long long a, long long b) { return (a % MOD) * (b % MOD) % MOD; } // 减法：C++ 里负数取模仍为负，必须先加 MOD 再取模 long long sub(long long a, long long b) { return (a - b % MOD + MOD) % MOD; }

mul 里两个小于 10^9 的数相乘最大约 10^18，long long 上限约 9.2×10^18，安全。sub 里加一个 MOD 是为了把负值拉回正区间，只加一次就够，因为 a 和 b 都已经被限制在 [0, MOD) 内。真正容易翻车的是组合数递推和前缀积这两类题，中间变量忘记开 long long，前六个测试点全过，第七个点开始错，这种错最难查。

面试现场如果被问"这里会不会溢出"，标准答法是先说数据范围，再说变量类型，最后说如果不放心可以改用取模前的比较或者用无符号类型兜底。面试官要听的是你有这个意识，不是你现场推导一遍。

3.3 容器选型：同样 O(n log n) 差在哪

这张表里最值得说的是 unordered_map。它的平均 O(1) 有前提，一旦哈希函数被针对性构造，所有元素会挤进同一个桶，退化成 O(n)，在某些评测机上表现为"本地 0.1 秒，提交 T 掉"。稳妥的做法是读入前reserve(n * 2)预留桶数，或者干脆用排序 + 二分替代。另一处高频错误是 priority_queue 默认是大顶堆，想要小顶堆必须写priority_queue<int, vector<int>, greater<int>>，三个模板参数一个都不能少。

3.4 递归深度与栈：为什么树题要改成手写栈

这是树算法专题里最典型的题：给一棵 2×10^5 个点的树，求每个点的子树大小。思路一句话——后序遍历，每个点的 size 等于自身加上所有孩子的 size。写成递归只有六行，但节点数到 2×10^5、树退化成一条链时，递归深度就是 2×10^5，默认栈空间会直接崩，表现为运行错误而不是答案错误，很多人在本地测小数据永远发现不了。

// 迭代版后序遍历求子树大小：避免深链爆栈 vector<vector<int>> g; // 邻接表 vector<int> sz, order; vector<int> parent; void solve(int root, int n) { sz.assign(n + 1, 1); parent.assign(n + 1, 0); order.clear(); order.reserve(n); vector<int> st{root}; // 手写栈，先做一次前序拿到遍历序 parent[root] = -1; while (!st.empty()) { int u = st.back(); st.pop_back(); order.push_back(u); for (int v : g[u]) { if (v == parent[u]) continue; parent[v] = u; st.push_back(v); } } // 逆着前序就是后序：孩子的 size 一定先算完 for (int i = n - 1; i >= 0; --i) { int u = order[i]; if (parent[u] > 0) sz[parent[u]] += sz[u]; } }

核心技巧是用"前序 + 逆序"模拟后序：前序遍历保证父节点一定排在子节点前面，那么把整个序列倒过来，子节点就一定排在父节点前面，累加时不会漏。参数上，sz 初始化为 1 表示每个点自己算一个；parent[root] 设成 -1 是为了让根节点不往上传；order 预留 n 个空间避免反复扩容。这段代码的复杂度是 O(n)，比递归版多了常数，但换来了不会崩。

面试里如果手写递归被追问"树很深怎么办"，直接答"改成显式栈或者 BFS 分层处理"，比现场改代码更得分。

4. 真题演练：五类必考题的答题思路与代码

这一章挑五道覆盖不同专题的典型题，每道先给思路再给代码，代码后面说清楚关键行在干什么。这些题不是原题，是从原题里抽出来的模型，模型会了，同类题基本就是换皮。

4.1 排序与查找：前缀和加哈希表，把 O(n²) 压成 O(n)

题面：给定长度不超过 2×10^5 的整数数组和目标值 k，统计和等于 k 的子数组个数，元素可正可负。

思路三步：第一步，否定滑动窗口，理由是元素含负数时窗口不单调；第二步，把"子数组和"转成"两个前缀和之差"；第三步，扫到位置 i 时，只需要知道前面出现过多少次前缀和等于 pre[i] - k，用哈希表边扫边记。

#include <bits/stdc++.h> using namespace std; int main() { int n; long long k; scanf("%d %lld", &n, &k); unordered_map<long long, long long> cnt; cnt.reserve(n * 2 + 1); // 预留桶数，避免退化 cnt[0] = 1; // 空前缀，处理从下标 0 开始的子数组 long long pre = 0, ans = 0; for (int i = 0; i < n; ++i) { long long x; scanf("%lld", &x); pre += x; auto it = cnt.find(pre - k); // 找有多少个历史前缀满足差为 k if (it != cnt.end()) ans += it->second; ++cnt[pre]; // 先查后插，防止 k = 0 时把自己算进去 } printf("%lld\n", ans); return 0; }

cnt[0] = 1是这段代码的灵魂，没有它就会漏掉所有从头开始的区间。先查后插的顺序同样关键：如果先插入再查询，当 k 等于 0 时，当前前缀会跟自己做一次匹配，凭空多出一个子数组。ans 用 long long 是因为子数组个数最多约 n²/2，2×10^5 的规模下会超过 int。面试口述时把这两点讲出来，比背代码有效得多。

4.2 动态规划：先答"状态是什么"，再谈转移

题面：给定 m 种面额的硬币（每种无限个）和一个目标金额，求凑出该金额所需的最少硬币数，凑不出返回 -1。

这类题面试官最想听的第一句话不是转移方程，而是"状态定义为凑出金额 v 所需的最少硬币数"。定义清楚了，转移自然出来：dp[v] = min(dp[v], dp[v - c] + 1)。

const int INF = 0x3f3f3f3f; int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INF); dp[0] = 0; // 凑 0 元需要 0 枚，这是唯一的初始合法状态 for (int c : coins) // 外层枚举物品 for (int v = c; v <= amount; ++v) // 内层正序，允许同一硬币重复使用 dp[v] = min(dp[v], dp[v - c] + 1); return dp[amount] == INF ? -1 : dp[amount]; }

两层循环的顺序决定了这是完全背包还是 0-1 背包：物品在外、容量在内且正序，表示每件物品可以用无限次；如果内层改成逆序，就退化成每件只能用一次。INF 取 0x3f3f3f3f 而不是 INT_MAX，是为了dp[v - c] + 1时不会溢出成负数。这两点几乎每次面试都会被追问一次，答错任何一个都会让面试官怀疑你是在背代码。

4.3 图算法：BFS 的三段式写法

题面：给一个 n×m 的网格，'#' 是墙，'.' 是通路，求从起点到终点的最少步数，走不通返回 -1。

BFS 的写法固定成三段：初始化队列和距离数组、while 循环逐层扩展、越界和访问判断前置。

int dx[4] = {-1, 1, 0, 0}; int dy[4] = {0, 0, -1, 1}; int bfs(vector<string>& grid, int sx, int sy, int ex, int ey) { int n = grid.size(), m = grid[0].size(); vector<vector<int>> dist(n, vector<int>(m, -1)); // -1 兼作未访问标记 queue<pair<int,int>> q; dist[sx][sy] = 0; q.push({sx, sy}); while (!q.empty()) { auto [x, y] = q.front(); q.pop(); if (x == ex && y == ey) return dist[x][y]; // 出队时判终，保证是最短路 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}); } } return -1; }

用 dist 数组同时承担"距离"和"是否访问"两个职责，省掉一个 visited 数组，这是 BFS 的标准写法。终点的判断放在出队时而不是入队时，是因为入队时的距离还不一定是最终值，出队时才能保证。dx、dy 两个数组把四个方向展开成循环，比写四段 if 更不容易漏方向，面试时也更整洁。

4.4 区间查询：树状数组的适用边界

题面：给一个长度 n 的数组，支持两种操作——把某个位置的值加上 v，查询区间 [l, r] 的和。操作次数不超过 2×10^5。

只要出现"单点修改 + 区间查询"，就该想到树状数组；如果变成"区间修改 + 区间查询"，就得换线段树加懒标记。这个判断链条要在读完题的三秒内走完。

struct BIT { int n; vector<long long> t; BIT(int n) : n(n), t(n + 1, 0) {} void add(int i, long long v) { // 单点加：沿 i += lowbit(i) 往上爬 for (; i <= n; i += i & -i) t[i] += v; } long long sum(int i) { // 前缀和：沿 i -= lowbit(i) 往下跳 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取出的是 i 的最低位 1，add 靠它向上更新所有覆盖该位置的节点，sum 靠它向下拆解前缀。树状数组的下标必须从 1 开始，传 0 会死循环，这是最常见的翻车点。t 用 long long 是因为前缀和很容易超过 int。整个结构体不到二十行，值得背下来，面试现场手写完全来得及。

4.5 字符串：哈希把子串比较变成整数比较

题面：给主串和模式串，判断模式串是否在主串中出现过，要求 O(n + m)。

这类题有两种答法，KMP 和字符串哈希。哈希的代码短、思路直白，面试里更好讲：把每个前缀映射成一个整数，子串哈希用两个前缀哈希相减再乘上长度幂的逆元得到。

const long long B = 131, MOD = 1000000007LL; vector<long long> buildHash(const string& s, vector<long long>& pw) { int n = s.size(); vector<long long> h(n + 1, 0); pw.assign(n + 1, 1); for (int i = 1; i <= n; ++i) { h[i] = (h[i - 1] * B + (s[i - 1] - 'a' + 1)) % MOD; // 前缀哈希 pw[i] = pw[i - 1] * B % MOD; // 预处理幂次 } return h; } long long getHash(const vector<long long>& h, const vector<long long>& pw, int l, int r) { // 取 s[l..r] 的哈希，下标从 1 开始 return ((h[r] - h[l - 1] * pw[r - l + 1]) % MOD + MOD) % MOD; }

B 取 131 是因为它是大于字符集大小的质数，冲突概率低；pw 数组预处理幂次，避免每次查询都快速幂；最后一个+ MOD) % MOD处理负数。要强调的是，单哈希存在被构造碰撞的可能，面试里主动补一句"工程上会用双哈希或者加随机基数"，是很加分的收尾。

5. 失分点：五个最容易反复踩的坑

下面五条是从大量错题里归纳出来的高频失分点，每一条都按"错在哪、为什么错、怎么答对"三段说。看的时候对照自己做过的题，能对上号的立刻回去重写一遍。

5.1 数组开小：n 的上界永远写在题面最后一行

错在哪：题面写 n ≤ 2×10^5，代码里开了int a[100005]，本地小数据全过，提交后从第三组开始运行错误。

为什么错：习惯性按 10^5 开数组，而这份题单里大量题目的上界是 2×10^5，图算法里边的数量还要再乘二。更隐蔽的是多组数据题的累加，上一组留下的数据没清空，下一组读到脏值。

怎么答对：读题时把 n、m、边数三个上界抄在草稿纸第一行，开数组时统一乘二再加十。全局数组比局部数组安全，因为它默认零初始化且不在栈上；如果必须用局部数组，别开在递归函数里。

5.2 二分写错边界：三种模板混着用

错在哪：找第一个大于等于 x 的位置，写成了while (l < r)配r = mid - 1，结果死循环或者答案差一。

为什么错：二分有三套常见写法——闭区间、左闭右开、以及求上下界的特化版——混用任意两套的更新规则就会死循环。核心分歧在 mid 的取整方向：区间收缩时要保证每轮范围真的变小。

怎么答对：只背一套闭区间模板，while (l <= r)，判中时l = mid + 1或r = mid - 1，循环结束后 l 就是第一个不满足条件的位置。写完立刻用两个元素的数组手推一次，这个习惯能挡掉九成的差一错误。

5.3 多组数据不清空：全局变量是隐形炸弹

错在哪：图论题里多组测试数据，邻接表只 push 不 clear，第二组数据跑出来答案翻倍。

为什么错：vector<vector<int>> g(n + 1)写在 main 里会重新构造，写在全局或者写在循环外就只构造一次；计数变量、标记数组同理。这类错误在小数据下答案只是偏大一点，很容易被误判成算法错。

怎么答对：每组数据开头统一做一次清理，或者把整个数据结构包进一个函数里按值构造。养成"读入组数之后第一件事是清零"的固定动作，比事后调试省时间。

5.4 计数题不取模：答案还没输出就已经错了

错在哪：题目要求答案对 10^9+7 取模，代码在最后一步才取模，中间过程早已溢出成负数。

为什么错：组合数、方案数、路径数这类题的中间结果增长极快，n 到 10^5 时随便一个阶乘都远超 long long。取模必须贯穿全程，不能攒到最后。

怎么答对：把所有涉及答案的变量统一用 long long，每次加、减、乘之后立刻取模，减法用(a - b + MOD) % MOD。写之前先问自己一句：这个数最大能到多少，中间量会不会超过 9.2×10^18。

5.5 输出格式：多一个空格就是零分

错在哪：输出一行 n 个数，最后一个数后面多带了一个空格，或者该换行的地方没换行。

为什么错：很多评测机对输出做逐字节比对，多一个空格、少一个换行都判错。这类失分最冤，算法完全正确，分照样没有。

怎么答对：输出多个数时用"第一个数单独输出，后面的数前面加空格"的写法，或者输出完判断i == n - 1 ? '\n' : ' '。提交前扫一眼题面的输出说明，尤其是"行末不要多余空格""两组数据之间空一行"这种细节。

6. 答题技巧：把题单刷成面试话术的三步法

刷题和答题是两件事。题会做，不代表面试时能讲明白。我在被追问到卡壳几次之后，固定了一个三步法，每道题都强制走一遍，慢一点，但复述率明显上来了。

第一步，定量级。读完题先不看别的，找 n 的上界和时间限制，反推允许的复杂度：n ≤ 20 想状压或折半枚举，n ≤ 5000 想 O(n²) 动态规划，n ≤ 2×10^5 只能 O(n log n)，n ≤ 10^6 得压到 O(n)。这一步在面试里要说出声，让面试官知道你是在按数据规模选方案，而不是套模板。

第二步，选模型。把题面里的关键词映射到模型上：连续子段和想到前缀和，最少步数想到 BFS，方案数想到动态规划，连通性想到并查集，区间修改想到线段树。这个映射表我在纸上抄过一遍，后来做题速度明显变快，因为大部分题在读完题的前三十秒就已经知道往哪个方向走了。

第三步，先讲边界再写代码。面试官最欣赏的开场是"我先确认几个边界：n 会不会是 0，元素会不会全负，答案会不会超过 int"。这三句话说完，即使代码写错一行，面试官也会认为你的工程意识在线。

押题优先级可以按这张表来排：

最后说一个习惯。从那以后我每次做完题，都强制用一句话写下"这道题的核心转化是什么"，比如"子数组和等于 k"的核心转化是"两个前缀和相减"。写完再合上题解。坚持一个月，你会发现面试时听到题面的第一反应不再是"我做过类似的"，而是"这题的核心转化是哪一个"。这个差别，就是刷了三百题和刷透一百题的区别。希望帮到你。

这份题单里每个专题的模板代码、易错点和上面那三步法的检查清单，我整理成了一份可以打印出来贴在桌前的备考笔记，按模块分好，做完一个专题划掉一块。需要的话按文末方式取一份，配合题单边做边对照，比单纯刷题数扎实得多。

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