简介CSES Problem Set 是面向C算法学习者与编程竞赛选手的高质量题解资源覆盖基础算法、动态规划、图论、贪心、数据结构、数论、回溯、位运算及模拟建模等10大核心模块精准匹配ACM/ICPC、Code Jam及大厂技术面试对算法能力的系统性要求。资源包为ZIP格式共28个独立可运行的C源文件.cpp涵盖字符串匹配、树距离、最小生成树、线段树、质数判断、棋盘回溯等典型题目实现总大小仅19KB轻量便携代码规范清晰便于逐题调试与原理验证。已有258人下载学习适合从入门到进阶的算法实践者——不仅提供完整可编译的参考实现更通过题目归类与模块化组织如String Algorithms、Graph Algorithms、Mathematics等子目录体现清晰的学习路径助力读者建立结构化算法知识体系与扎实编码习惯。1. 这不是刷题网站的镜像而是一套可本地运行、可断点调试、可二次封装的 C 算法验证沙盒你有没有试过在某个在线判题平台 AC 一道动态规划题但把代码复制到本地 g 编译后std::vector越界不报错、long long溢出没警告、输入格式稍有偏差就卡死——最后发现是平台隐藏了-D_GLIBCXX_DEBUG还替你加了ios_base::sync_with_stdio(false)CSES-Problem-Set 就是反其道而行之它不提供网页界面不托管测试数据不封装 IO它只给你一份纯 C 源码集合 标准化输入输出协议 可复现的本地验证脚本。所有题目以.cpp文件形式组织每个文件自带main()读标准输入、写标准输出完全符合 ISO/IEC 14882 标准。它适合三类人刚学完 STL 想验证std::set查找复杂度的新人、准备算法面试需反复调试状态转移的中阶开发者、以及需要把经典题解嵌入自己工程比如作为校验模块的系统工程师。这不是题库是算法的「最小可执行单元」。2. 项目结构与核心约定从目录树读懂它的设计哲学CSES-Problem-Set 的本质是一个高度自律的 C 工程实践样本。它没有CMakeLists.txt没有build/目录甚至没有src/分层——所有.cpp文件平铺在根目录下按分类子目录组织如sorting_and_searching/,graph_algorithms/。这种“扁平即正义”的结构背后藏着三个硬性约定它们共同构成了整个项目的可维护性基石。2.1 文件命名与分类逻辑用路径表达算法语义项目采用两级路径分类/ ├── sorting_and_searching/ │ ├── distinct_numbers.cpp │ ├── apartments.cpp │ └── ... ├── dynamic_programming/ │ ├── coin_combinations_i.cpp │ ├── removing_digits.cpp │ └── ... ├── graph_algorithms/ │ ├── counting_rooms.cpp │ ├── shortest_route.cpp │ └── ... └── ...每个子目录名本身就是一类算法范式的标签。distinct_numbers.cpp不叫p1234.cpp因为它的价值不在题号而在“去重”这个操作本身。更关键的是所有文件名小写下划线且与题目英文描述关键词严格对齐。这意味着你可以用grep -r coin.*combination .快速定位动态规划中组合类问题而不是靠记忆题号翻页。这种命名不是风格偏好而是为 CLI 工作流服务的基础设施——后续你会看到所有自动化验证脚本都依赖这个约定。2.2 单文件自包含无外部依赖无宏污染无全局状态打开任意一个.cpp文件例如dynamic_programming/coin_combinations_i.cpp你会发现它满足以下四条铁律头文件极简仅含iostream,vector,algorithm,climits等标准库绝无bits/stdc.h或自定义头文件无#define int long long类型劫持所有整数类型显式声明int,long long,unsigned避免隐式转换陷阱无全局变量所有数据结构均在main()内声明或通过函数参数传递IO 严格遵循标准流std::cin n;读整数std::cout ans \n;输出答案不用scanf/printf也不用endl避免 flush 开销。这种约束看似严苛实则是为了确保✅ 任何文件双击即可用g -stdc17 -O2 file.cpp -o file ./file编译运行✅ 所有文件可被#include到更大工程中只要保证命名空间干净✅ 静态分析工具如clang-tidy能直接扫描无需配置排除规则。提示如果你习惯用using namespace std;请暂时戒掉。CSES 所有文件都显式写std::vector这是为防止std::distance与自定义distance()函数发生 ADL 冲突——某次我在模拟项目X中因漏掉这点导致std::lower_bound在自定义迭代器上静默调用错误重载调试 3 小时才发现。2.3 输入输出协议统一格式即统一契约CSES 对每道题的输入输出格式做了机器可读的标准化。以graph_algorithms/counting_rooms.cpp为例// Input: first line has h, w (height and width) // next h lines each have w characters (. for floor, # for wall) // Output: single integer — number of connected components of .注意两点注释中明确写出行数、分隔符、字符含义、边界条件如h, w ≤ 1000在 README.md 中统一声明输出永远是单个值或单行字符串绝不出现Answer: to_string(ans)这类干扰判题的前缀。这个协议让自动化验证成为可能。后续章节会展示如何用 Python 脚本生成千组随机测试用例并用diff校验输出——这正是它区别于“网页题库”的核心能力把算法正确性验证从黑匣子交互变成白盒可追踪的编译-运行-比对闭环。3. 本地运行全流程从零开始跑通第一道题并验证结果别急着写代码先让环境“认得”这个项目。CSES 不要求 Docker 或虚拟环境但它对编译器版本和标准库行为有明确要求。下面是以 Ubuntu 22.04 / macOS Ventura 为基准的完整链路覆盖新手最易卡壳的五个环节。3.1 环境准备确认你的 g 支持 C17 且无 ABI 兼容问题CSES 所有代码使用 C17 特性如std::optional,if constexpr, 结构化绑定。执行以下命令验证g --version # 应输出类似g (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 # 若版本 9.0请升级sudo apt update sudo apt install g-11关键检查项不是版本号而是标准库 ABI 兼容性。某些旧版 libstdc 在std::string_view构造时存在内存越界已知影响sorting_and_searching/apartments.cpp。快速验证echo #include string_view | g -x c -stdc17 -c -o /dev/null - # 若报错 error: string_view is not a member of std说明标准库太旧注意macOS 用户若用 Homebrew 安装的 gcc务必用g-11而非系统clang因为后者默认不启用 GNU 扩展的__gnu_cxx::hash_map虽 CSES 不用但避免后续扩展踩坑。3.2 编译单个文件理解-O2和-D_GLIBCXX_DEBUG的取舍以sorting_and_searching/distinct_numbers.cpp为例# 生产级编译推荐首次运行 g -stdc17 -O2 distinct_numbers.cpp -o distinct_numbers # 调试编译发现越界时启用 g -stdc17 -D_GLIBCXX_DEBUG -g distinct_numbers.cpp -o distinct_numbers_debug参数详解-O2开启二级优化保留调试信息-g可选平衡速度与可调试性-D_GLIBCXX_DEBUG激活 GNU libstdc 的容器调试模式使vector[i]越界立即 abort而非静默 UB切勿同时用-O2和-D_GLIBCXX_DEBUG前者会内联函数后者需函数符号冲突导致编译失败。运行验证# 准备输入按题目要求第一行n第二行n个整数 echo -e 5\n2 3 2 2 3 | ./distinct_numbers # 输出应为2 表示不同数字个数3.3 批量验证用 Python 脚本驱动测试用例CSES 官方不提供测试数据但项目根目录下有testgen/子目录需手动创建里面存放生成器脚本。我们用一个通用生成器gen_random_ints.py# testgen/gen_random_ints.py import sys import random def main(): n int(sys.argv[1]) if len(sys.argv) 1 else 1000 # 生成 n 个 [1, 1000] 范围内的随机整数 nums [random.randint(1, 1000) for _ in range(n)] print(n) print( .join(map(str, nums))) if __name__ __main__: main()然后编写验证脚本verify.py#!/usr/bin/env python3 import subprocess import sys import os def run_solution(sol_path, input_data): 运行可执行文件返回 stdout 字符串 result subprocess.run( [sol_path], inputinput_data, textTrue, capture_outputTrue, timeout5 ) return result.stdout.strip() def count_distinct(nums): Python 参考实现 return len(set(nums)) if __name__ __main__: sol ./distinct_numbers # 生成 10 组测试 for i in range(10): # 生成输入 input_data subprocess.check_output( [python3, testgen/gen_random_ints.py, 100] ).decode().strip() # 获取 C 输出 cpp_out run_solution(sol, input_data) # 解析输入得到期望答案 lines input_data.strip().split(\n) n int(lines[0]) nums list(map(int, lines[1].split())) expected str(count_distinct(nums)) if cpp_out ! expected: print(f❌ Test {i} failed!) print(fInput: {input_data}) print(fExpected: {expected}, Got: {cpp_out}) sys.exit(1) print(✅ All tests passed!)执行python3 verify.py。这个脚本的价值在于它把“人工肉眼比对”变成了可重复、可集成到 CI 的步骤。当你修改算法时只需改一行cpp_out ...就能切换对比基准比如换成 Rust 实现。3.4 常见问题排查五条血泪经验总结现象 → 原因 → 解决全是真实翻车现场现象./distinct_numbers运行后卡住CtrlC 显示SIGINT但无输出原因输入数据末尾缺换行符std::cin n阻塞等待CSES 要求输入严格按行最后一行必须有\n解决用echo -e 5\n2 3 2 2 3\n | ./distinct_numbers注意末尾\n或在生成器中print()后加空行现象g报错error: optional is not a member of std原因编译器版本 ≥ 10 但未启用 C17 标准或头文件未包含optionalCSES 文件已包含故必是编译参数问题解决确认命令为g -stdc17 ...而非-stdgnu17后者可能禁用部分标准特性现象本地输出2但提交到在线平台显示 WAWrong Answer原因平台输入含 Windows 换行符\r\n而std::cin默认跳过空白但某些情况下\r被当作字符读入解决在main()开头加std::cin.sync_with_stdio(false); std::cin.tie(nullptr);并确保输入生成器用 Unix 换行echo -e默认满足现象make命令报错make: *** No targets. Stop.原因CSES 无 Makefile新手误以为需 make项目设计就是g直接编译解决删掉所有Makefile相关尝试回归g -stdc17 xxx.cpp -o xxx现象valgrind ./distinct_numbers显示Invalid read of size 8原因代码中vectorint a(n); a[n] 1;越界但-O2优化后未触发崩溃解决先用-D_GLIBCXX_DEBUG编译复现定位越界位置C17 下可用a.at(n)替代a[n]强制边界检查4. 核心模块拆解dynamic_programming/coin_combinations_i.cpp的完整链路这道题是 CSES 动态规划入门题求用给定面额硬币组成目标金额的方案数每种硬币无限使用。它短小精悍仅 25 行却浓缩了背包问题的精髓。我们逐段解析重点看它如何用最简 C 表达状态转移并规避常见陷阱。4.1 完整源码与逐行注释#include iostream #include vector #include algorithm using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, x; cin n x; // n: coin types, x: target sum vectorint coins(n); for (int i 0; i n; i) { cin coins[i]; } // dp[i] number of ways to make sum i // Use long long to avoid overflow on large x (x 1e6) vectorlong long dp(x 1, 0); dp[0] 1; // base case: one way to make sum 0 (use no coins) // Iterate over coins first - ensures unlimited supply per coin for (int coin : coins) { for (int s coin; s x; s) { dp[s] dp[s - coin]; } } cout dp[x] \n; }关键点解析ios_base::sync_with_stdio(false); cin.tie(nullptr);解除 C 与 C IO 流同步提升大输入读取速度x 可达 1e6输入行数多vectorlong long dp(x 1, 0)x最大为 1e6dp数组大小 1e61用long long防止方案数溢出如全用 1 元硬币方案数 1外层遍历 coins内层遍历 s 从 coin 到 x这是“完全背包”的标准写法保证每种硬币可重复使用若内外层颠倒则变成“0-1 背包”每种硬币只能用一次dp[0] 1数学上组成 0 元只有一种方法——不选任何硬币这是所有 DP 的起点漏掉则全盘皆错。4.2 状态转移的物理意义为什么dp[s] dp[s - coin]假设当前处理硬币面额coin 2目标s 5dp[5]表示组成 5 元的所有方案数dp[5-2] dp[3]表示组成 3 元的所有方案数每一种组成 3 元的方案末尾加一枚 2 元硬币就得到一种组成 5 元的方案因此新增方案数 dp[3]累加到dp[5]。这个逻辑成立的前提是dp[3]已包含所有用之前硬币如 1 元组成的方案。所以必须先固定 coin再从小到大更新 s——这就是循环顺序的设计依据。4.3 边界条件与数值安全x 0和溢出防护当x 0时vectorlong long dp(1, 0)创建大小为 1 的数组dp[0] 1正确设置外层for (int coin : coins)中内层for (int s coin; s x; s)因coin 1且x 0循环体不执行最终输出dp[0] 1符合数学定义。溢出防护体现在两处long long类型x ≤ 1e6最坏情况全 1 元方案数为 1不会溢出但若硬币含 1 元方案数实际是组合数long long可支撑x ≤ 1e6dp数组大小x 1若x 0x 1 1无越界若x 1e6dp占用约 8MB 内存在现代机器上安全。提示我曾在模拟项目X中把dp声明为vectorint测试时x 100000时dp[100000]溢出为负数导致后续计算全错。从此养成习惯凡计数类 DP无脑long long除非明确知道上界小于2^31。4.4 可视化调试技巧用cerr打印中间状态当逻辑复杂时在main()中插入调试输出发布前删除// 在双重循环内添加仅调试用 // for (int coin : coins) { // cerr Processing coin: coin \n; // for (int s coin; s x; s) { // long long prev dp[s]; // dp[s] dp[s - coin]; // cerr dp[ s ] prev dp[ (s-coin) ] dp[s] \n; // } // }cerr输出到 stderr不影响 stdout 的答案输出且g -O2不会优化掉cerr与cout不同。这是比 IDE 断点更轻量的调试方式尤其适合算法题。5. 二次开发实战把 CSES 题解封装成 C 库函数供其他项目调用这才是 CSES 的隐藏价值——它不是终点而是你工程中的一个模块。设想你在开发某跨平台系统需要频繁计算“硬币组合数”但不想每次复制粘贴coin_combinations_i.cpp。下面教你把它变成可链接的静态库并支持 C 风格调用。5.1 提取核心逻辑为独立头文件新建lib/coin_combinations.h#ifndef COIN_COMBINATIONS_H #define COIN_COMBINATIONS_H #ifdef __cplusplus extern C { #endif /** * brief Calculate number of ways to make target sum with given coins * param coins: array of coin denominations * param n: number of coin types * param x: target sum (0 x 1000000) * return number of combinations, or -1 on error (e.g., x 0) */ long long coin_combinations(const int* coins, int n, int x); #ifdef __cplusplus } #endif #endif新建lib/coin_combinations.cpp#include coin_combinations.h #include vector #include algorithm long long coin_combinations(const int* coins, int n, int x) { if (x 0) return -1; if (x 0) return 1; std::vectorlong long dp(x 1, 0); dp[0] 1; for (int i 0; i n; i) { int coin coins[i]; if (coin 0) continue; // skip invalid coins for (int s coin; s x; s) { dp[s] dp[s - coin]; } } return dp[x]; }关键改造点添加extern C块确保 C 编译器生成 C 风格符号避免 name mangling参数改为指针长度符合 C 接口惯例调用方无需std::vector增加输入校验x 0返回 -1coin 0跳过增强鲁棒性移除所有using namespace std和ios_base设置库函数不应干涉调用方 IO 状态。5.2 编译为静态库并链接使用# 编译为对象文件 g -stdc17 -c lib/coin_combinations.cpp -o lib/coin_combinations.o # 打包为静态库 ar rcs libcoin.a lib/coin_combinations.o # 使用示例test_user.cpp #include iostream #include lib/coin_combinations.h int main() { int coins[] {1, 2, 5}; long long res coin_combinations(coins, 3, 10); std::cout Ways: res \n; // 输出 10 }编译链接g -stdc17 test_user.cpp -L. -lcoin -o test_user ./test_user # 输出 Ways: 105.3 进阶支持自定义分配器与异常安全若你的系统对内存敏感如嵌入式可进一步改造coin_combinations接受自定义分配器// 在头文件中增加重载 long long coin_combinations_custom_alloc( const int* coins, int n, int x, void* (*alloc_func)(size_t), // malloc-like void (*free_func)(void*) // free-like );实现中用alloc_func(sizeof(long long) * (x1))替代std::vector并在函数退出前调用free_func。这需要你熟悉placement new但 CSES 的简洁结构让这种改造成本极低——因为原始代码无全局状态、无资源泄漏点。从那以后我每次把算法题解迁移到生产环境都强制走一遍“提取头文件 → 编译静态库 → 编写 C 调用示例 → valgrind 检查内存”的流程。哪怕只是临时脚本这套动作也成了肌肉记忆。它逼我思考这段代码的输入契约是什么输出是否可预测失败时能否优雅降级CSES 不教这些但它用最朴素的.cpp文件给了我练习这些工程直觉的沙盒。希望帮到你。本文还有配套的精品资源点击获取