前言

testlib 是一款由 Mike Mirzayanov 开发的开源项目。本家在这里 -> https://github.com/MikeMirzayanov/testlib。

OI-Wiki 上对于此已经有不少介绍了，我并不觉得我能写得更好。

因为 testlib 可以保证生成的数据在不同环境上一样，我推荐大家使用它造数据。

以下大部分是 AI-generated Text。

命令行参数

通常来说，我们在 OI 中会使用如下方式声明主函数：

int main();

不过，编写 testlib 程序时，我们一般用这种方式声明：

int main(int argc, char** argv);

其中 argc 表示命令行参数的数量，argv 即为命令行参数。 argv 下标从 0 开始。

读者可以尝试使用这个程序自己探究一下 argc 和 argv 中存在什么东西。

#include <iostream>

int main(int argc, char** argv) {
    using namespace std;
    cout << "argc = " << argc << endl;
    for(int i = 0; i < argc; i++)
        cout << argv[i] << endl; 
    return 0;
}

如果你在 Windows 中这样调用这个程序：

test.exe argv[1] argv[2] argv[3]

你应该得到这样的输出：

argc = 4
test.exe
argv[1]
argv[2]
argv[3]

另外，testlib 具有解析命令行参数的功能，使用 opt 函数。

#include "testlib.h"

int main(int argc, char** argv) {
    using namespace std;
    registerGen(argc, argv, 1);
    string filename = opt(1);
    // 下面这是不行的
    // const char* filename = opt<char*>(1);
    long long n = opt<long long>(2);
    int k = opt<int>("k");
    bool is_full_t = opt<bool>("using-fullt");
    double maxv = opt<double>("R");
    printf("Destination = %s,\n"
           "n = %lld, k = %d,\n"
           "maxv = %f\n",
           filename.c_str(), n, k, maxv);
    if (is_full_t)
        printf("Using Full T\n");
    return 0;
}

如果你这样执行此程序：

./OI_Project_main fc2.in 161 -k8 -R=154.25 --using-fullt

应该会产生这样的输出：

Destination = fc2.in,
n = 161, k = 8,
maxv = 154.250000
Using Full T

opt 支持按编号读取，也支持按名字读取。命名参数常见的写法有：

• --key=value 或 -key=value；
• --key value 或 -key value；
• --k12345 或 -k12345（键 k 只有一个字母，后面直接接数字）；
• -prop 或 --prop 表示开启一个布尔参数。

当前版本的 testlib 还支持默认值：

int n = opt<int>("n", 10);        // 找不到 --n 时返回 10
bool flag = opt<bool>("flag", false);
string s = opt("s", "abc");
if (has_opt("extra")) {
    // 存在 --extra 时执行
}

使用带默认值的 opt 后，testlib 会在程序退出前检查是否所有命令行选项都已被读取，这可以帮助你发现拼错的参数名。

Generator（数据生成）

生成器是什么？

生成器（generator）是负责产出测试数据的程序。大多数题目都有很大的输入（例如长度为 $2\times 10^5$ 的数组、$10^5$ 个点的树），不可能全部手造。此时就应该写生成器，用随机数据加少量手造特殊数据组成一套测试数据。

写生成器时强烈建议使用 testlib，而不是直接使用 rand() 或手写随机数。原因是：

• rand()、C++11 的 mt19937、uniform_int_distribution 等实现并不统一。同一份代码、同一个参数，换一个编译器或平台，完全可能生成不同的数据。
• testlib 自带一套跨平台一致的随机数生成器，并且已经封装好了很多造数据常用的功能。

testlib 生成器的第一句可执行代码必须是：

registerGen(argc, argv, 1);

其中第三个参数 1 表示使用新版随机数生成器。调用它之后，全局对象 rnd 会被初始化，并且所有命令行参数都会参与随机种子的计算。因此：

• 同样的命令，在任何编译器、任何平台上生成的测试数据都相同；
• 只要命令不同，随机种子一般也会不同，输出通常随之改变。

生成器分两种：

• 单测生成器：一次运行只输出一个测试，输出到标准输出。生成多个测试时，用不同命令行参数多跑几次，例如 ./gen --n=100 > 1.in。
• 多测生成器：一次运行输出很多测试。在输出每个测试前调用 startTest(i)，testlib 会把标准输出重定向到名为 i 的文件。

rnd 常用方法

rnd 的类型是 random_t。常用调用如下：

wnext 可以理解为对若干次 next 的结果取最大值或最小值。例如 rnd.wnext(3, 1) 等价于 max(rnd.next(3), rnd.next(3))；t 为负数时取最小值，t 为 0 时就是普通 next。

一个简单的单测生成器

下面的程序读取 --n、--maxa 和 --seed 三个参数，输出一行 $n$，再输出一行 $n$ 个整数。opt 的用法见上一节。

