对拍

对拍介绍

对拍程序是比赛中自己检查算法的 bug、发现未考虑全的情况的一种好方法。

其一般由以下几部分组成：

1. 待检测程序 —— 需要检测问题的程序
2. 标程 —— 标准程序，如果过有正解，可以为正解的程序；若无正解，可以选择较小数据范围的暴力程序（保证正确性），能用朴素的办法解出有效的结果。
3. 数据生成器 —— 负责随机生成给定范围的输入数据进行测试的程序
4. 主程序 —— 可以控制生成测试数据，然后分别运行 标程 和 待检测程序，判断两个程序的结果是否一致，反馈出答案不一致的测试数据。

具体实现代码

这里我们以具体问题 为例子

注意： 使用的时候，需将待 检测程序， 标程，数据生成器，主程序 都编译为 .exe 文件后，运行 主程序 即可。

待检测程序

Solve.cpp，需要进行 debug 的目标代码。

标程

Std.cpp，一般为标准答案的程序，在比赛或其他情况下未知标准写法的情况时，也可以使用 暴力 方法产生仅仅适合小数据范围的程序，用于与自己的 待检测程序 产生的答案进行差异比较。

数据生成器

RandomData.cpp，用于产生测试数据进行输入。

注意： 若标程为暴力程序，注意产生合适的数据范围大小是否会超过该程序开的数组大小，或超出运行时间。

例如，有一个求第几项斐波那契数列的问题：

斐波那契数列的 $1-4$ 项为：$1, 1, 2, 3$。
其有 $n$ 个问题，每个问题询问第 $k$ 项斐波那契数列的值 模 $10^9 + 7$ 是多少。
其输入数据：
第一行输入一个整数 $n$，代表问题个数，后面 $n$ 行每行输入一个整数 $k$，代表询问第 $k$ 项的答案。

数据范围如下：

• $1\le n \le 10^6$
• $1\le k \le 10^6$

该问题的测试数据输入可以如下设计：

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

//大整数
mt19937_64 rd64((unsigned) time(0)); // 种子，可以选择时间作为seed
LL getBigRandom(LL a, LL b) {   //[a, b] 之间
    uniform_int_distribution<LL> dis(a, b); // 设置范围
    return dis(rd64);
}

//小整数
mt19937 myrand((unsigned) time(0));
int getRandom(int a, int b) {   //[a, b]之间
    return myrand() % (b - a + 1) + a;
}

int main() {
    int n = getRandom(1, 1000000);
    printf("%d\n", n);
    for (int i = 1; i <= n; i++) {
        int k = getRandom(1, 1000000);
        printf("%d\n", k);
    }
    return 0;
}

主程序

Check.cpp，用于产生多组测试用例，对待检查程序和标程的答案进行比较，找出存在差异的测试用例。

若某个测试用例没有通过，即两程序执行的输出存在差异，则其错误的 测试用例输入 即为当前的 std.in 文件中，对应的 标程的输出 在 std.out 中，待检查程序的输出 在 solve.out 中。

下面的写法为 Windows 中的检测程序，若为 Linux 或 MacOS 中，将 system 比较语句(14行)中的 fc 替换为 diff 即可。同时在 Windows 下 clock() 获取到的时间为 毫秒，而在后两者的系统中获取的时间为 秒，需要注意。

#include<bits/stdc++.h>

using namespace std;

int main() {
    for (int T = 1; T <= 100; T++) {
        system("RandomData.exe > std.in");         //随机产生测试数据
        double st = clock();
        system("Solve.exe < std.in > solve.out");  //执行待检查程序并计时
        double ed = clock();

        system("Std.exe < std.in > std.out");  //执行暴力程序或者标准程序

        if (system("fc solve.out std.out")) {    //判断待查程序和暴力程序的运行结果异同
            printf("Wrong Answer on test case #%d\n", T);
            return 0;
        } else {
            printf("Accepted, Test Case #%d, Cost Time %.0lfms\n", T, ed - st);
        }
    }
    return 0;
}