简介这份资源是面向C学习者与算法竞赛备赛者的CSES Problem Set题解代码合集针对希望系统提升算法基础与问题解决能力的程序员覆盖从入门到进阶的完整训练路径。压缩包共28个文件全部为cpp源码整体约19KB按CSES官方分类组织涵盖基础算法、动态规划、图论与树、贪心、数据结构、数学、回溯剪枝、位运算、模拟建模及编码技巧等模块如背包、硬币兑换、最小生成树、线段树、并查集、质数判断等经典题目均有对应实现。目前已有256人学习下载适合准备ACM/ICPC、Google Code Jam等赛事或提升面试表现的读者参考。通过研读这些代码可对照题目理解状态转移、DFS/BFS、贪心策略与位运算技巧并借鉴字符串处理、输入输出格式等编码细节快速建立系统的解题思路与排错方法。1. 从零拆解 CSES-Problem-Set一份能直接刷的 C 竞赛题单如果你正在准备算法竞赛或者想找一套结构清晰、难度递进的题目来系统训练CSES-Problem-Set 大概率已经被你刷到过。它是一套以 C 为主要实现语言的竞赛编程题库覆盖从入门模拟到高级图论、动态规划的完整知识体系。和零散刷题不同这套题单按专题分类每道题都有明确的输入输出约束和测试数据适合用来做专项突破。我拿到这份资源后第一件事不是急着写代码而是先看目录结构——它把题目按「Introductory Problems」「Sorting and Searching」「Dynamic Programming」「Graph Algorithms」等模块拆开每个模块内部难度递增。这意味着你可以按专题逐个击破而不是随机刷题。对于刚接触竞赛的新手它能帮你建立完整的知识地图对于有经验的选手它是一份高质量的模拟训练集。接下来我会从环境搭建、专题拆解、代码模板、避坑经验几个角度把这份资源真正用起来。2. 环境搭建与 C 编译参数把本地跑题流程固定下来2.1 编译器选择与标准版本CSES 题目对 C 标准没有强制要求但绝大多数题解和官方测试都基于 C17 或更高。我一般用 g 配合-stdc17如果本地是 Windows 环境MinGW-w64 是常见选择Linux 下直接装 build-essential 即可。不建议用太老的编译器因为部分题目会用到结构化绑定、std::optional这类特性虽然不强制但写起来更顺手。先确认版本g --version如果输出低于 9.0建议升级。我遇到过用 g 7.5 编译时std::gcd找不到的情况虽然可以手写但没必要给自己添堵。2.2 编译参数与调试开关竞赛代码和工程代码不一样不需要开一堆警告但本地调试时我习惯加两个参数g -stdc17 -O2 -Wall -Wextra -o solution solution.cpp-O2开启优化CSES 部分题目数据量在 1e5 到 2e5 级别不开优化可能超时。-Wall -Wextra本地调试时暴露未使用变量、类型转换问题提交前可以去掉。-o solution指定输出文件名避免默认的a.out覆盖。如果要做性能测试可以加-pg生成 profiling 信息但 CSES 本身不要求按需使用。2.3 输入输出重定向与本地测试CSES 的测试数据不公开但每道题页面会给出样例输入输出。我一般把样例存成input.txt和expected.txt然后用重定向跑./solution input.txt output.txt diff output.txt expected.txt这样不用每次手动输入。对于多组样例的题目可以写个简单的 shell 脚本批量跑for i in $(seq 1 5); do ./solution test$i.txt out$i.txt diff out$i.txt exp$i.txt echo test$i passed done注意CSES 的输入格式通常是单组测试但部分题目有多组查询读题时要看清。2.4 目录组织建议我习惯按专题建目录每个专题下放题目文件和测试数据cses/ ├── introductory/ │ ├── weird_algorithm.cpp │ ├── missing_number.cpp │ └── ... ├── sorting_searching/ │ ├── distinct_numbers.cpp │ └── ... └── templates/ └── fast_io.cpp这样找题和复盘都方便。不要把所有 cpp 文件堆在一个目录里后期根本分不清哪个是哪个。3. 专题拆解与代码模板从 Weird Algorithm 到图论3.1 入门专题的典型套路CSES 的 Introductory Problems 部分看起来简单但有几道题容易翻车。比如 Weird Algorithm 要求模拟 Collatz 序列看似直接循环就行但要注意用long long因为中间值可能超过int范围。我见过有人用int提交后 WA排查半天才发现是溢出。再比如 Missing Number给 n-1 个数找 1 到 n 中缺失的那个。常见做法是用求和公式但 n 可能到 2e5和会超过int必须用long long。或者用异或避免溢出#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n; cin n; long long xorsum 0; for (int i 0; i n - 1; i) { long long x; cin x; xorsum ^ x; } for (long long i 1; i n; i) { xorsum ^ i; } cout xorsum \n; return 0; }ios::sync_with_stdio(false)和cin.tie(nullptr)是竞赛标配关闭同步后 cin/cout 速度接近 scanf/printf。异或的性质a ^ a 0a ^ 0 a所以把所有数和 1 到 n 异或一遍剩下的就是缺失的数。用long long是为了防止 n 较大时中间结果溢出虽然异或本身不溢出但读入时用 long long 更保险。3.2 排序与搜索专题的边界条件Sorting and Searching 部分有几道题对边界很敏感。比如 Distinct Numbers 要求统计不同值的个数直接排序后去重或者用set都行但set的常数大n2e5 时可能卡时间。我一般用排序#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); int cnt 1; for (int i 1; i n; i) { if (a[i] ! a[i-1]) cnt; } cout cnt \n; return 0; }排序后相邻比较时间复杂度 O(n log n)比set的 O(n log n) 常数小。注意 n0 的情况虽然 CSES 不会给空输入但写代码时最好习惯性判断。如果题目要求输出具体值而不是个数可以用unique去重后输出。另一道经典题是 Concert Tickets需要维护一个有序集合并支持删除和查找前驱。用multiset可以但要注意lower_bound和upper_bound的区别。我一般用multiset加upper_bound找第一个大于目标的位置然后回退auto it tickets.upper_bound(price); if (it tickets.begin()) { cout -1 \n; } else { --it; cout *it \n; tickets.erase(it); }这里有个坑erase(it)删除的是迭代器指向的元素如果先--it再erase要确保迭代器有效。另外multiset的erase如果传值会删除所有相同元素传迭代器只删一个。3.3 动态规划的状态设计Dynamic Programming 部分是 CSES 的核心难点。以 Dice Combinations 为例求用 1 到 6 的骰子掷出 n 的方法数。状态转移很直接dp[i] sum(dp[i-k]) for k in 1..6但要注意取模和边界。#include bits/stdc.h using namespace std; const int MOD 1e9 7; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint dp(n 1, 0); dp[0] 1; for (int i 1; i n; i) { for (int k 1; k 6 i - k 0; k) { dp[i] (dp[i] dp[i - k]) % MOD; } } cout dp[n] \n; return 0; }dp[0] 1是初始状态表示凑出 0 有一种方法什么都不选。内层循环从 1 到 6且i - k 0防止越界。取模用% MOD注意dp[i] dp[i-k]可能超过 int但 MOD 是 1e97两个小于 MOD 的数相加不会超过 2e914在 int 范围内所以不用 long long。另一道题 Minimizing Coins 要求用最少的硬币凑出目标金额状态转移是dp[i] min(dp[i], dp[i-coin] 1)。这里要注意初始化dp[0] 0其他为无穷大。如果目标金额无法凑出输出 -1。3.4 图论专题的存储与遍历Graph Algorithms 部分涉及 BFS、DFS、最短路、拓扑排序等。CSES 的图通常用邻接表存储n 和 m 在 1e5 到 2e5 级别用vectorvectorint足够。以 Counting Rooms 为例给一个网格图.表示地板#表示墙求房间数。直接 DFS 或 BFS 遍历连通块#include bits/stdc.h using namespace std; int n, m; vectorstring grid; vectorvectorbool visited; int dx[] {1, -1, 0, 0}; int dy[] {0, 0, 1, -1}; void dfs(int x, int y) { visited[x][y] true; 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 !visited[nx][ny] grid[nx][ny] .) { dfs(nx, ny); } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; grid.resize(n); visited.assign(n, vectorbool(m, false)); for (int i 0; i n; i) cin grid[i]; int rooms 0; for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] . !visited[i][j]) { dfs(i, j); rooms; } } } cout rooms \n; return 0; }方向数组dx/dy是网格图遍历的常用技巧避免写四个 if。visited用vectorvectorbool注意assign的用法。递归 DFS 在 n*m 较大时可能爆栈CSES 的网格最大 1000x1000递归深度可能到 1e6建议改成栈模拟或 BFS。我一般用 BFS 更稳。4. 避坑与常见问题那些提交后 WA 或 TLE 的瞬间4.1 整数溢出导致 WA现象本地样例通过提交后部分测试点 WA。 原因中间计算结果超过int范围比如求和、乘积、累加。 解决看到题目有求和、计数、组合数优先用long long。CSES 很多题 n 到 2e5和会到 2e10必须用 64 位整数。4.2 递归深度过大导致 RE现象提交后运行时错误本地小数据正常。 原因DFS 递归深度超过栈限制CSES 的图或网格可能到 1e5 层。 解决改成 BFS 或手动栈模拟。如果必须递归可以加#pragma comment(linker, /STACK:...)但跨平台不通用不如直接改迭代。4.3 输入输出未关闭同步导致 TLE现象算法复杂度正确但提交后超时。 原因cin/cout默认与stdio同步大量输入时慢。 解决加ios::sync_with_stdio(false); cin.tie(nullptr);。注意加了之后不要混用scanf/printf。4.4 取模运算顺序错误现象结果与预期不符或者负数。 原因减法取模时忘记加 MOD比如(a - b) % MOD可能为负。 解决写成(a - b MOD) % MOD或者用((a - b) % MOD MOD) % MOD。4.5 数组越界或未初始化现象本地跑出奇怪结果或者提交后 RE。 原因vector大小不够或者全局数组未清零。 解决用vector时确认resize或assign的大小全局数组默认清零但局部数组不会需要memset或fill。5. 进阶技巧用对拍和性能分析把正确率拉满5.1 对拍脚本的写法对拍是验证算法正确性的常用手段。写一个暴力解法brute.cpp和一个优化解法fast.cpp再加一个随机数据生成器gen.cpp循环比较输出。// gen.cpp #include bits/stdc.h using namespace std; int main() { srand(time(0)); int n rand() % 100 1; cout n \n; for (int i 0; i n; i) { cout rand() % 1000 ; } cout \n; return 0; }#!/bin/bash g -stdc17 -O2 -o brute brute.cpp g -stdc17 -O2 -o fast fast.cpp g -stdc17 -O2 -o gen gen.cpp for i in $(seq 1 1000); do ./gen input.txt ./brute input.txt brute_out.txt ./fast input.txt fast_out.txt if ! diff -q brute_out.txt fast_out.txt /dev/null; then echo Difference found at test $i cat input.txt break fi done echo All tests passedgen.cpp生成随机数据注意范围要覆盖边界。brute.cpp用最直接的方法保证正确但可能慢。fast.cpp是你要验证的解法。循环 1000 次发现差异就输出输入并退出。5.2 性能分析定位瓶颈如果算法复杂度没问题但 TLE可以用chrono计时auto start chrono::high_resolution_clock::now(); // 你的代码 auto end chrono::high_resolution_clock::now(); cerr Time: chrono::duration_castchrono::milliseconds(end - start).count() ms\n;或者用gprofg -stdc17 -O2 -pg -o solution solution.cpp ./solution input.txt gprof solution gmon.out analysis.txt看analysis.txt里哪个函数占用时间最多针对性优化。5.3 常见优化手段用vector代替list缓存友好。用数组代替unordered_map如果键范围小。减少函数调用把短函数写成宏或内联。用scanf/printf如果cin/cout优化后仍慢。避免频繁push_back不预留空间用reserve。5.4 复盘习惯我每次做完一道题不管 AC 还是 WA都会把代码和思路记下来。WA 的题标注错误原因AC 的题看有没有更优解法。CSES 的题目质量很高值得反复刷。从那以后我每次提交前都强制走一遍对拍和边界测试虽然多花几分钟但省下了大量排查时间。希望帮到你。本文还有配套的精品资源点击获取
