★ FEATURED ARTICLE 简介这份资源是《信息学奥赛一本通C》算法与数据结构部分的配套题目与测试数据合集面向青少年编程学习者及信息学奥赛参赛选手帮助读者在排序、查找、图论、动态规划、回溯、贪心等算法专题以及数组、链表、栈、队列、树、哈希表、堆、图等数据结构知识点上完成系统训练与实战检验。压缩包共收录2000个文件约68.52MB其中1561个.in输入文件与1489个.out输出文件构成完整测试用例182个cpp与175个pas源码提供参考实现另有74个ans答案、44个bat批处理脚本及若干pdf、txt、doc说明文档便于本地自动评测与对照学习。目前已有3174人学习下载适合按章节刷题、验证程序正确性并积累解题经验。1. 从一本通刷到省一算法和数据结构题目到底该怎么练很多刚接触信息学奥赛一本通C的学生第一反应是打开题库按顺序刷刷到第三章发现卡住了回头一看前两章也忘光了。问题不在题量在于这本书的算法和数据结构部分本身是一条有依赖关系的知识链——顺序结构、循环、数组、函数、递归、排序、查找、栈队列、树、图、动态规划每一环都踩在前一环上。你跳着刷等于在沙子上盖楼。这篇文章要解决的就是这件事把一本通里算法和数据结构部分的题目和测试数据拆成一条能落地的训练路径。我会讲清楚每类题该配什么测试数据、怎么自己造数据验证、本地怎么搭一套能跑通编译和对比输出的环境以及哪些章节值得反复刷、哪些可以快速过。适合已经能写基础C语法、准备冲CSP-J/S或NOIP普及组的学生也适合带竞赛班的教练拿去当训练大纲。核心判断只有一个一本通的题目本身不难难的是你没有配套的测试数据去验证边界。很多人写完代码提交看到“答案错误”就懵了因为题目给的样例太弱根本测不出数组越界、整数溢出、递归爆栈这些真实问题。所以这篇的重点不是讲题是讲怎么用测试数据把每道题吃透。2. 一本通算法与数据结构部分的章节依赖关系先刷哪块不会卡2.1 从语法到算法的四个台阶一本通的前几章是语言基础从“顺序结构程序设计”开始到“循环结构”“数组”“函数”“递归”为止这部分属于语法台阶。真正的算法和数据结构部分从“排序”和“查找”开始往后是“栈与队列”“树”“图”“动态规划”。这四个台阶的依赖关系非常明确第一台阶排序与查找。排序是后续几乎所有算法的基础二分查找依赖有序数组贪心依赖排序动态规划的很多状态转移也需要先排序。第二台阶栈、队列、链表。这三个是线性数据结构的核心栈用于表达式求值、括号匹配、DFS的非递归写法队列用于BFS、滑动窗口。第三台阶树与二叉树。二叉树的遍历是递归的经典应用堆是优先队列的实现基础并查集虽然常被归到图里但它的数组实现更像树。第四台阶图与动态规划。图的存储邻接矩阵、邻接表和遍历DFS、BFS是基础最短路、最小生成树、拓扑排序都建立在这上面。动态规划则是前面所有内容的综合区间DP需要排序预处理树形DP需要递归遍历。我一般建议学生按这个顺序刷但有一个例外如果你时间紧排序和查找可以快速过因为C的STL已经提供了sort和lower_bound你只需要理解原理不需要手写快排。但栈和队列必须手写一遍因为竞赛中经常需要手写单调栈、单调队列STL的stack和queue反而不够灵活。2.2 每类题该配什么测试数据一本通自带的测试数据往往只有一两组而且很多是题目描述里的样例。这远远不够。你需要自己造三类数据第一类边界数据。比如数组大小取到题目允许的最大值看会不会超时或爆内存整数取到int的边界看会不会溢出递归深度取到最大看会不会爆栈。第二类随机数据。用随机数生成器造大量测试用例和暴力程序对拍。这是发现逻辑错误最有效的方法。第三类特殊构造数据。比如排序题里造一个已经有序的数组、一个完全逆序的数组、一个所有元素相同的数组图论题里造一个链、一个菊花图、一个完全图。这些数据能暴露算法在特定情况下的退化。下面是一个造随机数据的模板用C写因为一本通本身就是C#include bits/stdc.h using namespace std; int main() { // 设置随机种子用时间保证每次运行不同 srand(time(0)); int n rand() % 1000 1; // 数据规模在1到1000之间 cout n endl; for (int i 0; i n; i) { // 生成1到10000之间的随机整数 cout rand() % 10000 1 ; } cout endl; return 0; }这段代码的逻辑很简单先随机一个数据规模n然后生成n个随机整数。参数说明rand() % 1000 1控制n的范围你可以改成题目要求的最大规模rand() % 10000 1控制每个元素的取值范围如果题目要求负数就改成rand() % 20001 - 10000。注意rand()的最大值是RAND_MAX通常是32767如果你需要更大的随机数要用rand() * rand()或者C11的mt19937。造完数据后你需要一个暴力程序来对拍。比如排序题暴力程序就是直接调用sort你的程序如果是手写快排就对拍验证。对拍脚本用bash写#!/bin/bash # 对拍脚本循环生成数据分别运行两个程序比较输出 for i in $(seq 1 1000); do ./gen data.in # 生成数据 ./my_solution data.in my.out # 运行你的程序 ./brute_force data.in bf.out # 运行暴力程序 if ! diff -q my.out bf.out /dev/null; then echo 发现差异测试数据已保存到 data.in break fi echo 第 $i 组通过 done这个脚本的逻辑是循环1000次每次生成数据、运行两个程序、比较输出。如果发现差异就停下来保留数据供你调试。参数说明seq 1 1000控制对拍次数一般1000次足够发现大部分逻辑错误diff -q只判断文件是否相同不输出具体差异速度快。提示对拍时两个程序必须用同一份输入数据而且暴力程序的逻辑必须绝对正确。如果你不确定暴力程序对不对先拿题目样例测一遍。3. 本地环境搭建与编译调试从VSCode到命令行3.1 VSCode配置C竞赛环境很多学生用Dev-C但那个IDE太老了调试功能弱而且不支持C11以上的特性。我推荐用VSCode配置一次就能一直用。步骤如下第一步安装MinGW-w64编译器。下载后解压到C盘根目录比如C:\mingw64然后把C:\mingw64\bin加到系统环境变量Path里。验证方法打开命令行输入g --version能看到版本号就成功了。第二步安装VSCode然后装三个扩展C/C微软官方、Code Runner、Competitive Programming Helper。C/C扩展提供智能提示和调试Code Runner提供一键运行Competitive Programming Helper提供竞赛常用的代码模板和测试用例管理。第三步配置tasks.json和launch.json。在项目文件夹下新建.vscode文件夹里面放两个文件// tasks.json编译任务 { version: 2.0.0, tasks: [ { label: compile, type: shell, command: g, args: [ -stdc17, // 使用C17标准 -O2, // 开启O2优化竞赛常用 -Wall, // 开启所有警告 -g, // 生成调试信息 ${file}, // 当前文件 -o, // 输出文件 ${fileDirname}/${fileBasenameNoExtension}.exe ], group: { kind: build, isDefault: true } } ] }// launch.json调试配置 { version: 0.2.0, configurations: [ { name: C Debug, type: cppdbg, request: launch, program: ${fileDirname}/${fileBasenameNoExtension}.exe, args: [], stopAtEntry: false, cwd: ${fileDirname}, environment: [], externalConsole: true, // 使用外部控制台方便输入 MIMode: gdb, miDebuggerPath: C:/mingw64/bin/gdb.exe, preLaunchTask: compile } ] }参数说明-stdc17指定C标准一本通的部分题目可能要求C98但竞赛现在普遍用C14或C17-O2是竞赛常用的优化级别能显著提升运行速度-Wall开启警告能帮你发现未初始化变量、类型不匹配等问题-g生成调试信息配合gdb使用。3.2 命令行编译与手动测试VSCode虽然方便但有时候你需要快速编译一个文件用命令行更快。基本命令# 编译单个文件 g -stdc17 -O2 -Wall -o solution solution.cpp # 运行并手动输入测试数据 ./solution # 用文件重定向输入输出 ./solution input.txt output.txt # 比较两个输出文件 diff output.txt expected.txt如果你在Windows上把./solution换成solution.exe。是输入重定向是输出重定向这两个符号在竞赛中非常常用因为你可以把测试数据存成文件不用每次手动输入。手动测试时我习惯用echo管道快速输入echo 5 3 1 4 1 5 | ./solution这行命令把两行输入通过管道传给程序适合快速验证样例。注意echo后面的字符串里\n要写成实际换行或者用$...语法。注意如果你在Windows的PowerShell里管道和重定向的语法略有不同建议用cmd或者Git Bash。另外diff命令在Windows上可能没有可以用fc代替或者装一个Git Bash。3.3 用gdb调试递归和数组越界一本通的递归题和数组题最容易出问题。递归爆栈时程序会直接崩溃没有任何输出数组越界时可能读到垃圾值导致结果莫名其妙。这两种情况用gdb都能快速定位。编译时加-g然后运行gdb ./solution。常用命令run运行程序可以带参数比如run input.txtbt查看调用栈递归爆栈时能看到重复的栈帧p variable打印变量的值break line_number在某一行设断点next单步执行不进入函数step单步执行进入函数continue继续运行到下一个断点比如你怀疑数组越界可以在访问数组的地方设断点然后打印下标(gdb) break solution.cpp:15 (gdb) run (gdb) p i (gdb) p arr[i]如果i超出了数组范围gdb会显示Cannot access memory at address...你就知道问题在哪了。递归爆栈的典型表现是bt输出大量重复的栈帧而且栈帧的地址越来越小。这时候你需要检查递归的终止条件是否正确或者把递归改成迭代。一本通里有些题目的递归深度可能达到10万层默认栈大小只有1MB左右肯定会爆。解决办法是在编译时加-Wl,--stack67108864把栈大小改成64MBg -stdc17 -O2 -Wl,--stack67108864 -o solution solution.cpp这个参数在Windows的MinGW上有效Linux下用ulimit -s命令调整。4. 排序、查找、栈队列的测试数据构造与对拍4.1 排序题的六类测试数据一本通的排序章节包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序。每学一种排序你都需要用同一组测试数据去验证。我一般准备六类数据第一类随机数据。规模从10到100000元素范围从1到1000000。这是基本测试。第二类已排序数据。元素已经升序排列。这对冒泡排序和插入排序是最好情况对快速排序是最坏情况如果基准选第一个元素。第三类逆序数据。元素降序排列。这对冒泡排序和插入排序是最坏情况对快速排序也是坏情况。第四类所有元素相同。这能暴露快速排序的分区问题如果分区不当会退化成O(n^2)。第五类大量重复元素。比如只有1和2两种值但数量各占一半。这能测试三路快排或者计数排序。第六类极端规模。n取到题目允许的最大值比如1000000看会不会超时。下面是一个生成这六类数据的脚本#include bits/stdc.h using namespace std; int main(int argc, char* argv[]) { int type atoi(argv[1]); // 从命令行参数获取数据类型 int n atoi(argv[2]); // 数据规模 srand(time(0)); if (type 1) { // 随机数据 for (int i 0; i n; i) cout rand() % 1000000 1 ; } else if (type 2) { // 已排序 for (int i 1; i n; i) cout i ; } else if (type 3) { // 逆序 for (int i n; i 1; i--) cout i ; } else if (type 4) { // 全部相同 for (int i 0; i n; i) cout 42 ; } else if (type 5) { // 大量重复 for (int i 0; i n; i) cout (i % 2) 1 ; } else if (type 6) { // 极端规模随机 for (int i 0; i n; i) cout rand() % 1000000 1 ; } cout endl; return 0; }编译后用./gen 1 100000 data1.in生成第一类数据以此类推。参数说明type控制数据类型n控制规模。注意atoi把字符串转成整数所以运行时必须带两个参数。生成数据后用你的排序程序和std::sort对拍。对拍脚本前面已经给过这里不再重复。重点观察你的快排在已排序数据上是否超时你的堆排序在大量重复数据上是否正确你的归并排序在极端规模下是否爆内存4.2 二分查找的边界测试二分查找看起来简单但边界条件极其容易写错。一本通的二分查找题目通常要求在一个有序数组中查找第一个大于等于x的元素或者最后一个小于等于x的元素。这两种变体的边界处理不同。测试二分查找你需要构造以下数据查找值小于数组最小值查找值大于数组最大值查找值等于数组最小值查找值等于数组最大值查找值在数组中间但不存在数组中有多个相同的查找值下面是一个测试模板#include bits/stdc.h using namespace std; int main() { vectorint arr {1, 3, 3, 3, 5, 7, 9}; vectorint queries {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; for (int x : queries) { // 查找第一个大于等于x的位置 int pos lower_bound(arr.begin(), arr.end(), x) - arr.begin(); cout x x lower_bound pos; if (pos arr.size()) cout arr[pos] arr[pos]; cout endl; } return 0; }运行后观察输出确认每个查询的结果符合预期。参数说明lower_bound返回第一个大于等于x的迭代器减去begin()得到下标如果所有元素都小于x返回arr.size()。upper_bound类似返回第一个大于x的位置。提示手写二分时循环条件用while (left right)还是while (left right)取决于你的区间定义。左闭右闭区间用前者左闭右开区间用后者。混用会导致死循环或漏查。4.3 栈和队列的模拟测试一本通的栈和队列题目包括括号匹配、表达式求值、滑动窗口最大值、迷宫最短路。这些题目的测试数据需要覆盖空栈/空队列的操作栈满/队列满的情况如果用数组模拟连续多次入栈后一次性出栈入栈和出栈交替进行以括号匹配为例测试数据要包括空字符串、只有左括号、只有右括号、左右括号数量相等但顺序错误、嵌套多层括号、括号类型不匹配。下面是一个生成括号序列的代码#include bits/stdc.h using namespace std; int main() { srand(time(0)); int n rand() % 20 1; // 括号对数1到20 string s; for (int i 0; i n; i) { // 随机生成左括号或右括号 if (rand() % 2 0) s (; else s ); } cout s endl; return 0; }这段代码生成的括号序列不保证合法正好用来测试你的程序是否能正确判断非法情况。参数说明n控制括号总数rand() % 2决定生成左括号还是右括号。如果你需要生成合法括号序列可以用递归或者卡特兰数构造。对拍时暴力程序可以用一个简单的栈模拟bool isValid(string s) { stackchar st; for (char c : s) { if (c () st.push(c); else { if (st.empty()) return false; st.pop(); } } return st.empty(); }这个暴力程序逻辑简单不容易写错适合作为对拍基准。5. 树、图、动态规划的测试数据与常见翻车点5.1 二叉树的遍历测试一本通的二叉树题目通常要求给出前序和中序求后序或者给出后序和中序求前序。测试数据要覆盖只有一个节点只有左子树只有右子树完全二叉树斜树每个节点只有左孩子或只有右孩子随机二叉树生成随机二叉树的代码#include bits/stdc.h using namespace std; struct Node { int val; Node *left, *right; Node(int v) : val(v), left(nullptr), right(nullptr) {} }; // 随机插入节点 Node* insert(Node* root, int val) { if (!root) return new Node(val); if (rand() % 2 0) root-left insert(root-left, val); else root-right insert(root-right, val); return root; } // 前序遍历 void preorder(Node* root, vectorint res) { if (!root) return; res.push_back(root-val); preorder(root-left, res); preorder(root-right, res); } // 中序遍历 void inorder(Node* root, vectorint res) { if (!root) return; inorder(root-left, res); res.push_back(root-val); inorder(root-right, res); } int main() { srand(time(0)); Node* root nullptr; int n rand() % 10 1; for (int i 1; i n; i) { root insert(root, i); } vectorint pre, in; preorder(root, pre); inorder(root, in); for (int x : pre) cout x ; cout endl; for (int x : in) cout x ; cout endl; return 0; }这段代码生成一棵随机二叉树输出前序和中序。参数说明insert函数随机选择左子树或右子树插入所以生成的树形状随机n控制节点数量。你可以用这个输出作为测试数据然后写一个程序根据前序和中序重建二叉树再输出后序验证是否和原始树的后序一致。5.2 图的存储与遍历测试一本通的图论题目从邻接矩阵和邻接表开始然后是DFS、BFS、最短路、最小生成树。测试数据要覆盖孤立节点没有边自环节点到自己的边重边两个节点之间多条边不连通图完全图链状图菊花图一个中心节点连接所有其他节点生成随机图的代码#include bits/stdc.h using namespace std; int main() { srand(time(0)); int n rand() % 10 1; // 节点数1到10 int m rand() % (n * (n - 1) / 2 1); // 边数不超过完全图 cout n m endl; setpairint,int edges; for (int i 0; i m; i) { int u rand() % n 1; int v rand() % n 1; if (u v) continue; // 避免自环 if (u v) swap(u, v); // 避免重边 if (edges.count({u, v})) continue; edges.insert({u, v}); cout u v endl; } return 0; }这段代码生成一个无向图节点编号从1到n边不重复、不自环。参数说明n控制节点数m控制边数set用来去重。注意这个生成器可能生成的边数少于m因为去重后有些边被跳过了。如果你需要精确的边数可以用一个循环直到生成m条边。对拍时DFS和BFS的暴力程序可以用递归和队列分别实现然后比较遍历序列是否一致。最短路题目可以用Floyd算法作为暴力程序因为Floyd写起来简单不容易错。5.3 动态规划的边界与对拍动态规划是一本通里最容易翻车的部分。状态定义错了、转移方程漏了、初始化不对、边界没处理都会导致答案错误。测试数据要覆盖最小规模n1最大规模n取题目上限所有元素相同元素递增元素递减随机数据以最长上升子序列LIS为例暴力程序可以用O(n^2)的DPint lis_brute(vectorint arr) { int n arr.size(); vectorint dp(n, 1); int ans 1; for (int i 1; i n; i) { for (int j 0; j i; j) { if (arr[j] arr[i]) { dp[i] max(dp[i], dp[j] 1); } } ans max(ans, dp[i]); } return ans; }你的程序如果是O(n log n)的贪心二分就用这个暴力程序对拍。参数说明dp[i]表示以arr[i]结尾的最长上升子序列长度初始化为1转移时遍历所有j i如果arr[j] arr[i]就更新。这个暴力程序的时间复杂度是O(n^2)n取1000左右对拍足够。注意对拍时如果暴力程序超时就减小数据规模。对拍的目的是验证正确性不是测试性能。性能测试用最大规模数据单独跑。5.4 常见翻车点排查现象程序在本地运行正确提交后答案错误。 原因本地编译器可能没有开启O2优化或者C标准不同。一本通的部分题目对整数溢出敏感本地int是32位提交环境可能也是32位但如果你用了long long而本地没测出来提交后可能因为格式化输出错误。 解决提交前用-O2 -stdc17重新编译并且用最大规模数据测试。输出long long用%lld不要用%d。现象递归程序在本地能跑提交后运行时错误。 原因提交环境的栈空间比本地小递归深度过大导致爆栈。 解决把递归改成迭代或者用-Wl,--stack67108864编译如果提交环境支持。更稳妥的做法是手动用栈模拟递归。现象数组越界但程序不崩溃结果莫名其妙。 原因C不检查数组越界越界读写可能覆盖其他变量的值。 解决把数组大小开大10个元素并且在访问前检查下标。用vector的at()方法可以在越界时抛出异常但竞赛中一般不用因为性能损失。现象二分查找死循环。 原因left和right的更新方式不匹配循环条件。比如while (left right)时如果right mid而不是mid - 1可能死循环。 解决统一区间定义。左闭右闭用while (left right)更新left mid 1或right mid - 1左闭右开用while (left right)更新left mid 1或right mid。现象动态规划答案偏小。 原因初始化不对。比如求最大值时dp数组初始化为0但有些状态应该是负无穷。 解决根据题目含义初始化。求最大值初始化为-INF求最小值初始化为INF计数问题初始化为0。dp[0]通常需要单独处理。6. 用对拍脚本把一本通题目刷成肌肉记忆对拍不是万能的但没有对拍是万万不能的。我带学生刷一本通时要求每道算法题都必须写对拍脚本而且对拍通过1000组以上才算过。这个习惯一旦养成比赛时你会本能地先写暴力程序再用对拍验证正解而不是凭感觉提交。对拍脚本可以写成一个通用模板放在~/oi/目录下每次新建题目文件夹时复制过去。模板长这样#!/bin/bash # 通用对拍脚本用法./duipai.sh 生成器 你的程序 暴力程序 GEN$1 SOL$2 BRUTE$3 for i in $(seq 1 1000); do ./$GEN data.in ./$SOL data.in sol.out ./$BRUTE data.in brute.out if ! diff -q sol.out brute.out /dev/null; then echo 第 $i 组数据发现差异已保存到 data.in echo 你的输出 cat sol.out echo 暴力输出 cat brute.out exit 1 fi done echo 全部1000组通过参数说明$1、$2、$3分别是生成器、你的程序、暴力程序的可执行文件名。运行时用./duipai.sh gen solution brute。注意所有程序都要提前编译好而且生成器要接受命令行参数或者从标准输入读取规模。进阶用法把对拍和随机种子结合。生成器里用argv[1]作为随机种子对拍脚本循环时传入不同的种子这样能覆盖更多情况// 生成器接受种子作为参数 int main(int argc, char* argv[]) { int seed atoi(argv[1]); srand(seed); // ... 生成数据 }对拍脚本改成for i in $(seq 1 1000); do ./$GEN $i data.in # ... 其余不变 done这样每次生成的随机数据都不同而且可以复现——如果第500组出错你直接用./gen 500就能重新生成那组数据。我自己的习惯是每道题建一个文件夹里面放solution.cpp、brute.cpp、gen.cpp、duipai.sh、data.in。刷完一道题文件夹保留期末复习时直接重新对拍一遍比看笔记有用得多。这个习惯坚持了三年从普及组到提高组对拍救了我至少十次——每次都是我以为自己写对了结果对拍跑出差异才发现边界条件漏了。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
