[洛谷日报#271]Testlib——最强出题辅助工具库
StudyingFather
2020-02-25 18:20:50
> Q：写个 Special Judge 太难了，面对各种各样奇怪的输出，搞不好 spj 就 RE 了。
>
> A：试试用 Testlib 写 checker？根本不用担心各种各样奇怪的格式问题。
>
> Q：写个数据生成器太难了，同样一套数据生成器，同样的生成参数，放到 Linux 下生成的数据就变了个样，这咋整啊？
>
> A：用 Testlib 写 generator 吧，同样的数据生成器，同样的参数，保证在任何环境下参数都一样。
>
> Q：草，最近一场模拟赛出题人用脚造数据，明明是一棵树，他给造了个环出来。
>
> A：你可以教他用 Testlib 写 Validator。
>
> Q：最近想出个交互题，不知道交互器咋写。
>
> A：用 Testlib 吧，写 interactor 也方便了不少呢。
>
> Q：所以 Testlib 究竟是啥东西？为啥这么牛逼？
## 1 啥是 Testlib
Testlib 是一套历史悠久的出题辅助工具库。它可以用于书写数据生成器（Generator），数据校验器（Validator），答案检查器（checker），交互器（interactor）。
著名编程竞赛平台 Codeforces 是 Testlib 的最大使用者。在 Codeforces 上出题，上面提到的四种程序都需要使用 Testlib 完成（详见 [OI Wiki - 出题](https://oi-wiki.org/topic/problemsetting/)）。
最新版本的 Testlib 可以在 [Github](https://github.com/MikeMirzayanov/testlib) 上找到。
## 2 Testlib 的 IO 库
面对各种各样奇怪的输出文件，出题人都会感到十分头疼。
使用常规的 IO 来读取数据，鲁棒性很难得到保证。因此 Testlib 通过一套完善的 API 来读取数据，从而确保能在任何奇怪数据的考验下，都能给出正确的结果。
因为 Testlib 的 IO 库实在太重要了，我们对 Testlib 的介绍，首先从它的 IO 函数开始。
### 2.1 流对象
| 对象名 | 描述 |
| ------ | ---------- |
| `inf` | 输入文件流 |
| `ouf` | 选手输出流 |
| `ans` | 标准答案流 |
调用不同流对象的成员函数，就可以从不同的流中读入数据。
### 2.2 流函数
因为 Testlib 的流函数非常多，这里只列出一些常用函数。
有些函数有等价的表示，下面也一并给出。
| 函数 | 描述 |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| `char readChar()` | 读入一个字符。 |
| `char readChar(char c)` | 读入一个字符，要求必须为 `c`。 |
| `char readSpace()` | 读入一个空格，等价于 `readChar(' ')`。 |
| `void unreadChar(char c)` | 把字符 `c` 返回到流中。 |
| `string readToken()` 或 `string readWord()` | 读入一个串，不包含任何空字符（空格，制表符，换行等）。 |
| `string readToken(string regex)` 或 `string readWord(string regex)` | 读入一个串，且必须与 `regex` 一致。 |
| `long long readLong()` | 读入一个 64 位带符号整数。 |
| `long long readLong(long long L,long long R)` | 读入一个 64 位带符号整数，要求在 $[L,R]$ 的范围内。 |
| `vector<long long> readLongs(int n, long long L, long long R)` | 一次性读入 $n$ 个 64 位带符号整数，要求每个数都在 $[L,R]$ 的范围内。 |
| `int readInt()` 或 `int readInteger()` | 读入一个 32 位带符号整数。 |
| `int readInt(int L,int R)` 或 `int readInteger(int L,int R)` | 读入一个 32 位带符号整数，要求在 $[L,R]$ 范围内。 |
| `vector<int> readInts(int n, int L, int R)` 或 `vector<int> readIntegers(int n, int L, int R)` | 一次性读入 $n$ 个 32 位带符号整数，要求每个数都在 $[L,R]$ 范围内。 |
| `double readReal()` 或 `double readDouble()` | 读入一个双精度浮点数。 |
| `double readReal(double L, double R)` 或 `double readDouble(double L, double R)` | 读入一个双精度浮点数，要求在 $[L,R]$ 范围内。 |
| `double readStrictReal(double L, double R, int minPrecision, int maxPrecision)` 或 `double readStrictDouble(double L, double R, int minPrecision, int maxPrecision)` | 读入一个双精度浮点数，要求在 $[L,R]$ 范围内，且它的小数位数必须介于 $[minPrecision,maxPrecision]$ 之间，且不允许使用科学计数法等其他形式（例如 `1.0e+2` 这样的形式就是不允许的）。 |
| `string readString()` 或 `string readLine()` | 读入一整行（包含换行符），将流指针指向新行的第一个字符（如果存在）。 |
| `string readString(string regex)` 或 `string readLine(string regex)` | 读入一整行（包含换行符），且要求读入的串与 `regex` 一致。 |
| `void readEoln()` | 读入换行符，注意在 Windows 下会读入 `CR LF`，而在 Linux 下会读入 `LF`。 |
| `void readEof()` | 读入文件结束符 EOF。 |
调用的时候，只需按照 `流对象.流函数` 这样的语法调用，即可从指定的流中执行读入操作。例如 `inf.readInt()` 就可以从输入流中读入一个 32 位带符号整数。
如果读入的东西不符合期望（比如流指针指向一个字符串，却要求读入一个整数）会怎么办呢？在不同环境下结果会不一样，下面会讲到。
## 3 Generator
使用 Testlib 写数据生成器的一个好处是，如果参数一样，在不同的环境下数据生成器的结果都是一样的。而使用 `rand()` 的话，在不同环境下结果并不一样。
使用一个确定性的数据生成器显然会让出题人安心不少（方便了复现数据）。
### 3.1 一些函数
首先是初始化，我们在开头调用 `registerGen(argc, argv, 1);` 来初始化一个 Generator（最后一个参数是 Generator 的版本号，一般不用改）。在此之后，我们有了一个对象 `rnd`，通过调用它的成员函数来生成随机数。
请注意：**一旦使用了 Testlib，你就不能再调用 `rand()` 和 `random_shuffle()` 这些标准库内置随机函数**。你只能使用 Testlib 内的 `rnd` 对象和 `shuffle()` 函数。
下面是一个 `rnd` 对象的成员函数列表：
| 函数 | 描述 |
| ------------------- | ------------------------------------------------------------ |
| `rnd.next()` | 生成一个 $[0,1)$ 之间的浮点数。 |
| `rnd.next(R)` | 如果传入的参数是整数，生成一个 $[0,R - 1]$ 之间的整数。如果传入的参数是浮点数。生成一个 $[0,R)$ 之间的浮点数。 |
| `rnd.next(L,R)` | 如果传入的参数是整数，生成一个 $[L,R]$ 之间的整数。如果传入的参数是浮点数。生成一个 $[L,R)$ 之间的浮点数。 |
| `rnd.any(c)` | 返回容器 `c` 内的一个随机元素。对 `vector` 和 `string` 都可以使用。 |
| `rnd.wnext(i,t)` | 不均匀随机数生成器（具体定义比较长，下面会给出）。`rnd.wnext(4,2)` 相当于 `max(rnd.next(4),rnd.next(4))`；`rnd.wnext(4,-2)` 相当于 `min(rnd.next(4),rnd.next(4))`；`rnd.wnext(4,0)` 相当于 `rnd.next(4)`。 |
| `rnd.next("a|b|c")` | 等概率返回 `a`，`b`，`c` 这三个字符串中的一个。 |
附：关于 `rnd.wnext(i,t)` 的形式化定义：
$$
\operatorname{wnext}(i,t)=\begin{cases}\operatorname{next}(i) & t=0 \\\max(\operatorname{next}(i),\operatorname{wnext}(i,t-1)) & t>0 \\\min(\operatorname{next}(i),\operatorname{wnext}(i,t+1)) & t<0\end{cases}
$$
### 3.2 一个例子
下面是 [Codeforces](https://codeforces.com/blog/entry/18291) 上给出的一个生成树的代码（当参数 $t$ 较大时，生成的树更接近链，$t$ 较小时，生成的树更接近菊花）：
```cpp
registerGen(argc, argv, 1);//初始化数据生成器
int n = atoi(argv[1]);
int t = atoi(argv[2]);
vector<int> p(n);
//给 1..n-1 号点设置父亲
for(int i = 0; i < n; ++i)
if (i > 0)
p[i] = rnd.wnext(i, t);
printf("%d\n", n);
//打乱节点排序
vector<int> perm(n);
for(int i = 0; i < n; ++i)
perm[i] = i;
shuffle(perm.begin() + 1, perm.end());
// 随机加边
vector<pair<int,int> > edges;
for (int i = 1; i < n; i++)
if (rnd.next(2))
edges.push_back(make_pair(perm[i], perm[p[i]]));
else
edges.push_back(make_pair(perm[p[i]], perm[i]));
//打乱边的顺序
shuffle(edges.begin(), edges.end());
for (int i = 0; i + 1 < n; i++)
printf("%d %d\n", edges[i].first + 1, edges[i].second + 1);
```
### 3.3 生成多组数据
有两种方法可以一次性生成多组数据：
1. 写一个批处理脚本。
2. 使用 Testlib 内置的 `startTest(test_index)` 函数。
第一种方法非常简单，只需设好参数，将输出重定向到指定输出文件即可。
```bash
gen 1 1 > 1.in
gen 2 1 > 2.in
gen 1 10 > 3.in
```
对于第二种方法，在每生成一组数据前，调用一次 `startTest(test_index)`，即可将输出重定向至名为 `test_index` 的文件。
下面是一个使用 `startTest` 函数生成多组数据的例子。
```cpp
int main(int argc,char** argv)
{
registerGen(argc,argv,1);
int a,b,c;
for(int i=1;i<=10;i++)
{
startTest(i);
a=rnd.next(100),b=rnd.next(100),c=rnd.next(100);
genData(a,b,c);
}
return 0;
}
```
## 4 Validator
生成了一组数据后，需要检验这个数据是否符合要求（是否满足数据范围，数据的性质是否正确），这时候就需要写一个 Validator 来校验数据正确性。
校验器的开头需要先调用 `registerValidation(argc, argv);` 完成初始化。
### 4.1 一个例子
下面是一个检验一个图是否是树的校验器：
```cpp
#include "testlib.h"
using namespace std;
int fa[105];
void init(int n)
{
for(int i=1;i<=n;i++)
fa[i]=i;
}
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool merge(int x,int y)
{
x=find(x),y=find(y);
if(x==y)return false;
fa[y]=x;
return true;
}
int main(int argc,char** argv)
{
registerValidation(argc,argv);//初始化校验器
int n=inf.readInt(1,100);
inf.readEoln();
init(n);
for(int i=1;i<n;i++)
{
//int u=inf.readInt(1,n),v=inf.readInt(1,n);
//Validator 对格式要求非常严格，上面的写法忽略了两个数之间的空格
//下面的写法是正确的
int u=inf.readInt(1,n);
inf.readSpace();
int v=inf.readInt(1,n);
ensuref(merge(u,v),"Loop found!");
inf.readEoln();
}
//最后必须读入文件结束符 EOF
inf.readEof();
return 0;
}
```
在命令行下执行 `val < 1.in` 即可校验 `1.in` 是否合法，如果出现问题将返回错误信息。
### 4.2 注意事项
一些常见的坑点在上面的注释中写的很清楚了，这里再次强调一下：
1. **与 Checker 不同的是，Validator 对格式的要求非常严格**，多出的一个空格或一个回车都会导致校验失败。
2. Validator 最后必须读入文件结束符 EOF 表示校验结束。
### 4.3 `ensuref()` 的使用方式
在刚才的例子中，出现了一个新函数 `ensuref()`，它的作用与 `assert()` 类似。
以上面的例子为例，当 `merge(u,v)` 返回 false 时（即出现了环），`ensuref()` 就会被触发，并输出指定的错误信息。
## 5 Checker
现在的不少题目都没有一个固定的输出。给出一个输出，评判它是否正确，能得多少分，都需要用到 Checker。
Testlib 书写的 Checker 由于使用了一套较为严密的函数进行读取操作，从而避开了各种各样奇怪的输出导致 Judgment Failed 的惨剧。
### 5.1 一个简单的例子
先来一个浮点数加法的例子吧！
下面这个 checker 会判断选手输出和标准输出的绝对误差是否小于 $10^{-5}$，如果满足这一条件则认为输出正确。
还是一样，在使用 checker 前需要调用 `registerTestlibCmd(argc,argv);` 完成初始化。
```cpp
#include "testlib.h"
using namespace std;
int main(int argc,char** argv)
{
registerTestlibCmd(argc,argv);//初始化 checker
double pans=ouf.readDouble(),jans=ans.readDouble();
if(abs(pans-jans)<=1e-5)quitf(_ok,"Correct!");
else quitf(_wa,"Wrong Answer!");
}
```
编译后，按如下方式调用即可得到反馈：`spj <input-file> <output-file> <ans-file>`。
这里出现了一个新函数 `quitf()`，它将会反馈评测结果，并输出指定信息。
可用的状态有如下几种：
| 状态 | 描述 |
| ------------ | ------------------------------------------------------------ |
| `_ok` | 选手输出可以被接受。 |
| `_wa` | 选手输出不能被接受。 |
| `_pe` | 格式错误（事实上 Testlib 不检查输出格式）。 |
| `_pc(score)` | 部分正确，可以得到 score 的分数。 |
| `_fail` | 出现异常。可能原因有选手的答案比标准答案优，或标准答案不合法，需要特别注意。 |
### 5.2 进阶用法
（下面的内容参考了 [Codeforces 上的文档](https://codeforces.com/blog/entry/18431)）
下面是一个比较复杂的例子：给一个有向无环图，求其最长路径并输出。如果有多条最长路径，任意输出一条。
下面是一个不太好的 checker 实现：
```cpp
#include "testlib.h"
#include <map>
#include <vector>
using namespace std;
map<pair<int, int>, int> edges;
int main(int argc, char* argv[]) {
registerTestlibCmd(argc, argv);
int n = inf.readInt();
int m = inf.readInt();
for (int i = 0; i < m; i++) {
int a = inf.readInt();
int b = inf.readInt();
int w = inf.readInt();
edges[make_pair(a, b)] = edges[make_pair(b, a)] = w;
}
int s = inf.readInt();
int t = inf.readInt();
//读取标准答案
int jvalue = 0;
vector<int> jpath;
int jlen = ans.readInt();
for (int i = 0; i < jlen; i++) {
jpath.push_back(ans.readInt());
}
for (int i = 0; i < jlen - 1; i++) {
jvalue += edges[make_pair(jpath[i], jpath[i + 1])];
}
//读取选手输出
int pvalue = 0;
vector<int> ppath;
vector<bool> used(n, false);
int plen = ouf.readInt(2, n, "number of vertices");
for (int i = 0; i < plen; i++) {
int v = ouf.readInt(1, n, format("path[%d]", i + 1).c_str());
if (used[v - 1]) //确保一个点不会被经过两次
quitf(_wa, "vertex %d was used twice", v);
used[v - 1] = true;
ppath.push_back(v);
}
//检查路径是从 s 到 t 的路径
if (ppath.front() != s)
quitf(_wa, "path doesn't start in s: expected s = %d, found %d", s, ppath.front());
if (ppath.back() != t)
quitf(_wa, "path doesn't finish in t: expected t = %d, found %d", t, ppath.back());
//检查每一条边是否存在
for (int i = 0; i < plen - 1; i++) {
if (edges.find(make_pair(ppath[i], ppath[i + 1])) == edges.end())
quitf(_wa, "there is no edge (%d, %d) in the graph", ppath[i], ppath[i + 1]);
pvalue += edges[make_pair(ppath[i], ppath[i + 1])];
}
if (jvalue != pvalue)
quitf(_wa, "jury has answer %d, participant has answer %d", jvalue, pvalue);
else
quitf(_ok, "answer = %d", pvalue);
}
```
这个 checker 的问题出在了哪里呢？
- 假如选手输出比标准输出更优的话，按照上面的说明应该返回的是 `_fail`，但这个 checker 返回的是 `_wa`。因此如果这种事情发生的话，上面的 checker 将无法发现数据出了问题。
- 代码过于冗杂。注意到标准输出和选手输出本质上是平等的（输出的内容都一样），我们可以写一个函数来处理这两个输出。
下面是一个改进后的 checker。
```cpp
#include "testlib.h"
#include <map>
#include <vector>
using namespace std;
map<pair<int, int>, int> edges;
int n, m, s, t;
//这个函数传入了一个流对象作为参数
//从而减少代码长度
int readAns(InStream& stream) {
int value = 0;
vector<int> path;
vector<bool> used(n, false);
int len = stream.readInt(2, n, "number of vertices");
for (int i = 0; i < len; i++) {
int v = stream.readInt(1, n, format("path[%d]", i + 1).c_str());
if (used[v - 1]) {//确保每个点不会被用两次
//stream.quitf 和 quitf 的区别在于流的不同将会影响返回状态的不同
//如果 stream=ouf，它和 quitf 没有区别
//但如果 stream=ans，一切本来要返回 _wa 的状态都会返回 _fail（表明出现异常）
stream.quitf(_wa, "vertex %d was used twice", v);
}
used[v - 1] = true;
path.push_back(v);
}
//检查这条路径的起点是 s，终点是 t
if (path.front() != s)
stream.quitf(_wa, "path doesn't start in s: expected s = %d, found %d", s, path.front());
if (path.back() != t)
stream.quitf(_wa, "path doesn't finish in t: expected t = %d, found %d", t, path.back());
//检查路径上的相邻两点确实有边相连
for (int i = 0; i < len - 1; i++) {
if (edges.find(make_pair(path[i], path[i + 1])) == edges.end())
stream.quitf(_wa, "there is no edge (%d, %d) in the graph", path[i], path[i + 1]);
value += edges[make_pair(path[i], path[i + 1])];
}
return value;
}
int main(int argc, char* argv[]) {
registerTestlibCmd(argc, argv);
n = inf.readInt();
m = inf.readInt();
for (int i = 0; i < m; i++) {
int a = inf.readInt();
int b = inf.readInt();
int w = inf.readInt();
edges[make_pair(a, b)] = edges[make_pair(b, a)] = w;
}
int s = inf.readInt();
int t = inf.readInt();
int jans = readAns(ans);
int pans = readAns(ouf);
if (jans > pans)
quitf(_wa, "jury has the better answer: jans = %d, pans = %d\n", jans, pans);
else if (jans == pans)
quitf(_ok, "answer = %d\n", pans);
else //选手输出比标准答案更优，返回 _fail
quitf(_fail, ":( participant has the better answer: jans = %d, pans = %d\n", jans, pans);
}
```
### 5.3 一些建议
如果你要动手写一个 checker 的话，这里有一些建议：
1. checker 与 validator 不同，不用特别检查空白字符。
2. `quitf` 的反馈信息应该尽量详细。这一方面方便选手了解问题出在何处，另一方面方便了调试；
3. 记得限定参数范围，防止 checker 出现访问非法内存等问题；
4. 善用 readAns 函数来降低代码长度；
## 6 Interactor
如果要出一道交互题的话，交互器是必不可少的。
Testlib 的交互器可以用于 stdio 交互（即选手通过标准输入输出与交互器进行交互）。
### 6.1 流对象
考虑到交互题比较特殊，流对象的含义也发生了些变化。
| 对象名 | 描述 |
| ------ | ------------------------------------------------------------ |
| `inf` | 输入文件流 |
| `ouf` | 选手输出流（选手向交互器的输出） |
| `ans` | 标准答案流 |
| `tout` | 输出日志流（交互器可以向该流写入信息，checker 可以从 ouf 中读取这些信息） |
### 6.2 交互流程
一个 interactor 的交互流程是这样的：
1. 从输入文件流 `inf` 中读取所需信息；
2. 从选手输出流 `ouf` 中读取选手向交互器的输出（如果读入的数据不合法，则会返回 `_wa`）；
3. 向标准输出 `stdout` 输出信息给选手程序；
4. 如果交互正常结束，checker 将确认答案正确性（这时候 checker 可以通过读取 `ouf` 的信息（也就是交互器向 `tout` 输出的信息）来判断交互情况）。
和选手写的程序一样，**为了确保输出不被缓存，请在输出一行后立刻刷新缓冲区**。
在本地环境下，请通过 `interactor <input-file> <output-file> [<ans-file>]` 的方式调用交互器（`ans-file` 是可选的）。
### 6.3 一个例子
（下面的内容参考了 [Codeforces 上的文档](https://codeforces.com/blog/entry/18455)）
这是一个非常经典的猜数字游戏的例子：交互器随机生成一个 $[1,10^9]$ 的整数，你有 $50$ 次猜测的机会。
你需要向交互器输出一个数，交互器将会根据情况返回这几种结果：
- 1：表示你猜的数和实际相等，你需要立刻停止询问；
- 0：表示你猜的数比实际小；
- 2：表示你猜的数比实际大。
```cpp
int main(int argc, char ** argv){
registerInteraction(argc, argv);//初始化交互器
int n = inf.readInt();
cout.flush();
int left = 50;
bool found = false;
while(left > 0 && !found){
left --;
int a = ouf.readInt(1, 1000000000);//读取选手猜的数，记得检查范围
if(a < n)
cout << 0 << endl;
else if(a > n)
cout << 2 << endl;
else
cout << 1 << endl, found = true;
cout.flush();
}
if(!found)
quitf(_wa, "couldn't guess the number with 50 questions");
ouf.readEof();
quitf(_ok, "guessed the number with %d questions!", 50 - left);
}
```
注：这个例子没有检查标准答案，因为并不需要这么做。但其他题可能并非如此。
## Reference
- [Testlib - Codeforces](https://codeforces.com/testlib)
- [Testlib - OI-wiki](https://oi-wiki.org/intro/testlib/)