makedata.h：C++测试数据生成器，覆盖随机数、图、树与字符串

想靠手写样例把一道题的数据造全几乎不可能。随机化测试数据生成是OI出题绕不开的一步但很多初学者第一次尝试时都会卡在怎么写一个顺手的数据生成器上用临时脚本生成几组数据文件路径乱、格式不统一生成完还要手动跑一遍标准程序稍不注意边界就漏了。我一直习惯用C/C写数据生成器后来整理成makedata.h这个头文件库几行代码就能完成随机数、数组、图、树、字符串这类常见数据的生成。这篇文章面向想出题、想给校内训练出模拟赛、或者想给自己的代码做对拍的读者我会把makedata.h的核心用法、设计思路和我在实际出题中踩过的坑一起讲清楚。1. 出题人在生成测试数据时真正需要什么——痛点与目标先聊一个很现实的场景你刚刚写完了题面、确定了一个正解算法和暴力程序正准备把测试数据造出来然后发现手头没有一个顺手的工具。很多人第一反应是拿Python临时写脚本。Python当然能造数据但问题也不少语言运行环境不稳定、随机数种子没有统一管理、数据类型和格式在转存文件时容易出错而且如果一个OI选手要在一个没有Python的评测机环境里再生成数据就很尴尬。C/C数据生成器最大的优势是它可以和你的标程、暴力程序共用同一个编译环境和工具链生成的数据文件格式完全可控性能也足够。另一个更隐蔽的痛点是测试数据的质量比数量重要得多。你随手生成了几十组随机小数结果错误算法也能轻松通过这种数据等于白出。真正有价值的测试数据需要刻意覆盖边界值、极端大小、重复元素、图不连通、树退化成链这类情况而这些恰好是随机数裸生成给不了的东西。makedata.h存在的意义不是帮你多写几行随机数代码而是把造常规数据这件重复劳动压到最低让你把精力花在构造那些真正能卡住错误解法的数据上。所以makedata.h的设计目标可以拆成三条接口足够短一行代码出一类数据生成过程不要占据心智。格式可控能严格控制文件输出格式适配题目输入要求的各种情况。结构可组合边界数据、随机数据、极端数据可以自由混用方便批量生成。1.1 自己写数据生成脚本的尴尬我自己早期造数据时每道题的生成器都从零开始写。随机数要手动处理rand()的分布不均匀、RAND_MAX在Windows和Linux下不一致、想生成一个long long范围的随机数还要自己拼想生成一棵树得先想一个不会出现环的加边策略想生成一个字符串又得单独处理字母范围和长度。这些代码写完之后还有个更麻烦的问题它们没有统一风格。每道题的生成器长得完全不一样等到下一场比赛要改数据时光看自己写的代码都需要好几分钟更不用说复用了。这种经历一多我下定决心把常用操作全部收进一个头文件里取名makedata.h从此所有生成器都以同样的风格写代码量大幅缩水。1.2 makedata.h的设计思路接口统一、开箱即用makedata.h本质上是一个轻量级的“自定义测试数据生成库”。它不是像搜索引擎一样需要联网拉取的大框架而是一个直接放进工作目录就能#include的头文件。它把随机数生成、文件输出、常用数据结构生成三大类操作封装成函数使用者只需要了解接口名和参数含义。为什么用头文件而不是源文件加链接因为生成器场景需要的代码量本身不大如果为了用个随机数还要维护makedata.cpp、写头文件声明、搞编译链接反而违背了简洁的初衷。头文件一旦放好编译器在预处理阶段就把它并进去了每个生成器都是单文件编译做对拍、批量生成时拉起来就跑没有任何多余步骤。另外makedata.h特别强调“随机数可控”。每个函数都允许传入随机数种子不传时用当前时间做种子。这意味着批量生成大批数据时可以全部使用时间种子保证随机性而一旦发现某组数据能把别人的程序卡掉又能立刻用固定种子把这一组精确复现出来。这一点在出题和调试中极其重要后面我会用专门一节讲为什么固定种子是数据生成器的灵魂。2. makedata.h的关键接口与一次生成体验makedata.h在不同人群中流传的版本接口略有差池但核心思路是一致的。下面这套是我自己维护的版本所有命名都很直白你可以直接抄走当模板。2.1 核心接口清单函数名作用典型使用gen(seed)初始化随机种子gen(time(0))或gen(2333)rint(l, r)生成[l, r]范围内的随机整数rint(1, n)rlong(l, r)生成long long范围的随机整数rlong(1e18, 1e18 100)rperm(n, start)生成n个元素的随机排列排列、映射关系rshuffle(vec)将容器内元素随机打乱权值重排rstring(len, charset)按字符集生成随机字符串指定大小写字母/数字rtree(n, flag)生成n个节点的树flag控制是否退化成链树形DP题rgraph(n, m, flag)生成n点m边的图flag控制是否保证连通图论题split()开始写入输入文件配合文件流使用case_end()结束一组数据多组样例时标记输出部分我采用手动控制文件流的方式这样格式可控性最强。核心思路是先生成一个std::ofstream对象指向某个输入文件然后像写cout一样往里写数据。2.2 一个真实例子生成整数序列的数据假设我现在要出一题给定长度为n的整数数组a求最大子段和。输入格式第一行是一个正整数T表示测试组数每组第一行是n第二行n个整数。用makedata.h生成常规随机数据代码如下#include bits/stdc.h #include makedata.h using namespace std; int main() { gen(time(0)); ofstream out(data1.in); int T rint(3, 5); out T \n; for (int t 0; t T; t) { int n rint(1, 10); out n \n; for (int i 0; i n; i) { out rint(-100, 100); if (i 1 n) out ; } out \n; } out.close(); return 0; }这就是最简洁想表达的体感你不需要在生成器里写任何std::mt19937、uniform_int_distribution之类的东西rint帮你处理了分布gen帮你处理了种子剩下的逻辑完全在描述题目输入长什么样。2.3 多组样例输出与文件名约定实际出题时一套数据通常由若干组文件组成命名我习惯用data1.in、data2.in递增编号。多组样例需要特别注意的是T的大小和每组数据的规模要协调。有些题T很大那么单组数据规模就得小有些题单组规模大T就只能是1。我通常把数据规模分成几档小数据n在1到10之间T比较多专门用来卡极端小值。中数据n在1000到10000之间让暴力程序能跑得动。大数据n取题目约束的最大值T取1用于验证正解的时间复杂度。如果一次性要生成20组数据可以在生成器外层加一个循环每次ofstream打开不同的文件名。这样写是完全重复的模板代码我一般会再封装一个make_data(int id, int T, int type)函数内部根据type决定生成策略生成器主函数就只剩一行循环调用。这个习惯省了我大量时间。3. 各种题型数据的生成套路不同题型的输入结构差异很大但仔细观察会发现OI题目常用的数据结构无非是序列、树、图、字符串、矩阵这几大类。makedata.h针对每类都设计了对应的生成方式。3.1 生成数组与区间询问数据序列类问题是最常见的。除了单纯随机填充数组出题人更重要的是构造三类数据单调数据让数组整体递增、递减或先递增后递减。这类数据能卡掉很多只在随机数据上有效、却对单调性处理不佳的算法。生成方式就是for循环里a[i] a[i - 1] rint(0, 5)。重复数据所有元素相同或者只有极少数不同取值。比如把所有a[i]都设成0或1能有效检验程序对相同元素压缩、离散化去重的处理。区间询问类如果是区间和、区间最值这类题询问的构造方式要随机中带一点设计。我常用随机生成l、r的方式但会故意加入一个全区间询问[1, n]和大量小长度询问[x, x]因为这两类边界最容易被线段树或树状数组的边界条件卡住。生成区间询问的典型写法如下void genQuery(int n, int m, ofstream out) { for (int i 0; i m; i) { int type rint(1, 10); int l, r; if (type 2) { // 大约20%的询问覆盖全区间 l 1, r n; } else if (type 4) { // 20%的询问是单点 l rint(1, n), r l; } else { l rint(1, n); r rint(l, n); } out l r \n; } }注意rint(l, n)这里我固定让r不小于l这样生成的询问天然合法不会因为格式错误把选手程序带偏。3.2 图与树的生成生成一棵树是很多初学者容易懵的地方因为他们会本能地想到随机加边然后判环这样写既慢又容易出bug。更简洁的方式是先固定根然后对每个非根节点随机指定一个编号小于自己的节点作为父节点。这样生成的图天然无环且连通n-1条边就是一棵树。void genTree(int n, bool chain, ofstream out) { for (int i 2; i n; i) { int fa; if (chain) fa i - 1; // 退化成链 else fa rint(1, i - 1); // 随机父亲 out fa i \n; // 注意如果有边权在这里追加 rint(1, W) } }chain参数用来控制是否退化成链。链是树形DP题最容易卡递归栈深度的数据如果标程用了非递归写法而选手程序用了递归链数据一测就暴露问题。随机树则用来验证常规情况的正确性。生成图比树麻烦一些因为要避免生成出重边和自环。我简单一点的策略是如果m接近n-1就先生成树再随机补边如果m很大比如接近完全图就用setpairint,int记录已有边随机生成直到数量足够。对于是否保证连通我的经验是在正式数据里至少要保留一组不连通图用于检验选手程序是否假设了图一定连通这种弱假设往往会导致运行时错误。3.3 字符串与特殊边界数据字符串题目里随机串其实是最容易生成的因为只需要一个字符集参数。但出题人真正关心的是特殊模式所有字符都相同、字符串只由两种字符交替出现、字符串的某个前缀是另一个串的循环节。这些模式直接影响字符串哈希、KMP、后缀数组等算法的表现。rstring(len, abc)的封装方式我很喜欢因为它把字符集参数暴露给了使用者。生成随机串之外的变体时我推荐在生成器里单独写一个genSpecialString函数里面可以拼循环节、拼全相同字符串。不要指望一个通用库把所有特殊模式都覆盖到这种特殊数据的构造本来就应该由出题人针对题目思维设计。4. 从能生成到够刁钻边界、强度与去重数据生成的另一半学问在于卡与查。随机数据只能保证你有一堆数据不能保证它们有区分度。一场好的比赛数据必须能筛出错误算法而这个目标靠的是刻意构造。4.1 极限数据与边界值的来源边界值通常来自题目描述里的约束条件。如果n的范围是1 n 1e5那么n1、n2、n1e5、n99999这四组数据几乎是必须的。别小看n1很多程序在n1时会访问不存在的下标或者循环条件出错在n比较大时这些错误反而被掩盖了。权值方面如果a[i]范围是-1e9 a[i] 1e9我会专门构造一组全部等于-1e9的数据和一组全部等于1e9的数据。这样做能暴露两类问题一是最大值累加时是否溢出二是最小值状态初始化是否正确。最大子段和问题经典错误就是初始化ans0导致全负数数据直接输出0这样的数据就是靠全负构造卡出来的。一个我常用的边界数据构造技巧叫平移法先构造一组结构非常整齐的数据比如所有元素随机但在某一个位置塞入一个极大值然后整体加减一个偏移量。这样程序如果对值域范围处理不当就会在边界上栽跟头而题面看起来又足够自然。4.2 固定随机种子与数据复现这一点是我特别想强调的。生成测试数据时的随机种子管理直接决定你的调试效率。最初我图省事每次生成都用gen(time(0))。有一天我用对拍工具发现某组数据能让暴力程序和一个WA的程序结果不一致但因为没有记录当时的种子这组数据无法复现我只能重新大规模跑对拍等它再次出现浪费了将近一小时。后来我把所有gen(time(0))改成了一套编号规则生成第k组数据时用gen(k * 10007 某个固定大质数)。这样只要我记录生成器参数每个数据文件都能根据它的编号精确还原出题复盘时能直接定位是哪组数据出了问题。更严谨一点的做法是给每个数据文件附一个seed.txt内容就是生成该组用到的种子。跟我合作过的命题组小伙伴都逐渐采用了这个习惯它的价值在命题现场debug时简直是救命级的。4.3 数据去重与合法性校验一组数据生成完最怕的是两份输入文件完全一样或者数据内部出现不合法情况。完全一样的两个数据文件会让评测机做很多无用功也可能导致为什么20组数据只有19组有效这种离奇问题。去重最简单的方法是生成后计算每个输入文件的哈希值然后比较所有哈希值是否重复。但这只解决了最表面的问题。更值得投入的是对每个文件跑一遍数据合法性校验程序我通常写一个独立的validator.cpp严格按照题面逐条检查n是否在范围内、a_i是否在范围内、图的边是否有重边自环、字符串长度是否匹配、T与总数据规模是否冲突。校验程序也是用C写的和标程、生成器放在同一个目录里。我见过不少选手和出题人用Python写validator但我的个人体会是校验程序一定要和生成器同语言同风格因为同一个选手对同一种语言的边界处理习惯是一致的这样反而能发现生成器里自以为生成了正确的数据实际输入格式已经越界的问题。5. 生成器与标程组合成出题流水线数据生成只是出题流程的一环。一个完整的出题流水线通常包含数据生成、标准答案生成、数据打包和最终校验四步。makedata.h在这条流水线里承担的是第一环但它的接口设计让后面几环衔接很顺畅。5.1 输入、答案、打包的标准流程我出题时的工作目录一般长这样problem/ ├── makedata.h ├── gen.cpp // 数据生成器 ├── std.cpp // 标准程序 ├── brute.cpp // 暴力程序 ├── validator.cpp // 合法性校验 └── data/ ├── 1.in ├── 1.out └── ...生成数据的流程是运行gen.cpp生成data/1.in到data/20.in。运行validator.cpp逐组检查输入合法性。运行std.cpp将每个.in文件读入结果写入对应的.out文件。用diff或批处理脚本检查.out文件不为空、行数正确然后整体打包成data.zip。标准答案生成这一步很多人直接写成std.cpp内部循环打开20个文件但这样会造成标准程序和评测机上的行为不一致。我更推荐的做法是让std.cpp只读单个文件、输出单个文件然后通过shell循环或Windows批处理逐个调用for i in $(seq 1 20); do ./std data/$i.in data/$i.out done这样做的好处是std.cpp就是你在评测系统上提交的那个版本它与真实测评行为完全一致不会出现本地生成答案和在线评测结果不一致的情况。5.2 对拍场景下的组合用法对拍是我日常调试中使用makedata.h最频繁的场景。流程非常简单先用makedata.h写一个gen.cpp生成一组随机小数据然后同时让std.cpp和待测程序跑这份数据比较输出。对拍数据的生成和正式测试数据的生成有一个重要区别对拍要求数据规模适中既能触发错误又不能让暴力程序跑太慢。我通常让对拍生成器的数据量远小于正式数据比如n在10到20之间图点数在8个左右。因为对拍的核心目标是快速暴露差异而不是压性能。写对拍脚本时我习惯在生成器里强制固定一个时间种子但每轮循环都让n随机变这样既保证每轮数据不同又保留了这轮数据如果出问题下一轮还能复现同一个n的可能。5.3 评测时的数据量控制最后想提醒一个容易踩的坑数据总大小。生成器如果没控制好很容易生成出一份几百MB的输入文件。比如n很大时还生成了m也接近n^2的稠密图文件体积急剧膨胀评测系统可能直接拒收。我的习惯是生成完数据后立刻检查一下du -sh data/如果整体超过50MB就要考虑压缩数据规模或减少数据组数。还有一个技巧是对于超大图数据不一定要把文件写到磁盘再跑答案可以直接让std.cpp从标准输入读取然后用管道把生成器的输出直接送给标准程序这样既节省磁盘空间又加快生成速度。但正式比赛数据还是要落盘因为需要持久化存档。6. 在VSCode里把生成器跑顺手makedata.h本身只是一个头文件但很多OI选手习惯用VSCode写代码而VSCode对C/C的include路径、智能提示和编译任务的配置有一些容易让人卡住的细节。这里我把自己调顺VSCode的经验整理一下尤其是和头文件库相关的部分。6.1 include路径与智能提示优先级#include makedata.h之所以用双引号而不是尖括号是因为双引号会优先在当前文件所在目录查找头文件。这也是为什么makedata.h和gen.cpp放在同一个目录就能直接编译。但VSCode的智能提示IntelliSense默认不一定认识这个头文件。如果不做任何配置打开gen.cpp时makedata.h下面会出现红色波浪线提示找不到源文件。这个问题的核心在于IntelliSense的include路径和编译器实际的include路径并不完全一致。解决办法是在.vscode/c_cpp_properties.json里配置includePath{ configurations: [ { name: Linux, includePath: [ ${workspaceFolder}/** ], defines: [], compilerPath: /usr/bin/g, cStandard: c11, cppStandard: cpp17, intelliSenseMode: linux-gcc-x64 } ], version: 4 }${workspaceFolder}/**表示把工作区下所有目录都纳入搜索范围这样不仅makedata.h能被识别任何子目录下的自定义头文件也都能找到。需要特别注意的是如果你开了多个工作区或者把makedata.h放在了一个不在当前工作区的公共目录里记得把那个目录也加进来。智能提示的路径优先级是当前文件所在目录优先于includePath列表includePath列表的条目从左到右依次查找所以不要把一些无关路径放在前面否则可能出现同名头文件被意外匹配的问题。6.2 结构体成员补全错误的排查很多人在VSCode里写C结构体时会遇到成员补全一直跳错、提示找不到成员名的情况。这个问题和makedata.h未必直接相关但它在写自定义生成器、validator时会频繁出现所以一并说一下。最典型的原因是IntelliSense的缓存没有刷新。当你新增了一个结构体成员或者修改了头文件里的接口VSCode的代码分析器可能还停留在旧缓存上。此时按CtrlShiftP输入C/C: Reset IntelliSense Database重置IntelliSense数据库然后重新加载窗口通常就能解决。第二个原因是C标准设置太低。makedata.h里如果用到了C11之后的特性比如auto、unordered_map、std::shuffle而c_cpp_properties.json里的cppStandard设成了c98智能提示就会出现大量误报。把它改成c17即可。这个设置不影响编译它只影响编辑器的代码分析但分析结果会直接影响你写代码的效率。6.3 tasks.json与编译退出代码最后是编译运行的问题。VSCode的调试和编译高度依赖.vscode/tasks.json我通常把它配置成多任务模式一键编译生成器{ version: 2.0.0, tasks: [ { label: build gen, type: cppbuild, command: /usr/bin/g, args: [ -stdc17, -O2, -Wall, -o, gen, gen.cpp ], group: build, problemMatcher: [$gcc] } ] }写完生成器后按CtrlShiftB执行编译如果编译失败VSCode的问题面板会直接列出错误位置。这里有个小技巧如果编译全部通过但运行时没有任何输出一个常见原因是没有查看程序的退出代码。VSCode终端里运行./gen后如果程序崩溃终端会显示退出码比如exit code 139段错误、exit code 134断言失败。根据退出代码能快速判断问题方向避免在用户输出为空时一头雾水。我曾经遇到过一次非常奇怪的问题生成器单独运行时一切正常但通过VSCode的Run Code插件运行时报退出代码1。排查了半天发现是插件默认工作目录和我的工作目录不一致程序找不到要打开的输出文件路径。解决办法是统一在tasks.json里设置options: {cwd: ${workspaceFolder}}让所有任务都在工作区根目录运行。这类环境问题看起来很小但在多文件出题流程里会浪费大量时间。聊到这里makedata.h能做什么、怎么用、以及搭配VSCode如何跑得顺已经说得很完整了。最后再分享一个我自己的习惯我并没有把makedata.h当成一个不能动的固定库它在我的目录里是持续演进的。每当我发现某种题型的数据构造有共性的模式我就会给它加一个函数并附上简短的注释。几年下来这个头文件从最初的几百行变成了千行级别但每一次扩展都让下一道题的出题工作快一点。你也可以试一试从抄一份核心接口开始把它慢慢变成你自己最顺手的出题工具。