对拍，即将相同的数据输入两个不同程序，比对其输出结果。可以用于在ACM/OI等比赛中用暴力算法检测标算的正确性，寻找使程序出错的样例数据。

随机数生成器

要编写好用的对拍程序，首要的是要编写一个随机数生成器，便于产生多样化的数据。

朴素随机数生成器

相信很多人都见过下面这种写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//DataGenerator_naive.cpp
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;

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

    //以下代码可以生成10个随机整数
    int n = 10;
    for (int i = 1; i <= n; i++)
    {
		printf("%d ", rand());
    }

    return 0;
}

但是这样的写法有个问题，在Windows下time(NULL)获取的是自 19701970 年 11 月 11 日至今经过的秒数，也就是说同一秒内获得的随机数种子是一样的，即我们每秒只能获得一组有效的随机样例，这样的效率太低，不是我们可以接受的。

利用命令行随机数种子

事实上，Windows命令行自带了一个随机数生成器%random%，每次调用都可以获得一个不同的整数，能够作为随机数种子，可以将上面的程序改写一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//DataGenerator_cmd.cpp
#include <iostream>
#include <string>
#include <sstream>
#include <ctime>
#include <algorithm>
using namespace std;
stringstream ss;

int main(int argc, char *argv[])
{
    int seed = time(NULL);
    if (argc > 1) //如果有参数
    {
        ss.clear();
        ss << argv[1];
        ss >> seed; //把参数转换成整数赋值给seed
    }
    srand(seed);

    //以下代码可以生成10个随机整数
    int n = 10;
    for (int i = 1; i <= n; i++)
    {
		printf("%d ", rand());
    }

    return 0;
}

这里我们利用了main函数的传入参数，argc表示参数个数，argv[]表示每个参数的值，以字符串形势表示。

以下命令可以通过调用%random%，并传入DataGenerator_cmd.exe，使得每次运行都能获得不同的种子，并将生成的随机数写入in.txt，以供目标程序读取数据：

1
DataGenerator_cmd.exe %random% > in.txt

利用系统的加密秘钥生成器生成随机数

下面这个 WinRandom 类调用了系统的加密秘钥生成器，这个生成器调用内核生成秘钥，所以是硬件的真随机数，可将其写成头文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//WinRandom.h
#include <windows.h>
#include <wincrypt.h>
#include <assert.h>
class WinRandom
{
    HCRYPTPROV handle;

public:
    WinRandom()
    {
        handle = NULL;
        CryptAcquireContext(
            (HCRYPTPROV *)&handle, NULL, NULL,
            PROV_RSA_FULL, 0);
    }
    ~WinRandom()
    {
        if (handle != NULL)
            CryptReleaseContext(handle, 0);
    }
    bool randBuf(void *dest, int len)
    {
        if (handle == NULL)
            return false;
        return CryptGenRandom(handle, len, (BYTE *)dest);
    }
#define _(func, typ)                                \
    typ func()                                      \
    {                                               \
        typ ret = 0;                                \
        assert(randBuf((void *)&ret, sizeof(ret))); \
        return ret;                                 \
    }
    _(randInt, int)
    _(randLong, long long)
    _(randUnsigned, unsigned)
    _(randUnsignedLong, unsigned long long)
    _(randShort, short)
    _(randUnsignedShort, unsigned short)
    _(randChar, char)
    _(randUnsignedChar, unsigned char)
    _(randSignedChar, signed char)
};

将上面的程序再改写以下，调用WinRandom类，就可以实现真随机数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//DataGenerator_WR.cpp
#include <iostream>
#include <cstdio>
#include "WinRandom.h"
using namespace std;

int main()
{
    WinRandom R;
    //用 R.randInt() 来返回一个随机的int型变量

    //以下代码可以生成10个随机整数
    int n = 10;
    for (int i = 1; i <= n; i++)
    {
		printf("%d ", R.randInt());
    }

    return 0;
}

对拍程序

这里的对拍程序通过 system()函数在C++程序内执行命令行指令，你可以自定义目标程序位置和随机数生成器位置等：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//checker.cpp
#include <iostream>
#include <cstdio>
#include <string>
#include <windows.h>
using namespace std;

int main()
{
    int type;	//选择生成器类型
    printf("input random generator type:\n");
    printf("1: naive\n");
    printf("2: cmdRandom\n");
    printf("3: WinRandom\n");
    scanf("%d", &type);

    int t = 100000;
    string Std = R"("{标算位置}.exe")";
    string Mtd = R"("{你的程序位置}.exe")";
    string DataGenerator;
    if (type == 3)
        DataGenerator = R"("{WR生成器位置}\DataGenerator_WR.exe")";
    else
        DataGenerator = R"("{cmd生成器位置}\DataGenerator_cmd.exe")";
    string in_txt = "in.txt";
    string mtd_out_txt = "mtd-out.txt";
    string std_out_txt = "std-out.txt";
    while (t--)
    {
        if (type == 2)
            system((DataGenerator + " %random%" + " > " + in_txt).data());
        else
            system((DataGenerator + " > " + in_txt).data());
        // printf("%s\n", (in_txt + " < " + Mtd + " > " + mtd_out_txt).data());
        system((Mtd + " < " + in_txt + " > " + mtd_out_txt).data());
        system((Std + " < " + in_txt + " > " + std_out_txt).data());
        if (system(("fc " + mtd_out_txt + " " + std_out_txt).data()))
            system("pause");
    }
    return 0;
}

请参阅