写在前面

本文旨在介绍基于 CYaRon 的信息学题目数据构造工作流，希望能帮助大家更加方便快捷地造出更强更毒瘤的测试数据，避免因为出锅或强度不够而被喷烂。

所有的引用材料已在文末附上，为避免有时 Github 因为一些奇奇怪怪的原因无法访问的情况，笔者找到了一份官方文档的民间镜像。在此感谢原作者 @czj_is_a_rookie。

CYaRon 简介

CYaRon 是由洛谷开发的基于 Python 的开源软件（但我们称之为轮子），用于便捷地生成 OI 题目的测试数据（并且在大多数情况下强度不低）。

其官方英文解释为 CYaRon Yet Another Random Olympic-iNformatics test data generator，但又有谁会信呢明明就是一个二次元含量100%的名字诶。并且怎么又是递归缩写……

CYaRon 入门

学会读文档是一个优秀程序员的基本素质——沃兹基·硕德

官方文档给的非常详细，列举了大量实例，方便您快速入门。

安装

首先您要确保您的计算机上有 Python 环境，推荐至少为 Python 3，笔者电脑上是 Python 3.9.2，以下内容将以此版本为准。如果您没有 Python 开发环境或版本过低，请于 Python官网 下载。注意在安装时勾选“添加到环境变量”一项。

随后，打开命令行，运行以下命令：

pip install cyaron

等待进度条读完，下载完成！

笔者安装的 CYaRon 版本为 0.4.3，以下介绍将以此版本为准。

编辑

这里推荐使用 Visual Studio Code 作为您的 Python 编辑器，详情参见 日报#12，此处不再赘述。请注意您可能需要下载名为 \text{Python} 的 VSCode 扩展插件，否则 Python 程序将无法正常被语法高亮。

编写数据生成器

在写一个完整的数据生成器之前，首先你得有一个标程。

但是如果没有的话也没关系，只是不能生成输出文件而已。

首先，编译标程，得到一个可执行文件。请注意这个可执行文件的路径，以后会用到。

如果您的计算机上有多个版本的 C/C++ 编译器，建议使用最新版的稳定版本或与比赛环境尽可能类似的编译器版本，避免因为编译器问题导致标程行为不符合预期从而使数据出锅。尽量不要碰那些 Profilling 版本的编译器，不然出锅都不知道怎么出的。同理，尽量不要给标程添加大于 -O2 的编译器优化，避免标程运行结果不理想。最后请确保您与标程提供者能够畅通联系以便随时补锅，并请 ta 确保标程中没有 UB。

别问我怎么知道的。MinGW-w64 GCC 10.3.0 64-bit Profiling 版本的编译器有锅，随机抽风。

之后，新建一个 Python 文件，在第一行写下

from cyaron import *

之后，您就可以调用 CYaRon 提供的所有函数了。

这是我目前正在参与出题的一道题目的数据生成器部分：

from cyaron import *

for id in range(1, 21):
    test_data = IO(file_prefix="tree_", data_id=id)

这样的话生成的数据组们长这个样子：

以此类推，一共有 20 组数据。

在没有特殊指定 input_suffix 和 output_suffix 之前输入文件后缀名默认为 .in，输出文件后缀名默认为 out。当然您可以通过在函数中指定这两个变量来修改测试用例的后缀名。

如果您不想生成输出样例，可以在函数中指定 disable_output=True。

接下来可以根据题目需求编写您的数据生成器了。请记住您的所有问题基本都能在文档里得到解决。如果文档里没有的话就手写吧。

最后，使用 test_data.output_gen() 来生成输出样例（如果 disable_output 为 False）。此函数的参数为标程编译出来的可执行文件的地址。不要往括号里放一个 .cpp 之类的东西，出锅都不知道怎么出的，还贼难 debug（因为你压根想不到会在最后一行出锅）。

多种数据范围的处理之道

Python 没有大括号，这能让争论稍稍平息。但码风仍旧是重要的。

考虑如下例子，

输入文件第一行两个整数 n，m，表示一个图边数和点数。
接下来 m 行一个 DAG，以 u，v，w 的形式表示一条边。

出题人非常贴心地在题目最后附上了表格如下。