#include "testlib.h"
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);

    int n = opt<int>("n");
    int maxa = opt<int>("maxa", 100); // 当前版本的 testlib 支持默认值
    int seed = opt<int>("seed", 0);
    (void)seed; // 参数本身已经参与随机种子，读一下即可

    println(n);

    vector<int> a(n);
    for (int i = 0; i < n; i++)
        a[i] = rnd.next(1, maxa);

    println(a);
    return 0;
}

编译并运行：

g++ gen.cpp -O2 -std=c++17 -o gen
./gen --n=5 --maxa=10 --seed=1 > 1.in
./gen --n=5 --maxa=10 --seed=2 > 2.in

两次运行的参数只差一个 --seed，所以生成的数据不同；若连 --seed 也完全相同，则两次生成的数据必然相同。测试数据生成后，可以再用 --seed 值记录每份数据的“配方”，方便日后复现。

例：生成一棵无向树

下面是一个生成无向树的例子。n 是点数，t 控制树的形态：

#include "testlib.h"
#include <utility>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);

    int n = opt<int>(1);
    int t = opt<int>(2);

    // 先把 0 号点当作根，为 1..n-1 号点各选一个编号更小的父亲
    vector<int> p(n);
    for (int i = 1; i < n; i++)
        p[i] = rnd.wnext(i, t);

    // 打乱顶点编号，避免生成器痕迹太明显
    vector<int> perm = rnd.perm(n);

    vector<pair<int, int>> edges;
    for (int i = 1; i < n; i++) {
        int u = perm[i];
        int v = perm[p[i]];
        if (rnd.next(2))
            swap(u, v);
        edges.push_back(make_pair(u, v));
    }

    shuffle(edges.begin(), edges.end());

    // 输出时转成 1-based 编号
    println(n);
    for (auto e : edges)
        println(e.first + 1, e.second + 1);
    return 0;
}

说明：

• rnd.wnext(i, t) 返回 $[0,i-1]$ 中的整数。t 取一个很大的正数时，父亲偏向 $i-1$，树接近一条链；t 取一个很小的负数时，父亲偏向 $0$，树接近一朵菊花。
• 最后打乱边和顶点编号，可以让生成的树看起来更自然。

多测生成器

多测生成器在每次输出测试前调用 startTest(i)，例如下面的程序会生成 1、2、……、10 十个文件：

#include "testlib.h"

using namespace std;

void writeTest(int test) {
    startTest(test);

    int a = rnd.next(1, test * test);
    int b = rnd.next(1, test * test);
    println(a, b);
}

int main(int argc, char* argv[]) {
    registerGen(argc, argv, 1);

    for (int i = 1; i <= 10; i++)
        writeTest(i);
    return 0;
}

startTest(test) 会把标准输出重新打开为名为 test 的文件，所以生成后请检查当前目录，并按需要重命名。

生成器注意事项

1. 严格遵循输入格式。 空格、换行都要和题目描述完全一致；每个测试文件最后应当有一个换行。使用 println 输出整行可以少踩很多坑。
2. 大数据量注意输出速度。 大量小规模 cout << 可能较慢，可以用 testlib 的 println 或 printf。
3. 不要在一次 cout 语句中写多个 rnd.next。 例如：

   cout << rnd.next(1, n) << " " << rnd.next(1, n) << endl;

   这条语句中两个 rnd.next 的求值顺序是未定义的，不同编译器可能产生不同数据。先把两个随机数分别存入变量，再输出。
4. 参数解析用 opt，不要用 atoi(argv[3])。 atoi 不能安全处理参数缺失、参数不是合法整数等情况。
5. testlib 会阻止你使用 rand()/srand()；打乱容器时也请使用 testlib 的 shuffle，而不是 std::random_shuffle。

Validator（数据输入验证）

为什么要写 validator？

造完数据之后，还需要确认数据本身是合法的：上界可能写错、图可能不连通、数组长度可能和 $n$ 不一致、文件末尾可能多了一行空白……这些错误让选手遇到时会非常难受。validator（输入验证器）就是用来严格检查每个输入文件是否完全满足题目约束的程序。

写 validator 时，建议使用 testlib。它的读取函数本身就是“读什么就必须是什么”，格式错误时会立即报错，因此 validator 写得越贴近题面，数据越不容易出错。

基本结构

validator 的第一句可执行代码必须是：

registerValidation(argc, argv);

调用之后，就可以通过 inf 从标准输入读取数据。例如：

#include "testlib.h"

using namespace std;

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);

    inf.readInt(1, 100, "n");
    inf.readEoln();
    inf.readEof();
    return 0;
}

这段代码检查输入中恰好有一个 $[1,100]$ 的整数，并且它后面是换行和 EOF。本地运行时：

g++ val.cpp -O2 -std=c++17 -o val
./val < 1.in

• 数据合法时，validator 正常结束（返回 0）。
• 数据不合法时，validator 输出以 FAIL 开头的错误信息并返回非零值。

第三个参数 "n" 是可读变量名。如果数据越界，会得到类似这样的信息：

FAIL Integer parameter [name=n] equals to 0, violates the range [1, 100]

常用读取函数

validator 中常用的 inf 方法以及 ensure/ensuref 如下：

