简介信息学奥赛一本通C教材的算法与数据结构部分配套题目与测试数据包面向备战信息学奥赛的青少年选手和教练旨在通过大量针对性练习夯实算法思维与编程能力。内容全面覆盖排序、查找、图论、动态规划、回溯、贪心等经典算法也包含数组、链表、栈、队列、二叉树、哈希表、堆、图等结构的训练题可帮助读者在实战中掌握快速排序、二叉树遍历、最短路径、背包问题等核心考点。资源共两千个文件以输入测试数据、输出答案、C与Pascal源程序及标准答案文件为主另有少量说明文档和批处理脚本压缩包大小约六十八兆字节文件命名便于查找定位方便按知识点刷题和自查。目前已有三千一百七十四人学习与下载。这套题目和测试数据既适合日常练习也可作为赛前模拟素材读者能对照标准输出反复调试深化对复杂算法应用场景的理解从而有效提升竞赛水平。1. 信息学奥赛一本通C算法和数据结构题目到底怎么刷才不白费很多自学者拿着一本通啃到「算法和数据结构」这一章就觉得不对劲书上的例题能看懂代码也能抄下来跑通可一合上书自己动手连从哪下手都不知道。更闹心的是网上能找到的题解版本混乱有的只给核心代码不给测试数据你改了输入格式过不了还以为是自己算法写错了。这个标题里说的「题目和测试数据」其实才是这本书最有价值的部分——单看题面只是知道考什么有了测试数据才能验证你的实现对不对、复杂度够不够、边界有没有漏。这篇文章就是把这些题目按算法和数据结构两条线拆开先讲清楚每类题背后的套路再给出怎么组织测试数据、怎么用判题脚本批量验证的完整流程。适合两类人一类是刚学完语法、准备系统刷题冲击 NOIP 入门组或提高组的中学生另一类是带竞赛队的教练想把手里的题目整理成可以反复自测的本地题库。后面所有操作都用 C17 标准写编辑器用 VS Code 配官方 C/C 插件就够。我不会去复述书上的例题解法而是讲这本书没写透的东西题目之间怎么串、测试数据怎么用、踩过的坑有哪些。2. 算法与数据结构两条线先弄清这本书在考什么套路2.1 算法部分的题目结构从暴力枚举到剪枝搜索的递进关系信息学奥赛一本通里算法部分的题目编排不是随机的它基本遵循一条从「会做」到「做得快」的递进线。入门阶段大量题目本质上都是暴力枚举——把所有可能的情况列出来逐个判断。比如求满足某个条件的排列个数、找区间内符合条件的数这类题的数据范围通常控制在 10^6 以内O(n²) 或 O(n·m) 的直写都能过。这时候测试数据的作用是帮你确认枚举的边界起点是 0 还是 1、终点是 n 还是 n-1错了就是典型的 off-by-one。再往上走就是搜索这一块DFS 和 BFS 是重头。书上给的题目很多是迷宫类、连通块类、状态转移类。DFS 题最怕的是递归深度太大爆栈BFS 题最怕的是状态去重没做好导致队列爆炸。这里有个很实用的经验拿到一道搜索题先看数据范围能不能用「二维数组存访问标记」能的话别用 map 或 set 存状态数组的常数小得多。剪枝是算法部分真正的分水岭。一本通里有一批题目专门考这个从 N 个数里选若干个数满足某个条件、把一根绳子切成若干段求最大段长。这类题光靠 DFS 会超时必须加可行性剪枝和最优性剪枝。书上的题解往往直接给出剪枝条件但没告诉你测试数据是怎么设计的——通常最后一个测试点是专门卡你没剪枝的你的代码如果只过了前面几个点、最后一个 TLE别怀疑机器慢大概率就是剪枝不够。我习惯用clock()看单点耗时超过 900ms 就开始怀疑复杂度而不是怀疑评测机。2.2 数据结构部分的经典题栈、队列、树、图各自解决什么问题数据结构板块的题目本质上是考你「用什么容器装数据」。栈的经典题是表达式求值和括号匹配队列的典型题是约瑟夫问题和滑动窗口双端队列则出现在需要两头维护单调性的题目里比如求窗口最大值最小值。这一块刷题时不要纠结于背 STL 接口要养成先画图再写代码的习惯——把数据进出容器的顺序画出来代码基本就错不了。树和图的题就抽象一些。树的题目集中在遍历顺序先序中序后序、二叉树重建、哈夫曼树和堆排序上。图的部分则集中在最短路径Floyd、Dijkstra、最小生成树Prim、Kruskal和拓扑排序上。这里有一个很重要的认知一本通里的图论题数据范围普遍偏小很多用邻接矩阵存图就够了不需要一上来就写链式前向星。等到你开始做提高篇的题目发现邻接矩阵 MLE 了那时候再换邻接表不迟。2.3 排序与 STL 选型什么时候该手写什么时候该直接用库排序在算法部分占了不小的篇幅从冒泡、选择、插入到快排、归并、堆排序。有些初学者会觉得「既然 STL 有 sort 为什么还要手写排序」这个想法在竞赛里其实没问题——绝大多数题目的排序部分直接用std::sort就行它的底层是快排加插入排序的混合最坏情况下也做了防护。但有一类题你必须手写排序要求稳定排序的题比如按成绩排序后按照考号输出std::sort不稳定这时候用std::stable_sort或者手写归并排序。堆排序的手写价值也不在排序本身而在「维护动态最值」这个场景。比如不断插入数据、随时求当前最大值并删除这种题用std::priority_queue是常规做法。书上讲堆排序是为了让你理解优先队列的底层原理但在实际做题时优先队列已经帮你封装好了不需要每次重写。真正要手写堆的是那种需要「删除任意元素」的题目std::priority_queue做不到你需要用 set 或者自己维护一个带位置索引的堆。提示刷题时遇到「超时但思路正确」的情况先观察测试数据里是不是有单调性可以利用。如果数值序列是随机的O(n²) 算法只能过 70% 的点如果题目没有保证随机那出题人大概率故意构造了卡 O(n²) 的数据。3. 把题目和测试数据组织成自己的题库从零搭一套本地评测环境3.1 目录结构与文件命名规范让每题有唯一的身份拿到一本通的题目和测试数据后第一件事不是做题而是把它们整理成规范的目录结构。常见做法是每一道题一个文件夹命名规则用「章节编号-题号-题名」比如3.1-1365-采药。文件夹里放三个东西problem.md用于记题面要点和思路data/放测试数据src/放你的代码。测试数据本身要注意命名规范。大多数 OJ 用的是1.in/1.out这种命名也有用data1.in/data1.out的。你的本地评测脚本要能同时兼容这两种格式否则换一套数据就要改一次脚本。我自己的习惯是检查到数据后先写一个简短的 README 记录每组数据的规模特征1号点是样例、2-4号点是边界小数据、5-8号点是中等随机数据、9-10号点是极限数据。这样调试的时候可以直接定位到对应数据不用每组都跑一遍。mkdir -p 4.2-1375-奶牛晒衣服/src 4.2-1375-奶牛晒衣服/data touch 4.2-1375-奶牛晒衣服/problem.md这段命令创建题目文件夹和子目录。创建完目录后我会在problem.md里先写一段题面的核心逻辑比如「求最小时间使得干衣机辅助下所有衣服变干」然后列出数据范围——这是最关键的信息后面设计算法全靠它。数据范围决定复杂度如果n ≤ 10^5O(n²) 一定超时如果n ≤ 20那大概率可以用状态压缩或直接枚举。3.2 用脚本批量验证代码一次跑完所有测试点题目和数据都齐了之后需要一个批量评测脚本。原理其实很简单把编译好的程序对每个.in文件运行一次把输出和对应的.out文件做逐字节比对一致就 AC否则 WA。这个过程不要手动操作手动比对十几组数据既不现实也容易看走眼。# judge.py - 批量评测当前目录下所有测试点 import subprocess import filecmp import glob import sys import os exe ./main # 编译产物 data_dir ./data # 测试数据目录 cases sorted(glob.glob(os.path.join(data_dir, *.in))) total passed 0 for infile in cases: base os.path.splitext(infile)[0] outfile base .out total 1 runtime 0.0 try: t0 time.time() subprocess.run(exe, stdinopen(infile, r), stdoutopen(tmp.out, w), timeout2000) runtime (time.time() - t0) * 1000 except subprocess.TimeoutExpired: print(fTLE {infile}) continue # 评测结果 if filecmp.cmp(tmp.out, outfile, shallowFalse): print(fAC {infile} {runtime:.0f}ms) passed 1 else: print(fWA {infile} {runtime:.0f}ms) print(f{passed}/{total} passed)这段脚本的核心逻辑很直接glob按文件名排序匹配所有.in文件用subprocess.run执行编译好的程序把输入重定向到文件、输出重定向到临时文件然后用filecmp.cmp做逐字节比较。需要注意脚本开头的timeout参数它管的是单点限时——如果题目没给明确时限我一般设 2000 毫秒跑满还没结束就认为是 TLE。3.3 本地编译命令与 VS Code 任务配置批量评测的前提是你能快速编译出可执行文件。在 VS Code 里配置 C/C 环境时会用一个tasks.json来定义编译任务。命令行直接编的话我推荐带-O2 -stdc17这两个参数——O2 优化在竞赛评测里是标配本地不开 O2 的话有些代码性能表现会差几个档次可能误判为超时。{ version: 2.0.0, tasks: [ { label: build, type: cppbuild, command: g, args: [ -g, -O2, -stdc17, ${file}, -o, main ], group: {kind: build, isDefault: true}, problemMatcher: [$gcc] } ] }这个配置里的-g是为了生成调试信息-O2对标评测机性能-stdc17显式指定标准。很多初学者用 VS Code 默认配置编译时不开 O2结果本地跑 700ms 的数据到了评测机变成 200ms以为自己算法很接近极限了其实差距就是优化选项造成的。编译成功后直接用./main data/1.in tmp.out就能单点测试再跑上面那个 judge 脚本批量验证。4. 测试数据里的坑与排查方法为什么你的代码样例能过、测试全挂4.1 输入格式的隐形要求多组数据、EOF 与空格换行的陷阱一本通系列的题目输入格式上有一个特别容易翻车的点部分题目是多组测试数据直到 EOF 为止而题目描述里并不会特别醒目地标注这一点。常见表现是样例输入里只有一组数据但实际测试数据文件里有三组甚至更多。如果你用单次读取的写法程序读到第二组数据之前就异常退出了评测结果不是 WA 而是 RE 或直接没输出。多组输入的题目代码模板通常长这样int a, b; while (scanf(%d%d, a, b) 2) { // 处理一组数据 printf(%d\n, a b); }scanf的返回值表示成功赋值的变量个数当读到文件末尾时会返回 EOF循环自然结束。如果用while (cin a b)也是等效的。这里的关键是如果题目说「输入包含多行每行两个整数」你几乎可以确定是多组数据别只处理一行就退出。判断方法很简单——如果while循环没法写成「读进两个数就处理」那就要特别小心。行尾的空格和空行是另一个坑。大多数评测系统用的是逐字节比对不会忽略行尾空格和文末换行符。你本地输出看起来和答案「一样」但比对器认为不一样就是 WA。所以输出的时候尽量做到「每行末尾恰好一个换行最后一行也要换行」不要额外输出空格这能免掉大量无意义的返工。4.2 标准输出与错误输出的混淆调试信息混进答案这是我见过最频繁的低级错误在代码里加了一堆cout debug: x来调试顺手跑通了小数据检查输出文件时没发现有多余内容结果拿去批量评测全挂。原因在于这些调试信息混进了标准输出filecmp.cmp一比对自然不一致。解决的办法有两个。硬办法调试信息统一写到cerr这个流默认不参与文件重定向只在终端显示。软办法写代码时把调试输出包在一个宏里交题前全局注释掉。#define DEBUG 1 #if DEBUG #define dbg(x) cerr #x (x) endl #else #define dbg(x) #endif这个宏的思路是dbg(x)在 DEBUG 模式下输出到标准错误流在关闭模式下变成一个空语句编译器优化后没有任何开销。我把这种宏放在自己代码模板的开头每次做一本通的题都用它批量评测前检查一下DEBUG是否为 0。调试信息混进答案这种问题排查一次可能浪费十分钟用这个方式从根上杜绝。4.3 特殊值的边界条件0、负数、最大值与空串测试数据设计时出题人几乎一定会放边界数据但你自己跑样例时可能根本碰不到。整数类型的题要特别注意数据范围里有没有 0、有没有负数和最大值边界。比如求最大子段和初始值设为 0 就是错的——如果所有数都是负数正确答案应该是绝对值最大的那个负数而你输出 0 就 WA 了。这类问题的排查思路是手动构造几组极端数据全负数、全零、全都相等的数组每组都跑一遍看是否符合直觉。链表的题要关注空表的操作树的题要关注只有一个节点的树图论的题要关注只有一个顶点没有边的情况。我在写完代码后有一个习惯先看数据范围然后故意去构造这个范围的上下界数据。如果题目说节点数n ≤ 10^5我就生成一个恰好 10^5 个节点的树来跑这一个测试往往能排查出数组越界和递归爆栈的问题。4.4 算法复杂度被数据卡住时怎么定位最后一个常见问题是 TLE。一个程序在小数据上秒出到了大数据上跑不完这是复杂度超了不是死循环。定位方法比较笨但有效先跑最中间规模的数据比如一共有 10 组数据先跑第 5 组计算运行时间如果明显增大且接近时限再用二分法缩小范围看是从哪一组数据开始变慢的。通过这个方式你能判断出卡你的数据规模大致在什么量级反推算法的实际复杂度。复杂度排查时还有一个容易忽略的点STL 容器在数据量大的时候常数很大。std::map和std::set底层是红黑树单次操作复杂度是 O(log n)但常数是数组的好几倍。如果题目里能用数组解决的问题别用 map 替代——比如标记一个数是否出现过数据范围在 10^7 内就用bool visited[10000005]比unordered_set快得多。这类替换通常能让运行时间从 1900ms 降到 600ms效果显著。5. 进阶用法用对拍脚本验证正确性把一本通当成自己的算法模板库5.1 对拍用暴力程序验证高效程序一本通的测试数据是固定的你过了就是过了。但如果你自己构造了新的测试用例怎么确认答案是正确的这时候需要写一个暴力求解程序——逻辑简单、数据大时会超时但肯定正确——然后用小规模随机数据同时跑暴力程序和高效程序比对输出是否一致。这个流程叫对拍是竞赛选手调试的标配手段。# 对拍脚本随机生成小数据比对暴力解和高效解 import random import subprocess import filecmp def generate(): n random.randint(1, 15) with open(test.in, w) as f: f.write(f{n}\n) for _ in range(n): f.write(f{random.randint(-100, 100)} ) for i in range(1000): generate() subprocess.run(./brute test.in out1, shellTrue) subprocess.run(./fast test.in out2, shellTrue) if not filecmp.cmp(out1, out2, shallowFalse): print(fMismatch case #{i}) break else: print(All OK)这个脚本的核心思路是随机生成小数据分别运行两个程序并比对结果。暴力程序在小数据下也能秒出不会超时。如果两组输出不一致就说明高效程序在某个边界条件下算错了此时test.in就是最小的复现用例可以用来单步调试。注意随机数据生成要覆盖正负数和边界值纯随机有时候生成不了极端情况我会手动往生成逻辑里插入几个固定用例。这样的对拍脚本写好后就不再依赖官方数据的提示了。一本通的题做完后我习惯把高效程序、暴力程序和这个对拍脚本都存在同一个文件夹里以后遇到同类型的题直接复用。5.2 把题目的解法沉淀成模板不是背代码是背适用条件刷完一本通算法和数据结构部分的题最大的收获不是做完了多少道题而是形成了一套自己的模板库。以图论为例Dijkstra 模板、并查集模板、最小生成树模板、拓扑排序模板每个模板对应一个文件。但模板不是背下来的——背代码是最低效的学习方式因为考场上一紧张就会漏细节。我的习惯是给每个模板记录三个东西适用条件、复杂度、容易写错的地方。Dijkstra 模板的适用条件是边权非负复杂度 O((nm)log n)容易写错的是 dist 数组初始化时起点要设为 0、其余设为 INF以及优先队列里存的是 (dist, 节点) 而不是 (节点, dist)——这两者导致的结果完全不同。这些细节单独记下来比抄十遍代码更有用。5.3 从做题到出题反向审视测试数据的构造逻辑当你刷到一定程度官方数据已经不能满足验证需求了可以学着给自己出题换数据。方法是调整数据范围把 n 加大到原题的 10 倍以上看自己的程序能否在时限内跑完。这一个习惯非常重要因为一本通里不少题目的官方数据偏温和真实的竞赛会出更极限的数据。比如排序类的题官方数据可能是 10^5 个随机数你用自己的算法能过但如果换成 10^5 个已经有序的数快排可能退化到 O(n²)这时如果用的是std::sort没事手写的朴素快排就危险了。最后一件事我会定期把刷过的题按算法标签分类统计每个标签下AC的题数。这个统计的价值在于暴露你的薄弱项——如果你发现有连续十几道贪心的题都 WA 了那不是运气问题是这个类型的套路没掌握。找到短板后回到书本再读一遍对应的章节找同类型的题重新验证直到通过率达到目标。这本一道通的价值不在书本身而在于你对待题目和测试数据的方式。希望你也能用这套本地评测的办法把每个知识点刷出自己的体系来。本文还有配套的精品资源点击获取