如何在 Windows 下对拍

准备以下四个文件：

1. 不知正确性的程序 my.exe。
2. 保证正确的程序 std.exe。
3. 数据生成器 gen.exe。
4. 批处理脚本 pai.bat：

:loop
    gen.exe >gen.in
    std.exe <gen.in >std.out
    my.exe <gen.in >my.out
    fc my.out std.out
if not errorlevel 1 goto loop

运行 pai.bat 并查看结果。

注意：my.cpp 的代码修改完之后一定要重新编译！否则对拍的还是原来的错误程序的 exe。

随机数生成

生成随机数不建议使用 srand 与 rand 这种老式随机数。在 C++11 以上，可以使用 mt19937。

（以下代码假设开启万能头且 using namespace std;）

随机 32 位无符号整数

    mt19937 Rand(time(0));
    cout << Rand() << endl;

随机 64 位无符号整数

    mt19937_64 Rand(time(0));
    cout << Rand() << endl;

在区间 $[l,r]$ 内随机一个数

    uniform_int_distribution<int> distr(l, r);
    cout << distr(Rand) << endl; // Rand 为一个随机数生成器

随机打乱一个序列

    shuffle(a+1, a+n+1, Rand); // Rand 为一个随机数生成器

随机生成各种结构

生成一棵树

枚举点 $u$，在某个范围内 rand 一个 fa，比如 $[1,1]$ 或 $[u-10,u)$ 等。

可以方便地造出链和菊花，以及普通的期望树高为 $O(\log n)$ 的树。

生成一个图

随机加边。注意重边和自环。

生成一个连通图

生成一棵树，然后随机加边。

生成一个 DAG

生成一个排列，从后往前加边。

生成一个强连通图

生成一个环，然后随机加边。