\begin{array}{|c|c|c|c|} \hline \text{测试点编号} & n & m & w_i \\ \hline 1-5 & 1\leq n\leq 1000 & n-1\leq m\leq 2000 & 1\leq w_i\leq 300 \\ \hline 6-10 & 1\leq n\leq 20000 & n-1\leq m\leq 50000 & 1\leq w_i\leq 500 \\ \hline 11-20 & 1\leq n\leq 10^6 & n-1\leq m\leq5\times10^6 & 1\leq w_i\leq 500\\ \hline \end{array}

看到这里，是不是已经心跳加快，血压升高，开始问候出题人的直系亲属了？不要着急，看看你可以采用什么方法偷懒。

分析题目，发现并没有什么特殊性质（如果有的话也没关系，只需要加个特判）。这样的情况其实相当好处理。我们提供一个实例如下。

from cyaron import *

for id in range(1, 21):

    test_data = IO(file_prefix="data_", data_id=id)

    # 先把这几个变量定义了以避免作用域问题    
    MAXN = 0
    MAXM = 0
    MAXW = 0

    if id <= 5:
        MAXN = 1000
        MAXM = 2000
        MAXW = 300
    elif id <= 10: # 即 C++ 中的 else if
        MAXN = 20000
        MAXM = 50000
        MAXW = 500
    else:
        MAXN = int(1e6) # 不要把 C++ 的 (int)1e6 带到这里来！
        MAXM = int(5e6)
        MAXW = 500

    n = randint(500, MAXN) # 保证最低数据强度
    m = randint(n - 1, MAXM) # DAG 的性质，边数大于等于节点数-1
    graph = Graph.DAG(n, m) # n 点 m 边的 DAG
    test_data.writeln(n, m)
    test_data.writeln(graph)

    test_data.output_gen("假装这是标程地址")

是不是很简单？同样地，特殊性质也可以用这种方法来判断。另外，Python 的部分细节语法和各位熟悉的 C++ 有较大差异，不要把 C++ 的一些偷懒写法带入 Python。

成为负责任的数据人

再完美不过的反面教材：CSP-S 2022 T3

图论题对于数据人的挑战最大。这些问题往往会让只会随机生成样例的数据人体验到输出 NO 能拿满分、输出 1 能拿满分、打个奇奇怪怪的乱搞能拿满分、打个离谱到半人马座的贪心能拿满分等一系列快乐，并让自己的直系亲属在赛后总结帖中陷入危险。

如果这种情况出现了，作为数据人，我们就要完成对于我们来说最艰巨的任务：构造数据。

我们要想有没有一些性质能让问题有解。如果可以的话，就尽可能利用 CYaRon 已有的功能实现（基本都可以）。比如文档里的这个示例：

binary_tree = Graph.binary_tree(n, 0.4, 0.35)
# 生成一棵n个节点的二叉树，其中节点有40%的概率是左儿子，35%的概率是右儿子，25%的概率被随机选择

这样的话不仅方便快捷，还不容易出锅。记住：多一事不如少一事。

如果你还不能解决问题，那么接下来，你面前的有两种可能：

1. 有明确的特殊性质，但是 CYaRon 库函数里没有；
2. 没有明确的特殊性质（但是它总有一些性质让问题可解）。

对于第一种情况，

1. 去 Github 上面提 issue，由于响应时间过长故不推荐，但是被开发者看到的 issues 能帮之后的数据人们减少困难，所以提 issue 就是在为 CYaRon 的开发做贡献。
2. 自力更生，丰衣足食（继续往下看）。

对于第二种情况：

我们要想如果有解的情况下是什么样的。是不是数据一定符合一些特征然后经过标程里一些奇奇妙妙的操作最后得到最终的答案的？我们没办法固定它的性质去找答案，那我们固定答案有解去反推特征是否可行呢？在大多数题目下是可行的。这里只是提供一个思想，因为不同的题目有不同的特征。如果您想到用什么样的算法能够解决问题但是不知如何实现的话，请继续往下看。

学会利用外部工具

现在我们面临的问题都是用 Python 和 CYaRon 难以解决的那些毒瘤性质。我们来看这样一个例子。

题目：一笔画问题的经典模型。给定一个无向连通图，如果存在一笔画方案就输出 YES，不存在就输出 NO。

如果随机生成数据，那么除非你拯救了地球积攒了巨量 RP，不然你的每一个输出样例都会是这个样子：