testlib validator 是严格模式，不会自动跳过空格。例如读取一个整数后，如果下一个字符是空格而不是换行，readEoln() 就会报错。请按题目格式把空格和换行也显式读掉。

另外，readEoln() 在 Windows 和 Linux 上对行尾的要求不同。如果在 Windows 上生成数据、在 Linux 上验证时遇到 Expected EOLN，请检查 .in 文件的行尾是否为 CRLF/LF 并统一格式。

多测数据的验证

对于有 $T$ 组测试数据的题目，使用 setTestCase(i)，报错时 testlib 会自动带上测试点编号：

#include "testlib.h"

using namespace std;

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);

    int T = inf.readInt(1, 10, "T");
    inf.readEoln();

    for (int tc = 1; tc <= T; tc++) {
        setTestCase(tc);
        int n = inf.readInt(1, 10000, "n");
        inf.readEoln();
        inf.readInts(n, -1000, 1000, "a");
        inf.readEoln();
    }

    inf.readEof();
    return 0;
}

例：验证一棵树

很多约束不是 readInt 的范围检查能表达的。例如“边不重复”“没有自环”“图是一棵树”，就需要在读取时额外判断。下面的 validator 验证输入为 $n$ 个点、$n-1$ 条边的无向树：

#include "testlib.h"
#include <set>
#include <vector>

using namespace std;

int find(vector<int>& f, int x) {
    return f[x] == x ? x : f[x] = find(f, f[x]);
}

int main(int argc, char* argv[]) {
    registerValidation(argc, argv);

    int n = inf.readInt(2, 100000, "n");
    inf.readEoln();

    vector<int> f(n + 1);
    for (int i = 1; i <= n; i++)
        f[i] = i;

    set<pair<int, int>> edges;
    for (int i = 0; i < n - 1; i++) {
        int x = inf.readInt(1, n, "x");
        inf.readSpace();
        int y = inf.readInt(1, n, "y");
        inf.readEoln();

        ensuref(x != y, "Tree can't contain loops");
        ensuref(edges.count(make_pair(x, y)) == 0,
                "Tree can't contain multiple edges between a pair of vertices");

        edges.insert(make_pair(x, y));
        edges.insert(make_pair(y, x));

        int rx = find(f, x);
        int ry = find(f, y);
        ensuref(rx != ry, "Tree can't contain cycles");
        f[rx] = ry;
    }

    inf.readEof();
    return 0;
}

这里同时检查了边数、编号范围、无自环、无重边、无环。对 $n$ 个点的无向图，$n-1$ 条边且无环，就能保证它是一棵树。

testlib 的正则（pattern）

readToken、readLine 等函数支持一个简化版正则，常用语法有：

• 字符集合：[a-z] 表示一个小写字母；[^a-z] 表示任意非小写字母字符；
• 长度范围：[a-z]{1,100} 表示长度 $1$ 到 $100$ 的小写字母串；
• 或：mike|john 表示两者之一；
• 可选字符：-?[1-9][0-9]{0,3} 可以匹配 $-9999$ 到 $9999$ 的非零整数；
• 重复：[0-9]* 和 [0-9]+。

它不是完整的编程语言正则，匹配算法也比较贪心。例如 pattern [0-9]?1 不能匹配 1，因为 [0-9]? 会先把 1 吃掉。需要严格检查小数位数时，建议直接使用 readStrictDouble。

testset 与 group

如果需要按测试集或测试组放宽/收紧限制，可以使用：

if (validator.testset() == "pretests") {
    // 只检查较小的范围
} else {
    // 检查完整范围
}

if (validator.group() == "even-n-and-m") {
    ensure(n % 2 == 0);
    ensure(m % 2 == 0);
}

运行时这样传入：

./val --testset pretests --group even-n-and-m < 1.in

验证器注意事项

1. 最后一定要 inf.readEof()，否则文件末尾多出的任何内容都不会被发现。
2. 题面写的是 long long 范围，就要用 readLong/readLongs，不要用 readInt。
3. 有 $T$ 组数据的题，记得 setTestCase。
4. 读数组时优先使用 readInts/readLongs，又短又不容易错。
5. 养成“每份数据都过一遍 validator”的习惯。生成器保证数据“长什么样”，validator 保证数据“没有长歪”。

杂话

• 本文的 Generator 部分主要整理自 testlib 官方博客和仓库中的 generators/ 示例；Validator 部分主要整理自官方博客和仓库中的 validators/ 示例。写新题时，直接复制仓库里的示例再改，通常比自己从头写更快。
• testlib 原版仓库：https://github.com/MikeMirzayanov/testlib；WyOJ 复制版：https://wfirstzhang.wyoj.org.cn/post/147。
• 本文只涉及 generator 和 validator。testlib 还提供 checker（比较输出）和 interactor（交互题），有需要时可以继续查阅官方文档。
• 推荐的造数据流程：先写 validator，把题面约束固化成代码；再写 generator；生成后用 validator 把每个 .in 都跑一遍；最后用标准程序/暴力程序对拍。