简介CSES Problem Set 是面向算法学习者与C编程进阶者的高质量在线题集配套代码资源覆盖基础语法、动态规划、图论、贪心、数论、位运算等10大核心模块专为ACM/ICPC备赛、大厂技术面试及算法能力系统性提升设计。资源包共28个文件全部为可直接编译运行的C源码.cpp涵盖字符串匹配、树距离计算、最小生成树、线段树、回溯路径搜索等典型题目实现代码结构清晰、注释规范便于理解算法逻辑与编码细节。压缩包仅19KB轻量易用目录按主题分层组织如String Algorithms、Graph Algorithms、Mathematics等支持按知识点精准定位学习。目前已有256人下载学习所含28份完整可执行方案不仅提供标准解法更隐含常见边界处理、输入输出优化及复杂度控制思路是夯实C算法工程实现能力的实用型代码参考集。1. 这不是刷题网站的镜像而是一套可本地运行、可断网调试、可嵌入CI的C算法验证沙盒你有没有试过在面试前夜想重跑一道经典动态规划题却发现网页题库加载失败或者在飞机上想复现某道图论题的优化解法结果连提交按钮都点不动CSES-Problem-Set 就是为这种场景而生的——它把整个在线判题系统的核心逻辑打包成一个纯本地、零依赖、开箱即用的 C 工程。它不提供前端界面不连数据库不走 HTTP 协议它只做一件事给你一个标准输入/输出契约一套预置测试用例和一个可被g -stdc17直接编译的骨架代码目录。所有题目按难度分层组织入门 → 数学 → 图论 → 字符串 → 高级数据结构每道题附带官方标程、暴力解、最优解三版参考实现更重要的是——每个.cpp文件里都埋了// TODO: implement solution here的明确锚点以及配套的test/子目录下对应.in和.out文件。这不是教学课件也不是 PDF 题集而是一个能make test自动比对输出、支持gdb单步调试、甚至可被 Jenkins 拉取后跑通全部 300 题目的真实工程。适合正在准备算法岗笔试的应届生、需要快速验证新思路的竞赛老手以及想把算法模块集成进自己系统的 C 开发者。2. 项目结构与构建流程从 clone 到首次通过测试的完整链路2.1 目录结构解析为什么 test/ 和 solutions/ 是平行而非嵌套关系项目根目录下最核心的四个一级目录是solutions/、test/、tools/和docs/。其中solutions/下按题目编号如1068、1070组织每个编号子目录内包含solution.cpp待填空主文件、brute.cpp暴力参考、optimal.cpp最优解和Makefile单题编译规则。test/目录则严格按相同编号镜像例如test/1068/001.in对应solutions/1068/solution.cpp的第一组输入001.out是预期输出。这种平行结构不是随意设计——它让tools/run_test.py脚本能用统一路径模板test/{id}/{n}.in → solutions/{id}/solution.cpp → diff against test/{id}/{n}.out完成全量回归。如果你把测试用例塞进solutions/里就会破坏工具链的路径推导逻辑导致make test-all报No such file or directory: test/1068/001.in。我第一次翻车就栽在这儿手动移动了test/下的某个子目录结果整套自动化测试直接哑火。# 正确的目录树节选 CSES-Problem-Set/ ├── solutions/ │ ├── 1068/ # Collatz Sequence 题目 │ │ ├── solution.cpp # 你写的代码必须读 cin n; 输出序列 │ │ ├── brute.cpp # O(n²) 暴力模拟用于生成测试答案 │ │ └── Makefile # 定义 g -o sol1068 solution.cpp │ └── 1070/ # Chessboard and Queens ├── test/ │ ├── 1068/ │ │ ├── 001.in # 输入3 │ │ ├── 001.out # 输出3 10 5 16 8 4 2 1 │ │ └── 002.in # 输入1 │ └── 1070/ ├── tools/ │ ├── run_test.py # 主测试驱动支持 --id 1068 --verbose │ └── gen_test.py # 用 brute.cpp 自动生成 .out 文件 └── Makefile # 全局入口make test-all → 调用 tools/run_test.py提示solutions/{id}/Makefile中的CXXFLAGS -stdc17 -O2 -Wall -Wextra是硬性要求。CSES 所有题目默认开启-O2且部分题如 1620 Tree Distances I在-O0下会因递归栈溢出超时。别试图删掉-O2来方便调试——正确做法是g -g -O0单独编译调试版但提交前务必切回-O2。2.2 构建与测试命令详解make、python、g 三层协作机制整个构建流程本质是三层调用顶层make解析全局Makefile中层python tools/run_test.py控制测试流底层g编译执行。执行make test-id ID1068时实际发生的是Makefile中test-id:规则展开为python tools/run_test.py --id $(ID) --verboserun_test.py读取solutions/1068/Makefile获取编译命令如g -stdc17 -O2 solution.cpp -o sol1068执行编译再遍历test/1068/*.in对每个输入文件./sol1068 test/1068/001.in /tmp/out.txtdiff /tmp/out.txt test/1068/001.out关键参数说明--timeout 2强制进程 2 秒内退出避免死循环卡住 CI--diff-mode unified输出diff -u格式便于快速定位第几行不匹配--no-color关闭 ANSI 颜色码适配 Jenkins 日志解析# tools/run_test.py 关键片段已简化 def run_single_test(solution_dir: Path, test_in: Path, test_out: Path) - bool: # 1. 从 solutions/{id}/Makefile 提取可执行名正则匹配 all:.*?([a-zA-Z0-9_]) exe_name parse_makefile_for_exe(solution_dir / Makefile) # 2. 编译cd 到 solution_dir 后执行 make subprocess.run([make], cwdsolution_dir, checkTrue) # 3. 执行并捕获输出 with open(test_in, r) as f_in: result subprocess.run( [f./{exe_name}], stdinf_in, capture_outputTrue, textTrue, timeout2 # ⚠️ 必须设 timeout否则无限循环无感知 ) # 4. 比对用 difflib.SequenceMatcher 计算相似度容错空格/换行 actual_lines result.stdout.strip().splitlines() expected_lines test_out.read_text().strip().splitlines() return actual_lines expected_lines注意subprocess.run的timeout2是防御性设计。CSES 题目时间限制普遍为 1 秒但本地机器性能波动大设 2 秒既留出余量又防止真死循环拖垮整套测试。2.3 首次运行避坑指南环境、权限与路径的三重校验现象 1make test-id ID1068报错No rule to make target test-id原因当前目录不在项目根目录或Makefile被意外修改比如删掉了.PHONY: test-id声明。CSES 的Makefile依赖 GNU Make 的隐式规则若缺失.PHONYmake 会尝试把test-id当作文件去查找。解决cd到项目根目录执行ls -l Makefile确认文件存在且未被破坏若曾编辑过用git checkout -- Makefile恢复。现象 2python tools/run_test.py --id 1068提示PermissionError: [Errno 13] Permission denied: ./sol1068原因g编译生成的可执行文件没有执行权限尤其在 Windows WSL 或某些 NFS 挂载点下。Linux 默认不继承源文件权限。解决在solutions/1068/Makefile的编译命令后追加chmod x $(EXE)例如all: $(EXE) $(CXX) $(CXXFLAGS) solution.cpp -o $(EXE) chmod x $(EXE)现象 3测试输出与预期完全一致但diff显示Files /tmp/out.txt and test/1068/001.out differ原因Windows 换行符CRLF污染。若你在 Windows 上用记事本编辑过solution.cpp保存时可能插入\r\n导致输出多出\r字符。解决全局配置 Git 自动转换git config --global core.autocrlf input然后rm test/1068/*.out python tools/gen_test.py --id 1068重新生成纯净.out文件。现象 4g报错error: ‘__int128’ was not declared in this scope原因部分题目如 1712 Exponentiation II需用__int128处理 10^18 级别幂运算但旧版 GCC7.0不支持。解决升级 GCC 至 7.5或改用 Clangsudo apt install clang然后修改solutions/1712/Makefile中CXX clang并添加-stdc17。3. 核心模块拆解solution.cpp 的标准契约与四类题目模板3.1 输入/输出契约为什么所有 solution.cpp 都以 while(cin n) 开头CSES 题目输入格式高度结构化solution.cpp的第一行几乎总是#include iostream第二行是using namespace std;第三行开始处理输入。但真正决定程序行为的是输入终止条件。观察solutions/1068/solution.cpp#include iostream using namespace std; int main() { long long n; while (cin n) { // ← 关键题目未说明输入组数用 EOF 终止 while (n ! 1) { cout n ; if (n % 2 0) n / 2; else n 3 * n 1; } cout 1 endl; } }这个while (cin n)不是随意写的——它对应 CSES 官方题面中 “The only input line has an integer n” 的隐含扩展多组测试用例连续输入以 EOF 结束。这是 CSES 所有入门题的默认契约。若你写成cin n;单次读取则只能通过第一个测试点后续用例因无输入而卡死。同理字符串题如 1071 Message Route要求cin n m;读节点数和边数之后用for(int i0; im; i) cin u v;读边这种固定组数的模式在图论题中占 70%。注意long long是安全选择。CSES 明确要求 n ≤ 10^6但 Collatz 序列中间值可能达 10^12int会溢出。我见过三次因用int n导致 WA 的血泪案例——错误输出不是逻辑错而是计算中途变负数。3.2 四类题目模板从模拟到高级数据结构的代码骨架CSES 题目可归纳为四大模式每种对应固定代码骨架题目类型代表题号输入特征solution.cpp 核心结构关键注意事项模拟类1068, 1070单整数/单字符串while(cinn){...}或string s; cins;注意边界n1 时 Collatz 序列只有 1数学类1069, 1072多参数a,b,kcinabk; coutpow_mod(a,b,k)endl;必须手写快速幂std::pow会 double 精度丢失图论类1620, 1621n,m 后跟 m 行边vectorvectorint adj(n1); for(i0;im;i){cinuv; adj[u].push_back(v);}节点编号从 1 开始邻接表大小开 n1数据结构类1647, 1652q 次查询cinq; while(q--){int op; cinop; if(op1)... else ...}线段树必须用 0-indexed 数组别信模板里的 1-indexed以图论题 1620 Tree Distances I 为例其solution.cpp骨架必须包含#include iostream #include vector #include queue #include algorithm using namespace std; int main() { int n; cin n; vectorvectorint adj(n1); // ← 关键n1因节点 1~n for (int i 0; i n-1; i) { int u, v; cin u v; adj[u].push_back(v); adj[v].push_back(u); } // BFS 求每个点到 1 号点距离第一次 BFS vectorint dist1(n1, -1); queueint q; q.push(1); dist1[1] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist1[v] -1) { dist1[v] dist1[u] 1; q.push(v); } } } // 第二次 BFS 求直径端点第三次求所有点最大距离... // 此处省略但结构必须是三次 BFS 或树形 DP }3.3 测试用例生成原理brute.cpp 如何成为你的“后悔药”brute.cpp不是摆设。当你卡在某道题如 1652 Hotel Queries的边界 case 时brute.cpp是唯一能给你确定性答案的参照物。它的生成逻辑很简单对小规模输入n≤100用 O(n²) 暴力枚举所有可能输出精确答案。tools/gen_test.py会调用它# 生成 test/1652/001.in随机小数据 python tools/gen_test.py --id 1652 --size small --count 1 # 用 brute.cpp 计算答案存为 001.out cd solutions/1652 ./brute ../../test/1652/001.in ../../test/1652/001.outbrute.cpp的价值在于它帮你绕过“我的算法是否正确”的哲学问题直击“我的输出是否符合数学定义”。比如酒店查询题暴力解就是对每个查询q[i]从左到右扫描房间数组找到第一个 ≥q[i]的位置——逻辑清晰到无法歧义。当你发现solution.cpp输出和brute.cpp不一致问题 100% 出在你的优化逻辑里而不是测试用例错了。4. 算法实现精要三道高频题的 C 关键代码与踩坑实录4.1 动态规划题 1637: Projects —— 状态压缩与二分优化的临界点这道题要求在时间区间不重叠前提下最大化收益。标准解法是排序后 DPdp[i] max(dp[i-1], profit[i] dp[j])其中j是最后一个与i不重叠的项目索引。难点在于如何快速找j。错误做法TLE对每个i从i-1往前线性扫描找j。正确做法AC预处理prev[i]数组用二分查找upper_bound定位。#include iostream #include vector #include algorithm #include cctype using namespace std; struct Project { int start, end, profit; bool operator(const Project o) const { return end o.end; } }; int main() { int n; cin n; vectorProject p(n); for (int i 0; i n; i) { cin p[i].start p[i].end p[i].profit; } sort(p.begin(), p.end()); // 按 end 排序 // 预处理 prev[i]最大的 j 使得 p[j].end p[i].start vectorint prev(n, -1); for (int i 0; i n; i) { // 在 [0, i-1] 中找最后一个 end p[i].start 的索引 int lo 0, hi i; while (lo hi) { int mid (lo hi 1) / 2; // 上取整避免死循环 if (p[mid].end p[i].start) lo mid; else hi mid - 1; } if (lo i) prev[i] lo; } vectorlong long dp(n); dp[0] p[0].profit; for (int i 1; i n; i) { long long take p[i].profit; if (prev[i] ! -1) take dp[prev[i]]; dp[i] max(dp[i-1], take); } cout dp[n-1] endl; }关键参数说明sort(p.begin(), p.end())必须按end排序这是 DP 状态转移的基础若按start排会破坏无后效性。二分查找用while (lo hi)(lo hi 1) / 2是经典上界查找模板确保lo停在满足条件的最大索引。用(lo hi) / 2会导致lo停在最小索引从而漏掉更优解。dp数组用long long收益总和可能超int10^5 个项目每个收益 10^9总和 10^14。4.2 图论题 1620: Tree Distances I —— 两次 BFS 求树直径的严谨性证明此题要求输出每个节点到其他节点的最大距离即该点的偏心距。暴力解 O(n²) 必 TLE正解是利用树的性质任意点u的最远点必为树直径的某一端点。核心逻辑任取一点如 1BFS找到最远点a从aBFS找到最远点ba-b即为直径从a和b分别 BFS得到distA[i]和distB[i]对每个i答案 max(distA[i], distB[i])#include iostream #include vector #include queue #include algorithm using namespace std; int main() { int n; cin n; vectorvectorint adj(n1); for (int i 0; i n-1; i) { int u, v; cin u v; adj[u].push_back(v); adj[v].push_back(u); } auto bfs [](int start) - vectorint { vectorint dist(n1, -1); queueint q; q.push(start); dist[start] 0; while (!q.empty()) { int u q.front(); q.pop(); for (int v : adj[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } } return dist; }; vectorint dist1 bfs(1); int a 1; for (int i 1; i n; i) if (dist1[i] dist1[a]) a i; vectorint distA bfs(a); int b a; for (int i 1; i n; i) if (distA[i] distA[b]) b i; vectorint distB bfs(b); for (int i 1; i n; i) { cout max(distA[i], distB[i]) ; } cout endl; }为什么必须两次 BFS第一次 BFS 找a是为了定位直径一端但仅凭dist1无法保证a是直径端点可能只是局部最远。第二次从a出发 BFS必然到达直径另一端b因为树中两点间路径唯一a的最远点必在直径上。这是树的中心性质不可省略。4.3 数学题 1094: Modular Exponentiation —— 手写快速幂的三个致命细节此题要求计算a^b mod m其中b可达 10^9。std::pow会溢出且无模运算必须手写快速幂。long long mod_pow(long long base, long long exp, long long mod) { long long res 1; base % mod; // ← 细节1base 可能 mod先取模 while (exp 0) { if (exp 1) { res (res * base) % mod; // ← 细节2每次乘后立即取模防 long long 溢出 } base (base * base) % mod; // ← 细节3base 平方也需取模 exp 1; } return res; } int main() { long long a, b, m; cin a b m; cout mod_pow(a, b, m) endl; }三个细节缺一不可若跳过base % mod当a10^18, mod10^97时base * base直接溢出long long最大约 9×10^18。若res res * base不取模res可能达(mod-1)^2超long long。exp 1判断奇偶比exp % 2 1快且避免负数取模陷阱虽然本题exp≥0。5. 本地调试与 CI 集成从单步调试到 Jenkins 自动化验证5.1 GDB 调试实战如何在 solution.cpp 中设置条件断点观测中间状态CSES 题目逻辑密集光看输出难定位错误。以题 1647 Range Update Queries 为例它要求支持区间加和单点查。当你发现第 5 个查询结果错误但不知道是更新没生效还是查询读错了GDB 是唯一出路。步骤在solutions/1647/Makefile中将CXXFLAGS改为-g -O0 -stdc17加-g生成调试信息关-O2防止变量优化消失make编译启动 GDBgdb ./sol1647设置断点break solution.cpp:25 if i5假设第 25 行是查询循环i是查询序号运行run test/1647/001.in// solutions/1647/solution.cpp 片段 int main() { int n, q; cin n q; vectorlong long arr(n1, 0); vectorlong long diff(n2, 0); // 差分数组开 n2 防越界 for (int i 0; i q; i) { int op; cin op; if (op 1) { int l, r, x; cin l r x; diff[l] x; diff[r1] - x; // ← 断点设在此行观察 diff[l] 和 diff[r1] 是否正确 } else { int k; cin k; long long sum 0; for (int j 1; j k; j) sum diff[j]; // ← 断点设在此行观察 sum 累加过程 cout sum endl; } } }关键技巧用display diff命令让 GDB 每次停顿时自动打印diff数组前 10 项用watch diff[5]监视特定位置当diff[5]被修改时自动中断用btbacktrace查看调用栈确认是否进入正确分支注意GDB 在 WSL 中可能因符号表缺失报No symbol table is loaded。解决方法是apt install build-essential gdb确保安装完整调试工具链且编译时必须带-g。5.2 Jenkinsfile 集成如何让每次 push 自动跑通全部 300 题将 CSES 工程接入 CI 的核心是把make test-all封装成可重复执行的 pipeline。以下是一个生产可用的Jenkinsfile片段pipeline { agent any environment { CC gcc-11 CXX g-11 } stages { stage(Checkout) { steps { checkout scm } } stage(Build Test) { steps { sh sudo update-alternatives --install /usr/bin/gcc gcc /usr/bin/gcc-11 100 sh sudo update-alternatives --install /usr/bin/g g /usr/bin/g-11 100 sh make clean || true // 关键用 timeout 防止某道题死循环拖垮整条流水线 sh timeout 600 make test-all || echo Test failed, see logs above } } } post { always { archiveArtifacts artifacts: test-results/**/*.xml, allowEmptyArchive: true } failure { emailext ( subject: FAILED: ${env.JOB_NAME} [${env.BUILD_NUMBER}], body: Check console output at ${env.BUILD_URL}console, recipientProviders: [[$class: DevelopersRecipientProvider]] ) } } }参数说明timeout 600给全量测试设 10 分钟上限。CSES 300 题在 4 核机器上通常 3~5 分钟跑完10 分钟足够覆盖异常。update-alternatives确保使用 GCC 11支持 C17 完整特性避免因编译器版本低导致std::optional等特性不可用。make clean || true清除上次编译残留|| true防止clean规则不存在时报错中断 pipeline。5.3 常见 CI 失败排查五类典型日志与对应修复动作现象 1Jenkins 控制台输出Killed原因进程被 Linux OOM Killer 终止。常见于内存密集型题如 1697 Counting RoomsDFS 递归过深或邻接表过大。修复在solutions/{id}/Makefile中添加栈空间限制g -Wl,-stack_size,0x10000000macOS或ulimit -s 65536Linux。现象 2make test-all报Command python not found原因Jenkins agent 未预装 Python 3。CSES 工具链依赖 Python 3.6。修复在Jenkinsfile的stage(Checkout)后添加sh sudo apt-get update sudo apt-get install -y python3 python3-pip sh sudo ln -sf /usr/bin/python3 /usr/bin/python现象 3某道题测试通过但 Jenkins 显示UNSTABLE原因tools/run_test.py检测到超时subprocess.TimeoutExpired但未设failOnError: false。修复修改Jenkinsfile中sh命令为sh make test-all || exit 0 // 强制不失败让 post 阶段处理现象 4diff显示Binary files ... differ原因.out文件被当作二进制如含\0字符但 CSES 输出纯文本。修复在tools/run_test.py中强制文本模式with open(test_out, r, encodingutf-8) as f: expected_lines f.read().strip().splitlines()现象 5make test-id ID1068本地成功Jenkins 失败原因Jenkins 使用shshell而本地是bash$()语法在sh中不支持。修复将tools/run_test.py中所有subprocess.run(echo $(date), ...)改为subprocess.run([date], ...)避免 shell 特性。6. 二次开发指南如何安全地添加新题、替换标程、定制测试策略6.1 添加新题的标准化流程从题目分析到自动化测试注入假设你要新增题目 “1750: String Transformation”需求是给定字符串 s 和 t问能否通过若干次操作删除首字符或末字符使 s 变成 t。步骤 1创建目录结构mkdir -p solutions/1750 test/1750 cp templates/solution.cpp solutions/1750/solution.cpp cp templates/brute.cpp solutions/1750/brute.cpp cp templates/optimal.cpp solutions/1750/optimal.cpp步骤 2编写 brute.cpp保证正确性// solutions/1750/brute.cpp #include iostream #include string #include vector using namespace std; bool can_transform(const string s, const string t) { if (t.length() s.length()) return false; // 枚举所有长度为 t.length() 的子串 for (int i 0; i (int)s.length() - (int)t.length(); i) { if (s.substr(i, t.length()) t) return true; } return false; } int main() { string s, t; cin s t; cout (can_transform(s, t) ? YES : NO) endl; }步骤 3生成测试用例# 生成 5 组随机测试 python tools/gen_test.py --id 1750 --count 5 --generator python -c \import random; s.join(random.choices(abc, krandom.randint(1,10))); t.join(random.choices(abc, krandom.randint(0,len(s)))); print(s); print(t)\ # 用 brute.cpp 计算答案 for i in $(seq 1 5); do ./brute test/1750/$(printf %03d $i).in test/1750/$(printf %03d $i).out done步骤 4注入全局测试流修改tools/run_test.py的SUPPORTED_IDS列表加入1750修改Makefile的 test本文还有配套的精品资源点击获取