接下来我们要考虑特殊性质。如果这个问题有解，那么这张无向图里要么没有度数为奇数的点，要么只有两个度数为奇数的点。于是我们的第一反应应该是去翻 CYaRon 文档，但是很遗憾，开发者们并没有开发给定度数序列生成图的功能。

分析这个问题，首先确定一个图里一定只有偶数个奇数点。那么显然，使数据全部是 NO 的原因是奇数点过多。我们考虑如何减少奇数点的数量。

显然，给一个奇数加上 1 之后就会变成偶数，那么在两个奇数点之间加一条边就能把这两个奇数点同时消为偶数点。接下来的思路非常显然：

1. 读入整张图并统计奇数点个数，把奇数点编号记录下来；
2. 随机抽出两个奇数点相连，然后将其统计为偶数点；
3. 重复第二步直至奇数点数量小于等于 2；
4. 更新边数，重新将图输出。

为了方便起见，不妨把奇数点全部消去（此时全部为偶数点）后给一部分的测试样例增加一个节点，让其与 1 号节点相连（此时这些测试样例里面有两个度数为奇数的点）。不难看出，这样既能减少随机数的运算，还不会影响数据强度。

我们提供一种可能的实现如下。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

int dg[MAXN];
queue<int> lst;
vector<int> e[MAXN];

int main()
{
    srand((unsigned)time(NULL));
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        dg[u]++;
        dg[v]++;
    }

    for (int i = 1; i <= n; i++)
    {
        if (dg[i] % 2) lst.push(i);
    }

    while (!lst.empty())
    {
        int u = lst.front(); lst.pop();
        int v = lst.front(); lst.pop();
        e[u].push_back(v);
        m++;
    }

    int typ = rand() % 2;
    if (typ == 1)
    {
        n++;
        e[1].push_back(n);
        m++;
    }

    cout << n << " " << m << endl;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < e[i].size(); j++)
        {
            cout << i << " " << e[i][j] << endl;
        }
    }
    return 0;
}

如果您对图论足够熟练并且这是一道传统 OI 题目，您应该不用 15 分钟就能切掉它。但是我们要让这个程序与 CYaRon 联动。如何实现？

首先我们要用 CYaRon 生成一张随机图并将其输出到输出文件，再用我们的 C++ 程序来完成剩下的步骤。这里是 CYaRon 核心代码的一种实现。

n = randint(1, MAXN)
m = randint(n, MAXM)
graph = Graph.UDAG(n, m)
test_data.input_writeln(n, m)
test_data.input_writeln(graph.to_str(output = Edge.unweighted_edge))

(原谅这糟糕的语法高亮吧）

随后，使用 test_data.flush_buffer() 将输出缓冲区的内容写入文件以确保刚才所有的 input_writeln() 函数输出的内容全部都到了我们的输入文件里而不是缓冲区中。

随后，调用我们刚才写的 C++ 程序。现在问题有二：

1. 如何让这个程序向文件里输出？
2. 如何让这个程序知道它应该输出到哪里？

而第一个问题有无数种解答方案。大家在 CCF 系列比赛中应该已经很熟悉文件输入输出了；而第二个问题则需要略施小计。

众所周知，标准的 C++ 主函数是有参数的（如下）：

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

}

只不过我们平时把主函数的参数省略了而已。而这个 argc 和 argv 是什么东西呢？argc 是 argv 数组的大小，而 argv 是程序的所有外部参数，而外部参数平时只有一个，就是程序名本身。

我们不妨从此入手。在 Python 中带参数地调用可执行文件，然后在主函数内作出反应。修改 Python 代码如下：

n = randint(1, MAXN)
m = randint(n, MAXM)
graph = Graph.UDAG(n, m)
test_data.input_writeln(n, m)
test_data.input_writeln(graph.to_str(output = Edge.unweighted_edge))
test_data.flush_buffer()

opr = ".\get.exe " + "\"galaxy_" + str(id) + ".in\""
status = os.system(opr)

别忘了在 Python 文件开头添加 import os，在 Linux 环境下请把 .\get.exe 换为 ./get。

而此中的 opr 变量即是我们调用 get.exe 的命令。它形如：

.\get.exe "galaxy_2.in"

