什么？你还在用 C++ 出数据

在ACM JB *CPC 系列的比赛中，出题是非常关键的一环。作为出题人，题出得不好，就会被喷(?)。出题除了需要脑洞，还需要严谨的数据。如果数据错了/水了，后果就是出题人被选手吊起来打。

本人从大二上学期的新生选拔赛开始给学校的各类校赛(?)出题，也在现场/赛后踩了一些坑。因此总结一些出题(主要是造数据)的姿势，以供参考。

早期的实践 - 错误示范

一开始当然是 C++ 选手的沙雕操作: rand, freopen，然后再手动加几个很小很边界的人肉数据点 hack 一些能想到的沙雕写法。

这么搞很显然有弊端。首先是没法保证人肉数据点的正确性，就算是正确的，可能还是不够强。其次是麻烦，跑一把只能出一组数据，然后还要改freopen里的文件名。于是导致了数据只有一组

此外，当时还是个 Windows 用户。众所周知，rand生成的随机数最大值RAND_MAX是 library-dependent 的，在 Windows(MinGW) 下是 32767，因此跑不出比较大的随机数。

那个时候虽然知道这个 feature，但是解决方法比较沙雕: rand()*rand()。这显然变成了一个分布不均匀的随机，例如 19260817 出现的概率为 0。其实更好的解决方法是(rand()<<16)+rand()，不过总的来说使用 C++ 出数据是不推荐的做法。

当然，有一个场景必须要这么做——省赛(及其他现场赛 Windows 环境或没有 Python 的情况下)需要对拍的时候。这个时候，建议使用mt19937，还是比较方便的，起码不用考虑rand大小的问题。这也说明，出数据不一定是为了出题，可能还是为了过题。

题外话，从主办方的角度来说，现场赛使用 Windows 环境可能是为了萌新友好，不过个人还是希望明年我们办省赛的时候给选手们提供 Ubuntu 的标准现场赛环境(来自 Vim & Python 重度依赖患者的 flag?)

比较标准的姿势(大概)

发现 C++ 不好用的时候，接下来基本上就会想到 Python。随机数据import random一把梭，并且还有方便的列表操作 api。接下来以今年校内 C4 选拔赛原题tr为例，说明一个大致的出题流程。

首先是准备数据生成器，我这边一般命名为gen.py

1
2
3
4
import random
s="qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM1234567890/. "
for i in range(random.randint(1,100)):
  print(''.join([random.choice(s)for j in range(random.randint(1,100))]))

然后是用来读输入跑输出的程序，一般是标程，不过这题其实出得挺偷懒的，标程work.sh如下。显然这题的标题就是这么来的

1
2
#!/bin/bash
tr A-Z a-z

之后拿脚本gen.sh批量产出输入输出数据，比如搞个五组。

1
2
3
4
5
6
#!/bin/bash
for ((i=1;i<=5;i++));
do
python3 gen.py > $i.in
./work.sh <$i.in >$i.out
done

至此，我们当前目录下会有三个文件: gen.py, work.sh, gen.sh。当然这个work.sh纯属偷懒产物，一般的话还是好好拿 C++ 什么的写标程，然后编译得到可执行文件，比如g++ work.cpp -o work，然后上述gen.sh内的work.sh也相应改成可执行文件work。注意，这里的标程和数据生成器都不需要文件输入输出，直接走标准输入输出就好了。

基本的三件套到位，就可以在终端跑了。这里首先要加一波执行的权限。

1
2
$ chmod +x work.sh  # 偷懒产物，可忽略
$ chmod +x gen.sh

然后执行脚本，大功告成。

1
$ ./gen.sh

对于像校内 C4 选拔赛这样的需要 OI 赛制的，也可以微调一下gen.py，比如这题把空格去掉再跑一把形成另一批输入数据，酌情放点部分分给选手。此处就不再赘述了。

后来的偷懒方法

之后的好几场比赛，都是组的比较急，有的时候是比赛还有一周开始，但是我们还是一个题都没出的状态。所以就有了一种又快又不容易出锅的偷懒方法——利用好 Special Judge

目前，我校的 oj，如果题目是 spj 的，数据只需要提供.in文件，之后额外提供 spj 代码即可。显然，输出数据有没有出锅，肉眼还是比较难看出来的，但是 spj 代码就比较容易 review。出数据的流程和之前几乎没什么区别，去掉work的部分就可以了。这就意味着，标程有的时候就不需要写了(?)，例如玄学、BA、Arithmetic Sequence，就都是这么来的。

出题人自验的过程，也就是看一下 spj 代码有没有肉眼可见的 bug，不需要担心输出数据和输入数据是不是对不上了。之后丢给人验题，能过就行了

至于什么是肉眼可见的 bug，只能靠经验自由发挥了。以下举两个例子

之前现场出过的一个锅是，题目给 n、m 和长度为 m 的一个数组 a，spj 大概要判一个长度为 x(选手给出)的数组 b 是否满足$∑b_{a_i}$可以被 n 整除。当时有选手提交的代码就是只输出了一个 0，结果 spj 返回 Accepted。原因是 spj 虽然判了 x 是否比 m 大，但是没判 x 是否$\le 0$。至于现场修锅，比较曲折，大概是线上改库把人家的 Accepted 退回，题数--，手算一下去掉这题的罚时，然后再去通知人家。

还有一个锅，是在比赛结束后发现的，因为没有选手成功触发。这个问题首先其实和出题流程没有什么太大关系，是题目需要输出小数，根据精度判断是否正确。然后发现如果输出是NaN，spj 返回 Accepted。这种问题其实就比较状况外了，然后查之前的题有没有相同的问题，也是有些题有有些题没有。不过还是建议以后这种情况先用std::isnan判一下

总之，这种偷懒的方法还需要比较完善的 review 流程需要用ctf选手的目光去审计spj代码，可以在熟悉的情况下适当使用，正常情况下还是用上一部分所述的方法造数据。

附录1 如何把custoj上的题搬运到牛客

貌似上次留了这个flag，补档。挂题要用的牛客号在我这，有需要可以联系我，或者直接找牛客重置。

搬运题面的时候，可能会涉及到 latex 公式。因为我们出题一般都是 markdown 格式内嵌 latex，所以就直接点插入公式，粘贴全部的 markdown，再微调格式即可。

数据分为两种。没有 spj 的，直接搬过去就行了。有 spj 的，首先要新建对应数量的.out文件，内容随意，spj 不用到就行。之后修改 spj 代码，按牛客的要求将文件名写死。一般的具体做法是把 spj 代码中 main 里以下代码块(一般从18行起)

1
2
3
4
5
6
if(argc != 3){
    printf("Usage: spj x.in x.out\n");
    return ERROR;
}
input = fopen(args[1], "r");
user_output = fopen(args[2], "r");

改成

1
2
input = fopen("input", "r");
user_output = fopen("user_output", "r");

这样就能很方便地把 custoj 里的题目搬运到牛客上了。办个重现赛什么的还是很方便的

附录2

贵校什么时候考虑接入polygon啊

贵校什么时候校赛考虑用DomJudge啊