简介面向备战全国青少年信息学奥林匹克竞赛NOIP的选手与编程爱好者这套合集以C代码为核心覆盖排序、搜索、动态规划、图论、字符串处理等信奥常考知识点的实现方案与解题思路适合有一定编程基础、希望在备赛阶段集中刷题和巩固算法的学员。压缩包内含219个文件整体仅1.02MB以202个cpp代码文件为主体配合10个md说明文档、2个pptx课件、2个exe工具以及docx、png等辅助内容代码体量适中便于直接编译学习md文档可辅助理解思路课件适合讲解与回顾。目前已有615人下载学习。整理者Ganyang456按题号收录了P4180、P1967、P5588等典型问题既有可直接运行的算法实现也有思路解析与训练笔记能够帮助备赛者快速熟悉竞赛代码写法从读题、建模到编码形成完整闭环也可用于赛前查漏补缺。1. 信奥赛代码合集一份把“题解博客”变成“可跑工程”的备赛资源如果你曾经在半夜找一道图论的题解复制下来的代码却缺了两行头文件或者在自己的编译器上跑出了“段错误”你大概会明白“题解散落各处”有多折磨人。这份信奥赛代码合集把分区联赛常见题型、算法模板、数据结构和配套样例测试收进同一个目录统一用 C11 编写拿到手就能直接编译运行。它最大的价值不是多了几份代码而是提供了一套完整的备赛工程结构按算法主题找模板、按题目目录找题解、按测试目录验证答案全程不用打开网页拼碎片。适合正在备战分区联赛的学生也适合带集训队、给选手搭本地训练环境的教练以及任何想快速回顾经典竞赛算法的开发者。2. 整体架构与目录设计按题型和算法双索引不靠记忆翻文件2.1 目录总览模板与题目分开存放互不污染这套合集没有把所有代码堆在一个文件夹里而是先把“可复用算法模板”和“具体题目题解”拆成两条线。模板追求稳定测过一遍就不希望频繁改动题目会随着模拟赛不断添加更新频率高。两者混在一起会不断制造无意义的 diff时间一长自己也搞不清哪个版本是能跑的。于是目录分成了两层第一层是算法主题第二层是题目仓库。noip-code-collection/ ├── README.md ├── Makefile ├── templates/ # 输入输出、调试、通用宏 │ ├── io_fast.cpp │ └── debug.hpp ├── data_struct/ # 数据结构模板 │ ├── segment_tree.cpp │ ├── fenwick_tree.cpp │ ├── dsu.cpp │ └── treap.cpp ├── graph/ # 图论相关 │ ├── dijkstra.cpp │ ├── spfa.cpp │ ├── tarjan.cpp │ └── kruskal.cpp ├── dp/ # 动态规划 │ ├── knapsack_01.cpp │ ├── lcs.cpp │ ├── lis.cpp │ └── digit_dp.cpp ├── math/ # 数论与组合 │ ├── pow_fast.cpp │ ├── gcd_ex.cpp │ ├── prime_sieve.cpp │ └── ntt.cpp ├── string/ # 字符串 │ ├── kmp.cpp │ ├── ac_automaton.cpp │ └── manacher.cpp ├── search/ # 搜索 │ ├── dfs.cpp │ ├── bfs.cpp │ └── astar.cpp ├── problems/ # 具体题目题面题解代码数据 │ └── 2024_loading/ │ ├── statement.md │ ├── solution.md │ ├── main.cpp │ └── test/ │ ├── 1.in │ ├── 1.out │ └── 2.in │ └── 2.out └── scripts/ ├── run_all.sh └── judge.py题题分开的好处是显而易见的做题时你只需要进入problems/2024_loading这一个目录题面、题解、代码、样例全部就近放好不需要从外部记忆某个文件叫什么名字。我自己在刷题时最烦的事就是打开题解文章再跳到另一个页面下载数据最终往往是“题解和代码不同步样例还跑不出来”。这份合集的每一个题目目录都是一个自洽的验证单元脚本可以闭着眼跑。2.2 技术选型为什么统一用 C11、单文件、bits/stdc.h分区联赛的评测机生态里C 是绝对主流而 C11 是我认为“代价最小的保守选择”。C17 的结构化绑定、if 初始化虽然很香但老版本 GCC 未必能全量支持C98 又缺了 auto、lambda、priority_queue 的greater等实用特性。C11 足够写出接近现代风格的代码又在所有主流 OJ 上都有较高的兼容率所以整个合集的代码都限制在 C11 语法内。单文件main.cpp也是刻意为之。竞赛代码不需要像工程那样拆一堆.h和.cpp多文件反而带来 include 路径问题。你只需要g -stdc11 -O2 main.cpp -o main就能编译。bits/stdc.h是 GNU 头文件的集合虽然不属于标准库但竞赛评测机几乎都支持省去记忆几十个标准头文件的负担。如果你担心换环境完全可以在本地把templates/io_fast.cpp里的头文件拆成标准版本但这套合集的默认约定就是“只认 GCC”。CXX g CXXFLAGS -stdc11 -O2 -Wall TARGET main build: $(CXX) $(CXXFLAGS) problems/current/main.cpp -o $(TARGET) run: ./$(TARGET) $(INPUT)Makefile 里我习惯把-O2写成固定参数因为它就是评测机常用的优化等级。本地调 bug 时再手动换成-g -O0避免优化行为掩盖真实逻辑问题。-Wall开启编译警告虽然竞赛时代最怕警告刷屏但开发阶段这行能帮你挡住不少低级失误。2.3 命名规则看到文件名就知道考的是哪个算法算法模板的文件名直接采用英文缩写dsu.cpp一眼知道是并查集knapsack_01.cpp一眼知道是 0/1 背包。题目目录则统一用“年份主题词”比如2024_loading表示 2024 年一场模拟赛里的装载问题。这套命名约束比散装文件的“final_version_v2 靠谱得多配合根目录 README 里的索引表找题或者找算法都不需要打开文件看内容。我很推荐你在做二次整理时也保持这个习惯文件夹名可以略长但一定要包含算法或题型的英文关键词。这样以后想复习“树上 DP”时直接到dp/下列出文件而不是靠记忆翻完全部目录。3. 核心模块拆解输入加速、并查集、快速幂与 Dijkstra 的落地写法3.1 统一输入输出模板关掉 cin 和 stdio 的同步减少时间损耗看任何一份竞赛代码最先看的永远是输入输出段。很多选手在本地用 cin 读大数据没问题提交发现超时原因多半是没有关闭 C 标准流与 C 标准流的同步。ios::sync_with_stdio(false)解绑后cin/cout 的速度就能和 scanf/printf 持平代价是你不能再混用 printf 与 cout一旦混用输出顺序会乱。#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]; } cout accumulate(a.begin(), a.end(), 0) \n; return 0; }第一行cin.tie(nullptr)表示 cin 不再绑定 cout。默认情况下 cin 在每一次读入前都会刷新 cout 的缓冲区这会产生大量系统调用数据量大时直接影响运行时间。解除绑定后输出只在程序结束时统一刷新一次。注释里那句“不要混用”是血泪经验我曾经在本地跑得好好的提交后输出全乱排查半天才发现代码里又用了 printf。3.2 数据结构模板并查集和树状数组的工程级写法并查集是分区联赛里出现频率最高的数据结构之一silver 级别的连通性问题基本都在考它。这份合集里的dsu.cpp写法同时实现了路径压缩和按大小合并struct DSU { vectorint fa, sz; DSU(int n) : fa(n 1), sz(n 1, 1) { iota(fa.begin(), fa.end(), 0); } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } bool unite(int a, int b) { a find(a); b find(b); if (a b) return false; if (sz[a] sz[b]) swap(a, b); fa[b] a; sz[a] sz[b]; return true; } };find里的递归赋值就是路径压缩让路径上的每个点直接指向根节点。unite中先比较集合大小把小集合挂到大集合下避免退化成链表。这段代码返回 bool 是刻意的调用者可以通过返回值判断“是否真的发生了合并”在统计连通块数量时特别方便。需要注意的是数组下标从 1 开始开n 1的容量这样输入里编号为 1 的点能直接映射到fa[1]不用每次做减一转换。树状数组模板同样实用它解决的问题是“单点修改 区间查询”。相比线段树树状数组代码短、常数小适合在卡常数的题里使用struct BIT { int n; vectorint bit; BIT(int n) : n(n), bit(n 1, 0) {} void add(int i, int v) { for (; i n; i i -i) bit[i] v; } int sum(int i) { int res 0; for (; i 0; i - i -i) res bit[i]; return res; } int rangeSum(int l, int r) { return sum(r) - sum(l - 1); } };i i -i是树状数组的核心操作i -i取出 i 最低位的 1。更新操作从当前下标向上跳求和操作往下跳。这里用int存和如果题目数据范围超过 2^{31}-1记得把vectorint换成vectorlong long否则溢出后答案会变成负数这种错误很难肉眼发现。3.3 图论与数论模板Dijkstra 与快速幂的正确姿势图论模板里最常用的是堆优化 Dijkstra它用来解决非负权最短路。graph/dijkstra.cpp的实现采用了邻接表加优先队列核心代码如下vectorint dijkstra(const vectorvectorpairint,int g, int s) { int n (int)g.size(); vectorint dist(n, 0x3f3f3f3f); priority_queuepairint,int, vectorpairint,int, greater pq; dist[s] 0; pq.emplace(0, s); while (!pq.empty()) { int d pq.top().first; int u pq.top().second; pq.pop(); if (d ! dist[u]) continue; for (size_t i 0; i g[u].size(); i) { int v g[u][i].first; int w g[u][i].second; if (dist[v] d w) { dist[v] d w; pq.emplace(dist[v], v); } } } return dist; }0x3f3f3f3f是一个常用的“伪无穷大”常量它的十进制值约 10.6 亿两个这样的值相加仍小于 int 的最大值因此可以在松弛运算中安全参与比较。优先队列默认是大根堆通过greater变成小根堆每次弹出距离最小的节点。if (d ! dist[u]) continue;这段跳过了已经过期的节点是性能优化的关键否则同一个节点会被重复松弛多次。数论模块里快速幂是考频最高的模板之一求解a^b % modlong long qpow(long long a, long long b, long long mod) { long long res 1 % mod; while (b) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }res初始化为1 % mod是为了处理mod 1这种极端情况此时任何数对 1 取模都是 0。循环内b 1判断当前二进制位是否为 1如果为 1 就把当前底数乘进结果随后a a * a完成一次平方b 1右移一位等价于不断扫 b 的二进制。这个算法的复杂度是 O(log b)处理 1e18 的指数也只需几十次循环。若模数接近 1e18res * a可能溢出 long long这时需要改成基于加法倍增的快速乘合集里没有默认实现因为分区联赛的模数通常控制在 1e9 量级。4. 题解与代码对照从题目描述到样例输出的一条龙复现流程4.1 题目目录的固定结构每道题都有一条完整证据链problems/下每一道题都是一个自包含目录里面固定包含四个部分statement.md记录题目描述solution.md记录算法思路和复杂度分析main.cpp是可编译的程序test/下放置多组in和out测试数据。这样设计是为了让复盘不需要依赖任何外部上下文所有关键信息都在同一个文件夹里。另一个好处是后文要写的批量测试脚本可以按固定路径扫描不需要解析题目标题或文件名。problems/ └── 2024_loading/ ├── statement.md ├── solution.md ├── main.cpp └── test/ ├── 1.in ├── 1.out ├── 2.in └── 2.out我见过很多选手的题解文件夹最终变成“一堆.cpp加一个乱码的说明.txt”数据放在桌面懒得整理。这份合集从源头把结构定死新加题目时只要复制这个模板填上内容就能跑。statement.md里我习惯附上输入输出格式和样例说明solution.md里除了算法思路还会写“为什么用这个算法”的决策过程这对二次复习帮助极大。4.2 一道典型题目的完整拆解装载问题01背包变种的思考线以2024_loading为例这道题是经典的 01 背包变种有 n 个集装箱要装上一艘载重为 C 的船每个集装箱重量为 w_i要求总重量不超过 C求能装下的最大重量。它等价于“价值等于重量”的 01 背包可以用一维滚动数组求解。solution.md里记录的思路是定义dp[j]表示载重容量为 j 时能装下的最大重量初始化为 0对每个物品倒序枚举容量转移方程为dp[j] max(dp[j], dp[j - w[i]] w[i])。倒序枚举的目的是保证每个物品只被使用一次如果正序枚举就会退化成完全背包。对应的main.cpp是一个可直接编译的完整程序#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, C; cin n C; vectorint w(n); for (int i 0; i n; i) { cin w[i]; } vectorint dp(C 1, 0); for (int i 0; i n; i) { for (int j C; j w[i]; --j) { dp[j] max(dp[j], dp[j - w[i]] w[i]); } } cout dp[C] \n; return 0; }test/1.in的内容是4 10和2 3 5 7预期的1.out是10因为 2 3 5 10正好等于船载重。test/2.in设计了一个无法装满的情形例如3 6和2 2 2输出应为6。这两组数据分别覆盖“刚好装满”和“装不满”两种边界是初学者最容易漏掉的情况。4.3 一键批量验证run_all.sh 守住回归底线手工一个一个跑样例验证太容易漏掉了。合集里准备了一个scripts/run_all.sh它会自动编译problems/下所有main.cpp再逐个运行测试数据并与标准输出比对#!/bin/bash for dir in problems/*/; do if [ -f $dir/main.cpp ]; then g -stdc11 -O2 $dir/main.cpp -o /tmp/solve pass1 for infile in $dir/test/*.in; do base${infile%.in} /tmp/solve $infile /tmp/out if ! diff -q $base.out /tmp/out /dev/null; then echo FAIL: $dir ($(basename $infile)) pass0 break fi done [ $pass -eq 1 ] echo PASS: $dir fi done外层for dir in problems/*/会遍历每一个题目目录-f $dir/main.cpp判断文件是否存在避免扫到还没写完的题目。内层for infile in $dir/test/*.in找出所有输入文件base${infila%.in}去掉.in后缀得到对应的标准输出文件。diff -q只报告文件是否相同不会把大段差异刷屏。/dev/null丢弃 diff 的正常输出我们只需要 FAIL 通知。这个脚本跑一遍大约几秒钟能保证任何模板改动不会静默弄坏已有题目。5. 避坑指南评测机与本地不一致的 5 个高频翻车现场5.1 本地编译通过提交到评测机就 RE现象在 Dev-C 里默认设置编译运行样例全过复制同一份代码到在线评测系统返回 Runtime Error而且没有给出出错行号。原因是本地的编译器版本比较旧越界访问内存时不检查而评测机运行环境栈布局不同越界写坏数据后直接段错误。最常见的是开了长度为 n 的数组但在循环里访问到下标 n数组最后一个合法下标是 n - 1。解决方法是数组从 0 开始分配时把容量定为 n 5给余量使用 vector 时避免operator[]在 debug 阶段用a.at(i)访问vector 越界时会抛出异常并打印定位信息。编译时加上-fsanitizeaddress在本地检测一次能直接暴露所有越界。注意评测机不支持这个参数所以这只是在本地调试的手段。5.2 样例过了却因为多一个空格或换行被判 WA现象输出 n 个整数序列循环里写cout a[i] ;最后一个数后面多了一个空格。本地肉眼看不出来因为样例输出里换行之后没有对比。评测机的判题是字节级完全匹配末尾多余空格也算错。原因就是用循环统一按“数据加分隔符”的方式输出没有考虑最后一项。解决方法是养成固定习惯判断i 0时输出前置空格或者i 1 n时输出换行否则输出空格。更稳妥的做法是先用ostringstream拼出结果最后去掉尾部空格再输出代码量多一点但绝对不会踩坑。5.3 深递归在评测机上段错误本地却一切正常现象DFS 搜索一个网格图递归深度可能达到几千层本地栈空间足够运行完毕提交后有一两个点的错误是段错误。原因是评测机栈空间上限通常小于本地递归层数过深时栈溢出导致程序崩溃。很多选手第一反应是调整编译器栈大小但在 Linux 评测机上#pragma comment(linker, /STACK:...)没有任何效果这是 MSVC 的语法。正确做法是把递归改造成显式栈用stackpairint,int模拟 DFS虽然需要多写几行状态维护但根治了爆栈问题。另一种常见做法是在并查集、树状数组这类不需要深递归的场景里尽量避免递归写法对于边界明确的 DFS可以改用迭代加深或 BFS。5.4 unordered_map 被“定向爆破”成超时现象一道字符串计数题用unordered_mapstring, int统计词频随机数据本地跑得飞快提交后超时。原因是有些特殊构造的字符串会产生大量哈希碰撞导致 unordered_map 从哈希表退化成链表查找复杂度从 O(1) 退到 O(n)。这属于“被定向构造数据坑了”在分区联赛的硬核综合性题目中偶尔出现。解决方法是如果键是整数优先用数组当计数器因为整数范围往往不大如果必须用字符串哈希可以自己写双哈希代替 unordered_map或者干脆用mapstring, int牺牲一点常数换确定性。最极端的情况是我给 unordered_map 传入一个自定义的 hash内部使用随机种子让攻击者无法预知碰撞规则。5.5 全局变量和局部变量同名改了半天找不出 bug现象某道题开了全局数组dp又在某个函数里定义了一个局部变量也叫dp局部初始化成了别的含义函数内外操作的是两个不同的对象。常见的表现是函数内dp数组看起来被赋值了但回到主函数访问dp[0]还是 0。原因很明显变量遮蔽导致逻辑错乱。解决方法是强制规定模板和题解代码一律不允许在局部声明与全局变量同名的数组或结构体凡是需要跨函数使用的状态都放全局凡是局部临时变量用完全不同含义的命名。我在整理代码合集时专门写了一组简单的 lint 规则谁提交的代码里出现同名遮蔽就直接打回。从那以后基本没有因为这种低级问题浪费过调试时间。6. 二次开发把静态合集变成带自动判题的本地训练库6.1 用 judge.py 把样例验证变成一行命令run_all.sh适合验证全部题目但你在开发一道新题时更需要一个针对单一目录的快速判题器。我写了一个scripts/judge.py传入主程序路径和测试数据目录它自动编译、逐组运行、比对输出并给出每个测试点的通过状态#!/usr/bin/env python3 import subprocess from pathlib import Path import sys main, tests sys.argv[1], sys.argv[2] subprocess.run([g, -stdc11, -O2, main, -o, /tmp/solve], checkTrue) for infile in sorted(Path(tests).glob(*.in)): outfile infile.with_suffix(.out) got subprocess.run( [/tmp/solve], stdinopen(infile), textTrue, capture_outputTrue).stdout.strip() expected outfile.read_text().strip() status PASS if got expected else FAIL print(f{infile}: {status}) if status FAIL: sys.exit(1)注意strip()去掉了标准输出两端的空白这样处理可以忽略结尾换行符的差异但不会隐藏中间多余空格。使用方法是进入题目目录后执行python3 ../scripts/judge.py main.cpp test/如果所有样例通过屏幕上会依次输出 PASS否则在第一个 FAIL 处停止。想统计耗时的话可以给subprocess.run加timeout参数把超时判定为 TLE。我给自己定的工作流是把新题收集进problems/后先运行judge.py确认代码正确再运行run_all.sh看一下是否影响旧题。有一回我修改了templates/io_fast.cpp里关闭同步的写法导致三个老题目的输入顺序错乱因为没跑全量回归直到提交到评测机才被数据教训。从那以后我每次改完模板都强制跑一遍全量验证再叠加新功能。这套合集的价值不在代码本身而在于它能让你把每一次“改一改”都变成可验证的工程修改希望帮到你。本文还有配套的精品资源点击获取