别再手动造数据了！用Polygon的testlib.h和脚本批量生成Codeforces题目测试点
高效生成Codeforces测试数据：Polygon平台自动化实践指南
在算法竞赛题目设计过程中，测试数据的质量直接决定了题目的可靠性和公平性。传统手动构造测试用例的方式不仅耗时耗力，还难以保证覆盖各种边界情况。Polygon平台作为Codeforces官方推荐的出题系统，提供了强大的testlib.h库和脚本化工具链，让测试数据生成实现工业级自动化成为可能。
1. 理解testlib.h的核心功能
testlib.h是Polygon平台内置的随机数据生成库，它提供了丰富的API来生成各类符合竞赛需求的测试数据。与标准库的rand()函数不同，testlib的随机数生成器具有以下关键特性：
- 可复现性：相同的种子必然产生相同序列的随机数
- 跨平台一致性：在不同操作系统下生成结果保持一致
- 类型丰富：支持整数、浮点数、字符串、图结构等复杂类型的生成
基础随机数生成示例：
#include "testlib.h" int main(int argc, char* argv[]) { registerGen(argc, argv, 1); // 初始化生成器 // 生成[1,100]范围内的整数 int n = rnd.next(1, 100); // 生成[0.0,1.0]范围内的浮点数 double p = rnd.next(0.0, 1.0); // 生成10-20个字符的小写字母字符串 string s = rnd.next("[a-z]{10,20}"); }1.1 高级数据生成技巧
对于复杂数据结构，testlib提供了专门的生成函数：
| 数据结构 | 生成方法 | 参数说明 |
|---|---|---|
| 树 | rnd.tree() | 可指定节点数和是否加权 |
| 图 | rnd.graph() | 控制边数、连通性等属性 |
| 排列 | rnd.perm() | 生成随机排列 |
| 分区 | rnd.partition() | 将数分解为若干整数和 |
生成加权图的示例代码：
// 生成10个节点、15条边的连通图，边权范围[1,1000] auto graph = rnd.graph(10, 15, true, 1, 1000);2. 构建健壮的generator.cpp
一个专业级的generator应该具备以下特点：
- 参数化输入：通过命令行参数控制生成逻辑
- 模块化设计：不同函数负责不同数据特征的生成
- 异常处理：确保生成的任何数据都符合题目约束
2.1 参数化设计模式
推荐采用工厂模式组织generator代码：
// 定义不同生成模式 enum GenMode { NORMAL, MAX_CASE, CORNER_CASE }; GenMode parseMode(const string& arg) { if (arg == "max") return MAX_CASE; if (arg == "corner") return CORNER_CASE; return NORMAL; } int main(int argc, char* argv[]) { registerGen(argc, argv, 1); // 解析命令行参数 GenMode mode = parseMode(argv[1]); int n = opt<int>(2); // 获取第二个参数转为整数 switch(mode) { case NORMAL: generateNormal(n); break; case MAX_CASE: generateMax(n); break; case CORNER_CASE: generateCorner(n); break; } }2.2 边界情况生成策略
针对常见边界情况，可以预定义生成模板：
极值测试：
- 最大/最小输入规模
- 数据范围边界值
特殊结构测试：
- 完全二叉树/链状树
- 稠密图/稀疏图
- 全相同元素序列
极端分布测试：
- 升序/降序序列
- 所有元素相同
- 严格交替序列
生成极端测试数据的示例：
void generateMax(int n) { cout << n << endl; // 生成全是最大值的数据 for (int i = 0; i < n; i++) { cout << 1000000000 << (i == n-1 ? "\n" : " "); } }3. Polygon脚本自动化流程
Polygon提供了强大的脚本系统，可以批量执行generator并管理测试用例。脚本使用简单的类Shell语法，支持循环、条件等控制结构。
3.1 基础脚本编写
典型脚本结构包含以下部分：
# 清空现有测试 tests = [] # 生成10组常规测试 :loop 10 gen normal {test_index} > $ tests.append($) :endloop # 生成边界测试 gen max 100000 > $ tests.append($) # 设置第一个测试为样例 example tests[0]3.2 高级脚本技巧
动态参数传递：
:for i in 1..10 gen dynamic {$i*1000} > $ tests.append($) :endfor测试依赖管理：
# 先生成输入文件 gen input 100 > input.txt # 使用输入文件生成输出 solution output < input.txt > output.txt条件生成逻辑：
:if {$test_index % 2 == 0} gen even_case > $ :else gen odd_case > $ :endif
4. 测试数据质量验证体系
高质量测试数据需要系统化的验证方法，推荐采用分层检查策略：
4.1 静态检查清单
| 检查项 | 实现方法 | 自动化程度 |
|---|---|---|
| 格式合规 | testlib的validator | 全自动 |
| 边界覆盖 | 专用corner case生成器 | 半自动 |
| 规模合规 | 脚本检查文件大小 | 全自动 |
| 多样性 | 哈希值比对 | 全自动 |
4.2 动态验证技术
暴力验证法：
#!/bin/bash for test in tests/*.in; do brute_solution < $test > expected.out main_solution < $test > actual.out diff expected.out actual.out || echo "Failed on $test" done模糊测试技术：
// 随机修改输入数据的某些部分 void fuzzTest(string inputFile) { auto data = readFile(inputFile); for (int i = 0; i < 100; i++) { auto fuzzed = randomMutation(data); testSolution(fuzzed); } }性能基准测试：
# 测量各测试用例的执行时间分布 import time for test in tests: start = time.time() run_solution(test) duration = time.time() - start log_performance(test, duration)
在实际项目中，我通常会建立三级验证体系：首轮用validator检查基本格式，次轮用暴力法验证正确性，最后用模糊测试寻找边缘情况。这套组合拳下来，能发现90%以上的潜在数据问题。