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 究竟是啥东西？为啥这么牛逼？
Testlib 是一套历史悠久的出题辅助工具库。它可以用于书写数据生成器（Generator），数据校验器（Validator），答案检查器（checker），交互器（interactor）。
著名编程竞赛平台 Codeforces 是 Testlib 的最大使用者。在 Codeforces 上出题，上面提到的四种程序都需要使用 Testlib 完成（详见 OI Wiki - 出题）。
最新版本的 Testlib 可以在 Github 上找到。
面对各种各样奇怪的输出文件，出题人都会感到十分头疼。
使用常规的 IO 来读取数据，鲁棒性很难得到保证。因此 Testlib 通过一套完善的 API 来读取数据，从而确保能在任何奇怪数据的考验下，都能给出正确的结果。
因为 Testlib 的 IO 库实在太重要了，我们对 Testlib 的介绍，首先从它的 IO 函数开始。
| 对象名 | 描述 |
|---|---|
inf |
输入文件流 |
ouf |
选手输出流 |
ans |
标准答案流 |
调用不同流对象的成员函数，就可以从不同的流中读入数据。
因为 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 位带符号整数，要求在 |
vector<long long> readLongs(int n, long long L, long long R) |
一次性读入 |
int readInt() 或 int readInteger() |
读入一个 32 位带符号整数。 |
int readInt(int L,int R) 或 int readInteger(int L,int R) |
读入一个 32 位带符号整数，要求在 |
vector<int> readInts(int n, int L, int R) 或 vector<int> readIntegers(int n, int L, int R) |
一次性读入 |
double readReal() 或 double readDouble() |
读入一个双精度浮点数。 |
double readReal(double L, double R) 或 double readDouble(double L, double R) |
读入一个双精度浮点数，要求在 |
double readStrictReal(double L, double R, int minPrecision, int maxPrecision) 或 double readStrictDouble(double L, double R, int minPrecision, int 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 位带符号整数。
如果读入的东西不符合期望（比如流指针指向一个字符串，却要求读入一个整数）会怎么办呢？在不同环境下结果会不一样，下面会讲到。
使用 Testlib 写数据生成器的一个好处是，如果参数一样，在不同的环境下数据生成器的结果都是一样的。而使用 rand() 的话，在不同环境下结果并不一样。
使用一个确定性的数据生成器显然会让出题人安心不少（方便了复现数据）。
首先是初始化，我们在开头调用 registerGen(argc, argv, 1); 来初始化一个 Generator（最后一个参数是 Generator 的版本号，一般不用改）。在此之后，我们有了一个对象 rnd，通过调用它的成员函数来生成随机数。
请注意：一旦使用了 Testlib，你就不能再调用 rand() 和 random_shuffle() 这些标准库内置随机函数。你只能使用 Testlib 内的 rnd 对象和 shuffle() 函数。
下面是一个 rnd 对象的成员函数列表：
| 函数 | 描述 |
|---|---|
rnd.next() |
生成一个 |
rnd.next(R) |
如果传入的参数是整数，生成一个 |
rnd.next(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) 的形式化定义：
下面是 Codeforces 上给出的一个生成树的代码（当参数
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);有两种方法可以一次性生成多组数据：
startTest(test_index) 函数。第一种方法非常简单，只需设好参数，将输出重定向到指定输出文件即可。
gen 1 1 > 1.in
gen 2 1 > 2.in
gen 1 10 > 3.in对于第二种方法，在每生成一组数据前，调用一次 startTest(test_index)，即可将输出重定向至名为 test_index 的文件。
下面是一个使用 startTest 函数生成多组数据的例子。
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;
}生成了一组数据后，需要检验这个数据是否符合要求（是否满足数据范围，数据的性质是否正确），这时候就需要写一个 Validator 来校验数据正确性。
校验器的开头需要先调用 registerValidation(argc, argv); 完成初始化。
下面是一个检验一个图是否是树的校验器：
#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 是否合法，如果出现问题将返回错误信息。
一些常见的坑点在上面的注释中写的很清楚了，这里再次强调一下：
ensuref() 的使用方式在刚才的例子中，出现了一个新函数 ensuref()，它的作用与 assert() 类似。
以上面的例子为例，当 merge(u,v) 返回 false 时（即出现了环），ensuref() 就会被触发，并输出指定的错误信息。
现在的不少题目都没有一个固定的输出。给出一个输出，评判它是否正确，能得多少分，都需要用到 Checker。
Testlib 书写的 Checker 由于使用了一套较为严密的函数进行读取操作，从而避开了各种各样奇怪的输出导致 Judgment Failed 的惨剧。
先来一个浮点数加法的例子吧！
下面这个 checker 会判断选手输出和标准输出的绝对误差是否小于
还是一样，在使用 checker 前需要调用 registerTestlibCmd(argc,argv); 完成初始化。
#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 |
出现异常。可能原因有选手的答案比标准答案优，或标准答案不合法，需要特别注意。 |
（下面的内容参考了 Codeforces 上的文档）
下面是一个比较复杂的例子：给一个有向无环图，求其最长路径并输出。如果有多条最长路径，任意输出一条。
下面是一个不太好的 checker 实现：
#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。
#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);
}如果你要动手写一个 checker 的话，这里有一些建议：
quitf 的反馈信息应该尽量详细。这一方面方便选手了解问题出在何处，另一方面方便了调试；如果要出一道交互题的话，交互器是必不可少的。
Testlib 的交互器可以用于 stdio 交互（即选手通过标准输入输出与交互器进行交互）。
考虑到交互题比较特殊，流对象的含义也发生了些变化。
| 对象名 | 描述 |
|---|---|
inf |
输入文件流 |
ouf |
选手输出流（选手向交互器的输出） |
ans |
标准答案流 |
tout |
输出日志流（交互器可以向该流写入信息，checker 可以从 ouf 中读取这些信息） |
一个 interactor 的交互流程是这样的：
inf 中读取所需信息；ouf 中读取选手向交互器的输出（如果读入的数据不合法，则会返回 _wa）；stdout 输出信息给选手程序；ouf 的信息（也就是交互器向 tout 输出的信息）来判断交互情况）。和选手写的程序一样，为了确保输出不被缓存，请在输出一行后立刻刷新缓冲区。
在本地环境下，请通过 interactor <input-file> <output-file> [<ans-file>] 的方式调用交互器（ans-file 是可选的）。
（下面的内容参考了 Codeforces 上的文档）
这是一个非常经典的猜数字游戏的例子：交互器随机生成一个
你需要向交互器输出一个数，交互器将会根据情况返回这几种结果：
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);
}注：这个例子没有检查标准答案，因为并不需要这么做。但其他题可能并非如此。