其中 .\get.exe 是运行 get.exe 的命令，而 "galaxy_2.in" 则是 argv 数组的第二个值，即 argv[1]。这样，我们就能够在 C++ 程序里取到这个值，从而打开对应的文件。

接下来我们在此附上添加了文件输入输出和主函数传参的 get.cpp 代码，大家可以对比添加前与这版本的差异。基于多样化文件输入输出的考虑（有些题目要覆写源文件，有些要在源文件后追加），这里使用 C++ 风格的文件输入输出流。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

int dg[MAXN];
queue<int> lst;
vector<int> e[MAXN];

int main(int argc, char* argv[])
{
    srand((unsigned)time(NULL));

    ifstream read;
    ofstream write;

    read.open(argv[1], ios::in);

    int n, m;
    read >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int u, v;
        read >> u >> v;
        e[u].push_back(v);
        dg[u]++;
        dg[v]++;
    }

    for (int i = 1; i <= n; i++)
    {
        if (dg[i] % 2) lst.push(i);
    }

    while (!lst.empty())
    {
        int u = lst.front(); lst.pop();
        int v = lst.front(); lst.pop();
        e[u].push_back(v);
        m++;
    }

    int typ = rand() % 2;
    if (typ == 1)
    {
        n++;
        e[1].push_back(n);
        m++;
    }

    read.close();

    write.open(argv[1], ios::out);
    write << n << " " << m << endl;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < e[i].size(); j++)
        {
            write << i << " " << e[i][j] << endl;
        }
    }
    write.close();
    return 0;
}

可以看到，本代码中采用的文件打开方式是 ios::out，这么做会覆写文件。若想在文件后追加内容，请使用 ios::app。

总结一下，笔者认为面对此种情况最快速的方法是用熟悉且功能强大的语言修改 CYaRon 造出的数据从而手动实现 CYaRon 不能实现的特殊性质并保证数据强度。当然也可以在完善功能之后 Pull Request，为 CYaRon 的开发提供自己的微薄之力。

同理，当出题人要求生成一些有特殊性质的数据时也可以采用这种方法。

为生成器提速

众所周知 Python 的常数巨大，在使用 CYaRon 造数据时会比 Testlib 慢很多，但胜在简单好写，不容易出锅。

这也是上文所述构造特殊性质时使用 C++ 的原因。当生成器过于复杂或者特殊性质过多且数据范围过大时（特别是时间紧张的情况下），Python 巨大的常数将会成为压垮你心态的最后一根稻草。所以第一个提速方法是：在需要大量枚举以构造数据时使用 C++ 等小常数语言以提高运行效率。但请注意如果您过于追求常数小导致生成器出现 UB 或者写锅了就得不偿失了。

而第二种方法文档里亦有讲述：使用 PyPy 而非 Python。

PyPy 是一个以 Python 编写的 Python 语言的 JIT 编译器。对于具有大量循环和重复操作的程序，使用 PyPy 可以让执行效率获得成倍的提升。—— CYaRon 文档

补锅

众所周知数据人不是在补锅就是在出锅的路上。这里提供一些调试技巧。

• 重新阅读一遍题面，确定自己没有少造某些内容。
• 仔细阅读文档，检查自己有没有搞错某函数的用法。
• 输出中间变量。CYaRon 使用专用的函数来进行文件输出，所以 print() 函数仍可实现输出到控制台的功能，十分方便。或者实在不济也可以写个枚举程序看看哪里不正常。
• 造一组小范围的数据，然后肉眼 debug。
• 检查一些容易踩坑的错误（比如字符串的大小写，输出带权图还是不带权图，数据范围有没有多打一个 0 之类的）。
• 更换编译器重新编译标程。
• 联系标程提供者和验题人确保标程无误。
• 仔细看一遍生成器和标程，确保没有调试时遗留的输出语句没有注释。
• 看看珂爱的标程提供者有没有贴心地为你写上 freopen，如果有的话把它删掉并友好地告知 ta 下次不要这么干了（会使每个输出文件里面都是 0）。
• 删了重写。

其他数据人需要考虑的方面

• Subtask 及分数配置：尽量通过编辑 config.yml 完成，便于统一管理。
• Special Judge：请出门左转 Testlib。

Reference

洛谷官方介绍帖
Github 项目地址
文档民间镜像