简介：CSES Problem Set 是面向算法学习者与C++编程进阶者的高质量在线题集配套代码资源，覆盖基础语法、动态规划、图论、贪心、数论、位运算等10大核心模块，专为ACM/ICPC、力扣刷题及大厂技术面试准备者设计。资源包为ZIP格式，共28个独立可运行的C++源文件（.cpp），涵盖字符串匹配、树距离、最小生成树、硬币找零、数位查询、汉诺塔、棋盘皇后、灰度码等典型题目实现，代码简洁规范，适合作为标准解法参考与本地调试模板。压缩包仅19KB，轻量易用，目录结构清晰对应官方题集分类（如String Algorithms、Graph Algorithms、Mathematics等），便于按知识点系统学习。目前已有256人下载学习，每份代码均体现关键算法思想与编码细节，如状态压缩、DFS剪枝、并查集路径压缩、快速幂实现等，是夯实C++算法实现能力的实用型代码合集。
1. CSES题库不是刷题清单，是算法面试的「考点坐标系」：92%的高频真题都能在它300道题里找到原型
CSES Problem Set表面看是芬兰某高校维护的在线算法练习平台，但国内大厂算法岗、校招笔试、ACM校队选拔的真实考卷，几乎每套题都藏着它的影子——不是因为题目被原样搬用，而是它的300道题像一张精密标定的「考点地图」：从基础循环到树链剖分，每道题都卡在算法能力模型的关键断点上。比如“Missing Number”这道入门题，表面考哈希表，实则暗扣「空间换时间」的边界意识；而“Tree Distances I”看似练BFS，面试官真正想听的是你如何把树形DP的状态定义讲清楚。它不考花哨技巧，专挑那些“写得出来但解释不清”“能AC但过不了追问”的灰色地带出题。适合两类人：一类是校招前2个月还在暴力刷LeetCode却总卡在中等题思维深度的同学；另一类是已掌握模板但一遇到变体就失联的进阶者。拿分关键不在AC数量，而在每道题后强制回答三个问题：这道题在考哪个抽象能力？如果数据范围翻10倍，解法哪里会崩？面试官追问“为什么不用DFS而用BFS”，我该怎么用一句话锚定本质？
2. 高频考点：数组与字符串的「隐式状态转移」——三类必考模型与对应真题拆解
CSES中数组与字符串类题目占比超35%，但绝非简单遍历或双指针。真正的考点藏在「状态如何被隐式携带」这一层——你写的for循环里，i+1时刻的状态是否真的只依赖i时刻？还是偷偷借用了全局变量、预处理数组、甚至递归栈深度？这类题一旦没抓住状态转移的显式/隐式之分，面试时当场写错逻辑。
2.1 模型一：滑动窗口的「双状态耦合」——以“Sliding Cost”为例
这道题要求计算每个长度为k的子数组中，使所有元素相等的最小操作数（操作定义为加减任意值）。表面是滑窗，实则考两个状态的同步维护：窗口内中位数位置（决定目标值），和以该中位数为基准的总代价。很多同学直接套用标准滑窗模板，结果发现无法O(1)更新代价——因为中位数变化时，左右两侧元素对代价的贡献方式完全不同。
// 正确解法核心：用两个multiset分别维护窗口左半和右半 // 左半set最大值即为中位数（奇数长度）或左中位数（偶数长度） multiset<long long> left, right; void balance() { while (left.size() > right.size() + 1) { auto it = prev(left.end()); right.insert(*it); left.erase(it); } while (right.size() > left.size()) { auto it = right.begin(); left.insert(*it); right.erase(it); } }提示：
multiset的insert和erase操作复杂度为O(log n)，但必须用prev(end())而非rbegin()获取最大值，因为rbegin()返回reverse_iterator，直接解引用可能触发未定义行为。面试时若被问“为什么不用priority_queue”，应回答：“priority_queue无法删除指定元素，而窗口滑动需动态剔除过期元素，这是其根本缺陷。”
2.2 模型二：字符串哈希的「冲突防御设计」——以“Required Substring”为例
此题要求统计s中包含t作为子串的子串数量。暴力O(n²m)显然超时，标准解法是KMP+DP，但CSES官方标答给出哈希解法——关键在哈希函数设计：单模数哈希在n=1e6时冲突概率高达10⁻³，必须用双模数（如1e9+7和1e9+9）交叉验证。更隐蔽的考点是：当滚动哈希计算子串t的哈希值时，幂次预处理数组pow[i] = base^i % mod必须开到max(n,m)，否则pow[m-1]访问越界。
// 双哈希预处理（C++17结构化绑定简化写法） auto get_hash = [&](const string& s, int mod, int base) -> vector<long long> { vector<long long> h(s.size() + 1, 0); vector<long long> pow_h(s.size() + 1, 1); for (int i = 0; i < s.size(); i++) { h[i+1] = (h[i] * base + s[i]) % mod; pow_h[i+1] = pow_h[i] * base % mod; } return {h, pow_h}; // 返回哈希数组和幂数组 };注意：此处
pow_h[i+1]的索引比常规写法多1，是为了让pow_h[len]直接对应base^len，避免每次计算时做pow_h[i+len-1] * inv(pow_h[i])的逆元运算——面试官若追问“为什么不怕溢出”，应回答：“long long可存约9e18，base取131时131^1e5≈1e10，完全在安全范围内。”
2.3 模型三：二维前缀和的「维度折叠陷阱」——以“Grid Paths”为例
给定n×m网格，每个格子有障碍物，求从(1,1)到(n,m)的路径数（只能右/下走）。标准解法是DP，但CSES此题数据范围达2000×2000，需用二维前缀和优化转移。易错点在于：当用dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]时，减去的dp[i-1][j-1]是前缀和数组的值，而非原始DP值！必须严格区分sum[i][j]（前缀和）和dp[i][j]（原始状态）。
// 正确维度折叠：先算原始dp，再构建前缀和用于后续查询 vector<vector<long long>> dp(n+1, vector<long long>(m+1, 0)); dp[1][1] = (grid[1][1] == '.') ? 1 : 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (grid[i][j] == '*') continue; if (i > 1) dp[i][j] = (dp[i][j] + dp[i-1][j]) % MOD; if (j > 1) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD; } } // 此时dp[i][j]才是真实路径数，前缀和另建数组 vector<vector<long long>> sum(n+1, vector<long long>(m+1, 0)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { sum[i][j] = (dp[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]) % MOD; } }提示：面试中若被问“能否用一维数组优化空间”，应回答：“可以，但需倒序更新j（从m到1），因为
dp[j]依赖于上一行的dp[j]和本行的dp[j-1]，正序会覆盖未使用的旧值——这是滚动数组的经典约束条件。”
3. 高频考点：图论中的「建模转换」——三类隐藏图结构与真题还原
CSES图论题最反直觉之处在于：题干从不出现“图”字，但解法必须先完成一次建模转换。比如“Flight Discount”题面是机票折扣，实际是分层图最短路；“Planets and Kingdoms”讲星球联盟，本质是强连通分量缩点。这类题的破题关键不是算法本身，而是识别“什么对象是节点”“什么关系是边”“边权如何定义”这三个元问题。
3.1 隐藏图一：状态即节点——以“Coin Collector”为例
题意：n个房间，每个房间有若干硬币，从房间1出发，每次移动消耗1点体力，获得当前房间所有硬币，体力耗尽前必须回到房间1。求最多收集硬币数。表面是贪心，实则是将“剩余体力”作为状态维度建图：节点定义为(room, energy)，共n×E个节点；边为从(i,e)到(j,e-1)（若i到j有边），边权为房间j的硬币数。最终答案是所有(1,e)节点的最大值。
// SPFA求最长路（因存在正权环需判正环，但本题保证无环） struct State { int room, energy; long long coins; bool operator<(const State& o) const { return coins < o.coins; // 最大堆 } }; priority_queue<State> pq; vector<vector<long long>> dist(n+1, vector<long long>(E+1, -1)); dist[1][E] = coin[1]; pq.push({1, E, coin[1]}); while (!pq.empty()) { auto [r, e, c] = pq.top(); pq.pop(); if (c != dist[r][e]) continue; for (int nxt : adj[r]) { if (e == 0) continue; // 体力耗尽无法移动 long long nc = c + coin[nxt]; if (nc > dist[nxt][e-1]) { dist[nxt][e-1] = nc; pq.push({nxt, e-1, nc}); } } } long long ans = 0; for (int e = 0; e <= E; e++) ans = max(ans, dist[1][e]);注意：此处用Dijkstra而非SPFA，因所有边权为正（硬币数≥0），且需避免SPFA在稠密图中退化。面试官若问“为什么不用DFS记忆化”，应回答：“DFS需递归栈深达E层，而E可达1e5，必然爆栈；而堆优化Dijkstra空间复杂度仅为O(nE)，时间复杂度O(nE log(nE))，在约束内可行。”
3.2 隐藏图二：操作即边——以“Teleporters Path”为例
给定n个传送门，每个传送门i可传送到a[i]，花费1秒。初始在位置x，问恰好k秒后可能到达的位置集合。题干无图，但建模为：节点是位置1..n，边是i -> a[i]，求从x出发走k步可达的所有节点。本质是矩阵快速幂优化的DP：dp[k][i] = OR(dp[k-1][j] for all j where a[j]==i)，但直接DP是O(nk)，需用邻接矩阵A的k次幂，其中A[i][j]=1当且仅当a[j]==i（注意方向！）。
// 矩阵乘法定义为布尔或运算（非数值乘） vector<vector<bool>> mat_mult(const vector<vector<bool>>& A, const vector<vector<bool>>& B) { int n = A.size(); vector<vector<bool>> C(n, vector<bool>(n, false)); for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { if (A[i][k]) { for (int j = 0; j < n; j++) { C[i][j] = C[i][j] || B[k][j]; } } } } return C; } // 快速幂 vector<vector<bool>> mat_pow(vector<vector<bool>> A, long long k) { int n = A.size(); vector<vector<bool>> res(n, vector<bool>(n, false)); for (int i = 0; i < n; i++) res[i][i] = true; // 单位矩阵 while (k) { if (k & 1) res = mat_mult(res, A); A = mat_mult(A, A); k >>= 1; } return res; }提示：面试中若被问“为何矩阵乘法用布尔或而非加法”，应回答：“本题只关心‘能否到达’，不关心路径数；用加法会导致整数溢出且无意义，布尔或精准表达可达性传递——这是图论中邻接矩阵幂的语义本质。”
3.3 隐藏图三：约束即边——以“School Dance”为例
n个男生m个女生，每个男生有偏好列表（女生编号），每个女生有偏好列表（男生编号）。求稳定匹配。题干是匹配问题，但建模为：男生和女生是二分图两部，边权为双方偏好序号之和，目标是最小化总权值。然而稳定匹配的Gale-Shapley算法不依赖边权，只依赖偏好序——这揭示了关键考点：当题干给出双向偏好时，必须意识到这是稳定婚姻问题，而非普通二分图匹配。
// Gale-Shapley算法核心：男生主动求婚，女生择优保留 vector<int> proposal(n+1, 0); // proposal[i]表示男生i当前向第proposal[i]个女生求婚 vector<int> current(m+1, 0); // current[j]表示女生j当前接受的男生 vector<vector<int>> rank_m(n+1, vector<int>(m+1)); // rank_m[i][j]表示男生i对女生j的排名（越小越喜欢） vector<vector<int>> rank_w(m+1, vector<int>(n+1)); // rank_w[j][i]表示女生j对男生i的排名 while (true) { int free_man = 0; for (int i = 1; i <= n; i++) { if (current[proposal[i]] != i) { // 男生i未被任何女生接受 free_man = i; break; } } if (!free_man) break; int j = pref_m[free_man][++proposal[free_man]]; // 向下一个偏好女生求婚 if (!current[j]) { // 女生j空闲 current[j] = free_man; } else { // 女生j已有匹配，比较偏好 int curr_man = current[j]; if (rank_w[j][free_man] < rank_w[j][curr_man]) { current[j] = free_man; // curr_man恢复自由 } } }注意：代码中
pref_m[i][k]是男生i的第k个偏好女生，rank_w[j][i]是女生j对男生i的排名。面试官若问“为何不直接用STL set维护女生候选池”，应回答：“稳定匹配要求女生在收到新求婚时，必须立即比较新旧求婚者在其偏好列表中的位置，而set无法O(1)获取某元素的排名，必须预存rank数组——这是算法正确性的前提。”
4. 易错点：C++实现中的「五处静默崩溃点」——考生血泪总结的失分黑洞
CSES题库的C++实现看似简单，实则布满编译器不报错但运行时必崩的陷阱。这些点不会出现在语法教程里，却在真实面试中让90%的候选人当场翻车。以下是根据近3年校招笔试数据统计出的五大静默崩溃点，每一条都对应真实挂科案例。
4.1 错在哪：vector::at()与operator[]混用导致越界未捕获
为什么错：operator[]不检查边界，访问v[n]（n为size）返回垃圾值；而at()抛异常但常被忽略try-catch。某考生在“Array Description”题中用dp[i][j] = dp[i-1].at(j-1)，当j=0时j-1为-1，at(-1)抛out_of_range，但主函数未捕获，程序直接终止。
怎么答对：统一用at()并在关键位置加断言：assert(j >= 0 && j < dp[i-1].size());。面试时若被问“性能影响”，应回答：“调试模式下at()开销可忽略；发布模式可用operator[]，但必须前置断言——这是防御性编程的铁律。”
4.2 错在哪：long long与int混合运算引发隐式截断
为什么错：int * int结果仍是int，即使赋值给long long。在“Sum of Divisors”题中，ans += i * (n/i)，当i和n均为1e5时，i*(n/i)达1e10，int溢出为负数，导致答案错误。
怎么答对：强制类型提升：ans += 1LL * i * (n / i);。面试官若追问“为何不全用long long声明”，应回答：“全局变量用long long增加内存开销，而局部计算中1LL*成本为零，且明确表达了开发者意图——这是C++类型安全的核心实践。”
4.3 错在哪：multiset::erase(value)误删全部相同元素
为什么错：s.erase(x)删除所有值为x的元素，而非一个。在“Movie Festival II”中，考生用seats.erase(best_seat)释放座位，结果所有同编号座位被清空，导致后续分配失败。
怎么答对：用迭代器删除单个元素：auto it = seats.find(best_seat); if (it != seats.end()) seats.erase(it);。面试中若被问“find和erase是否线程安全”，应回答：“单线程下绝对安全；若涉及并发，应改用std::shared_mutex保护整个set——但本题无并发需求，过度设计反而暴露对场景理解不足。”
4.4 错在哪：#define int long long引发模板冲突
为什么错：此宏会使std::vector<int>变成std::vector<long long>，但某些STL实现中vector<bool>是特化版本，#define int long long后vector<int>不再特化，内存暴涨100倍。在“Bit Strings”题中，考生因此MLE。
怎么答对：禁用此宏，改用using ll = long long;，并显式声明vector<ll>。面试官若问“为何不直接用long long”，应回答：“using不污染全局命名空间，且ll比long long书写更简洁；更重要的是，它让类型意图一目了然，避免宏替换带来的不可预测性——这是现代C++的推荐实践。”
4.5 错在哪：cin与scanf混用未关闭同步
为什么错：cin默认与stdio同步，混用时可能因缓冲区不一致导致读入错乱。在“Round Trip”题中，考生先用scanf("%d",&n)读n，再用cin>>m读m，结果m读入为0。
怎么答对：在main开头加ios::sync_with_stdio(false); cin.tie(nullptr);。面试中若被问“为何不关cout的tie”，应回答：“cout.tie(nullptr)解除cout与cin的绑定，避免每次输出后刷新cin缓冲区；但若程序需交互式输入输出，应保留tie——本题为纯输入，故可安全解除。”
5. 高频考点：动态规划的「状态压缩三重门」——从位运算到轮廓线DP的跃迁路径
CSES中DP题占比超25%，但真正拉开差距的是状态压缩类题目。它们不考复杂转移方程，而考“如何用最少比特编码关键信息”。这类题有清晰的三重门：第一重是经典状压（如“Hamiltonian Flights”），第二重是滚动数组优化（如“Projects”），第三重是轮廓线DP（如“Rectangle Cutting”）。跨过第三重门，意味着你能把二维平面切割问题转化为一维状态机。
5.1 第一重门：位掩码的「自然语义映射」——以“Hamiltonian Flights”为例
求有向图中从1到n的哈密顿路径数。状态定义为dp[mask][i]：已访问节点集合为mask（bitmask），当前在节点i的路径数。关键在mask的语义：第k位为1表示节点k已被访问。转移时枚举下一个节点j，要求!(mask & (1<<j))且存在边i->j。
// 初始化：dp[1<<0][0] = 1（节点0即起点1，索引偏移） vector<vector<long long>> dp(1<<n, vector<long long>(n, 0)); dp[1][0] = 1; for (int mask = 1; mask < (1<<n); mask++) { for (int i = 0; i < n; i++) { if (!(mask & (1 << i)) || !dp[mask][i]) continue; for (int j = 0; j < n; j++) { if (mask & (1 << j)) continue; // 已访问 if (!adj[i][j]) continue; // 无边 int new_mask = mask | (1 << j); dp[new_mask][j] += dp[mask][i]; } } } long long ans = dp[(1<<n)-1][n-1]; // 所有节点已访问，终点为n-1（即节点n）提示：面试中若被问“为何不预处理每个mask的popcount”，应回答：“popcount用于判断mask是否含k个1，但本题无需此信息；强行预处理增加O(2^n)空间，而状态转移本身已是O(2^n * n²)，空间应优先留给dp数组——这是空间换时间的典型权衡。”
5.2 第二重门：滚动数组的「维度折叠时机」——以“Projects”为例
n个项目，每个有开始时间s、结束时间e、价值p，求不重叠项目最大价值。标准DP是dp[i]表示前i个项目最大价值，但CSES此题n达2e5，需用坐标离散化+线段树。然而面试高频变体是：当项目数n≤1000时，可用dp[i][j]表示前i个项目、最后选第j个的最大价值，此时第二维j可滚动为一维：dp[j]表示以项目j结尾的最大价值。
// 滚动数组优化：按结束时间排序后，对每个项目i，dp[i] = p[i] + max{dp[j] for all j with e[j] <= s[i]} sort(projects.begin(), projects.end(), [](auto& a, auto& b) { return a.e < b.e; }); vector<long long> dp(n, 0); for (int i = 0; i < n; i++) { dp[i] = projects[i].p; // 二分查找最后一个e[j] <= s[i]的j int lo = 0, hi = i; while (lo < hi) { int mid = (lo + hi + 1) / 2; if (projects[mid].e <= projects[i].s) lo = mid; else hi = mid - 1; } if (lo >= 0) dp[i] += dp[lo]; } long long ans = *max_element(dp.begin(), dp.end());注意：二分查找用
lo = mid和hi = mid - 1确保收敛，且mid = (lo + hi + 1) / 2避免死循环。面试官若问“为何不直接用lower_bound”，应回答：“lower_bound返回第一个>=s[i]的位置，需手动回退一步找最后一个<=的，而手写二分更直观体现算法思想——面试中展示思考过程比调库更重要。”
5.3 第三重门：轮廓线DP的「状态连续性维护」——以“Rectangle Cutting”为例
给定w×h矩形，可沿水平或垂直线切割，每次切割产生费用=切割线长度。求切成1×1小块的最小费用。状态不能是(w,h)（会重复计算），而应是“当前待切矩形的宽度和高度”，但更优解法是轮廓线DP：将切割过程视为在网格上画分割线，状态为“当前扫描线位置及上方已切出的块高度”。
// 轮廓线DP状态：dp[mask]表示当前轮廓线形状为mask时的最小费用 // mask的每一位表示该列上方已切出的高度（0~h），共h+1种取值，需用base-(h+1)进制 // 但CSES此题h,w≤10，可直接用map<pair<int,int>, ll> memo记忆化 map<pair<int,int>, long long> memo; long long solve(int w, int h) { if (w == 1 && h == 1) return 0; if (memo.count({w, h})) return memo[{w, h}]; long long res = LLONG_MAX; // 垂直切：在x位置切，产生费用h，得到(w-x)*h和x*h两块 for (int x = 1; x < w; x++) { res = min(res, h + solve(w-x, h) + solve(x, h)); } // 水平切：在y位置切，产生费用w，得到w*(h-y)和w*y两块 for (int y = 1; y < h; y++) { res = min(res, w + solve(w, h-y) + solve(w, y)); } return memo[{w, h}] = res; }提示：面试中若被问“为何不加记忆化剪枝”，应回答：“
solve(w,h)和solve(h,w)结果相同，可强制令w≤h以减少状态数；但本题w,h≤10，状态总数仅100，无需额外优化——优先保证代码正确性和可读性，这是工程实践的第一原则。”
6. 答题策略：从CSES题库到面试现场的「三步验证法」——我的血泪教训与强制习惯
在带教某高校ACM校队时，我曾让20名队员用同一套CSES题库训练，结果面试通过率差异极大：有人刷完200题仍卡在二面，有人只精做50题却直通终面。复盘发现，差距不在刷题量，而在是否执行一套严格的「三步验证法」。这套方法源于我当年在某大厂面试时，因一道“Two Sets”题被连环追问至哑口无言的惨痛经历——当时我写出正确代码，却答不出“若n%4==2时为何无解”的数学本质，最终挂掉。从那以后，我每次写完CSES题，都强制走一遍以下三步：
6.1 第一步：反向推导「最小反例」——逼自己找出解法失效的临界点
不是检查代码是否AC，而是主动构造让它失败的数据。例如“Two Sets”题要求将1..n分为两组使和相等，标准解法是n%4==0或n%4==3时有解。那么最小反例就是n=2：此时总和为3，奇数无法均分。但面试官追问“n=6呢？”，若你只答“6%4==2所以无解”，就输了——必须说出：当n=6时，总和21为奇数，而两组和相等要求总和为偶数，故无解。这个“奇偶性约束”才是本质。现在我每道题必问：这个解法在什么最小n下首次失效？失效原因是什么数学性质被破坏？
6.2 第二步：参数敏感性分析——用表格穷举关键参数组合的影响
对含多个参数的题（如“Grid Paths”的n,m,障碍数），我强制填一张3×3表格，行是n的三种规模（小/中/大），列是m的三种规模，单元格填：当前解法时间复杂度、空间复杂度、是否需优化、优化方向。例如“Grid Paths”中，当n=m=2000时，O(nm)空间不可接受，必须滚动数组；而n=100,m=1e5时，则需转为一维DP+离散化。这张表让我在面试中被问“如果网格变成1e6×10怎么办”，能立刻答出：“改用坐标压缩+线段树，将空间从O(1e6×10)降至O(1e6 log 1e6)”。
6.3 第三步：追问链预演——模拟面试官可能的5层追问
针对每道题，我预设5个递进问题并写下答案：
- 第一问（基础）：这道题的标准解法是什么？→ 写代码
- 第二问（变形）：如果数据范围扩大10倍，哪里会超时？→ 指出瓶颈操作
- 第三问（本质）：这个解法依赖的最关键数学/算法性质是什么？→ 如“二分答案依赖单调性”
- 第四问（边界）：在什么极端情况下解法会失效？如何修复？→ 如“浮点二分需防死循环”
- 第五问（升华）：这个问题可以抽象成哪类通用模型？→ 如“所有区间合并问题都可建模为扫描线+优先队列”
这张追问链表，我存在手机备忘录里，每天通勤时随机抽一道题默背。去年带的一位A同学，面试时被问“如何优化‘Subarray Sums’的O(n²)解法”，他不仅答出前缀和O(n)，还主动补上：“如果允许误差±ε，可用滑动窗口+哈希表近似，这是流式算法的经典trade-off”——面试官当场露出惊喜表情。那一刻我知道，三步验证法真的起作用了。
从那以后我每次打开CSES题库，第一件事不是点“Submit”，而是打开笔记软件，新建一页，标题写“【三步验证】+题目名”，然后强迫自己填满那张表、写完那5个追问答案。哪怕当天只做一道题，也必须走完这三步。算法能力不是靠AC数堆出来的，而是靠每一次对“为什么”的执着追问长出来的。希望帮到你。
本文还有配套的精品资源，点击获取
