Testlib 0.9.35 数据生成实战5分钟构建10组OI标准测试点附CYaRon示例在算法竞赛的题目设计中测试数据的质量直接影响着题目的区分度和公平性。一套好的测试数据应当全面覆盖各种边界情况、极端数据和随机场景而手动构造这些数据往往耗时耗力。本文将深入介绍如何利用Testlib 0.9.35这一专业工具快速生成符合OI/ACM竞赛标准的高质量测试数据。1. Testlib工具链概述与环境配置Testlib是由Mike MirzayanovCodeforces创始人开发的竞赛工具库最初作为Polygon系统的核心组件现已广泛应用于各类编程竞赛的数据生成与校验。其0.9.35版本在保持稳定性的同时提供了更丰富的随机数生成器和数据构造API。安装Testlib只需三个步骤wget https://raw.githubusercontent.com/MikeMirzayanov/testlib/master/testlib.h g -stdc11 -O2 -I. -o generator generator.cpp关键组件说明随机数系统支持固定种子复现、权重分布、非均匀分布等数据生成器提供图论、字符串、几何等数据结构生成校验器可验证输入数据合法性交互器用于实现交互题评测推荐开发环境配置# 基础工具链 sudo apt install g make python3 -y # 验证工具 pip3 install githttps://github.com/ouuan/validate-by-example2. 基础数据生成模式与实践Testlib提供了多种数据生成模式我们先从一个简单的整数序列生成器开始#include testlib.h #include vector using namespace std; int main(int argc, char* argv[]) { registerGen(argc, argv, 1); int n optint(n); int min_val optint(min); int max_val optint(max); vectorint a(n); for (auto x : a) { x rnd.next(min_val, max_val); } println(n); println(a); }编译运行g -stdc11 -O2 -I. -o int_gen int_gen.cpp ./int_gen -n 100 -min 1 -max 1e9 test1.in常见参数对照表参数类型示例说明固定值-n100直接指定参数值范围随机-min1 -max1e6在范围内均匀随机权重分布-typeweighted按预设概率分布生成递增序列-orderinc生成单调递增序列唯一值-uniquetrue确保所有元素唯一进阶技巧使用rnd.wnext()实现非均匀分布// 生成偏向小值的随机数 int x rnd.wnext(1, 100000, -5); // 生成偏向大值的随机数 int y rnd.wnext(1, 100000, 5);3. 复杂数据结构生成方案对于树形结构的生成Testlib提供了多种建树方式void gen_tree(int n, int diameter -1) { if (diameter -1) { // 随机树 println(n); for (int i 2; i n; i) { println(rnd.next(1, i-1), i); } } else { // 控制直径的树 vectorint path(diameter 1); iota(path.begin(), path.end(), 1); for (int i diameter 2; i n; i) { int parent rnd.next(1, i-1); println(parent, i); } } }图数据生成示例含重边和自环void gen_graph(int n, int m, bool allow_multi false, bool allow_loop false) { setpairint,int edges; while (edges.size() m) { int u rnd.next(1, n); int v rnd.next(1, n); if (!allow_loop u v) continue; if (!allow_multi edges.count({u, v})) continue; edges.insert({u, v}); edges.insert({v, u}); // 无向图 } println(n, m); for (auto [u, v] : edges) { println(u, v); } }特殊数据结构生成技巧分块数据先构造极端情况再填充随机数据// 前半部分为极值后半部分随机 for (int i 0; i n/2; i) a[i] MAX_VAL; for (int i n/2; i n; i) a[i] rnd.next(1, MAX_VAL);阶梯型数据模拟特定算法的最坏情况// 生成快速排序的最坏情况输入 for (int i 0; i n; i) { a[i] (i % 2 0) ? (n/2 i/2) : (n/2 - i/2); }4. CYaRon集成与批量生成CYaRonYet Another Random Olympic-iNformatics test data generator是基于Testlib的高级封装特别适合OI赛题的数据生成。下面是一个完整的CYaRon示例from cyaron import * def generate(): test_data IO(file_prefixtest, data_id1) n 100000 graph Graph.graph(n, n, weight_limit1000) test_data.input_writeln(n) for edge in graph.iterate_edges(): test_data.input_writeln(edge.start, edge.end, edge.weight) test_data.output_gen(std.exe) if __name__ __main__: for i in range(1, 11): generate() print(fGenerated test case {i})常用CYaRon组件对比组件名称功能描述典型应用场景Graph生成各类图结构图论算法测试Sequence生成序列数据排序、搜索算法测试String生成字符串数据字符串算法测试Geometry生成几何图形数据计算几何题目测试Compare自定义校验器特殊评判需求批量生成脚本示例生成10组测试数据#!/bin/bash for i in {1..10}; do g -stdc11 -O2 gen_$i.cpp -o gen_$i ./gen_$i test$i.in ./std test$i.in test$i.out done5. 实战案例全功能数据生成器下面我们实现一个完整的数据生成器支持多种生成模式#include testlib.h #include vector #include algorithm using namespace std; enum GenType { RANDOM, INCREASING, DECREASING, SPARSE, DENSE }; vectorint gen_array(int n, int min_val, int max_val, GenType type) { vectorint res(n); switch (type) { case RANDOM: for (auto x : res) x rnd.next(min_val, max_val); break; case INCREASING: for (auto x : res) x rnd.next(min_val, max_val); sort(res.begin(), res.end()); break; case DECREASING: for (auto x : res) x rnd.next(min_val, max_val); sort(res.rbegin(), res.rend()); break; case SPARSE: for (auto x : res) { if (rnd.next(0, 9) 7) x 0; else x rnd.next(min_val, max_val); } break; case DENSE: for (auto x : res) { if (rnd.next(0, 9) 3) x 0; else x rnd.next(min_val, max_val); } break; } return res; } int main(int argc, char* argv[]) { registerGen(argc, argv, 1); int n optint(n); int min_val optint(min); int max_val optint(max); string type_str optstring(type); GenType type RANDOM; if (type_str inc) type INCREASING; else if (type_str dec) type DECREASING; else if (type_str sparse) type SPARSE; else if (type_str dense) type DENSE; auto a gen_array(n, min_val, max_val, type); println(n); println(a); }使用方式# 生成随机数据 ./generator -n 100000 -min 1 -max 1e9 -type random random.in # 生成递增序列 ./generator -n 100000 -min 1 -max 1e9 -type inc inc.in # 生成稀疏数据 ./generator -n 100000 -min 1 -max 1e9 -type sparse sparse.in性能优化技巧使用reserve()预分配容器空间批量输出代替逐行输出对于超大规模数据考虑分块生成使用rnd.next()的批量版本生成多个随机数// 高效生成百万级随机数 vectorint nums(1e6); rnd.fill(nums.begin(), nums.end(), 1, 1e9);通过以上方法和技巧我们可以快速构建出覆盖各种边界情况的高质量测试数据显著提升算法题目的测试覆盖率。在实际使用中建议将生成器与校验器、标程一起纳入持续集成系统确保每次修改后数据的正确性和多样性。