对拍

原理

对拍是算法练习中一种很常用、很有用的编程技巧，有很多种实现方法，并且脚本可以自己编写，整一套自己用得顺手的就好了，原理都是差不多的：

对拍模板

我自己习惯在Ubuntu下写代码，比较干净一点，所以用了一点时间，实现了一套对拍工具，用VS Code自带终端就可以轻易使用，但前提是装好了g++编译器。

对拍文件中有以下文件：

基础程序：

random.cpp -> data.in

sol.cpp -> data.out

bf.cpp -> data.ans

check.cpp

控制脚本：

op.sh

mr.sh

test.sh

run.sh

ga.sh

ac.sh

数据文件：

三个data开头的文件

data.in

data.out

data.ans

数据生成器random.cpp

#include <cstdlib>
#include <ctime>
#include <stdio.h>

int random(int n){
    return (long long)rand() * rand() % n;
}

int main(){
    freopen("data.in","w",stdout);
    srand((unsigned)time(0));

    //在这里写程序，利用random()生成各种随机数
    //后面会有各种类型的随机数模板代码
    //往下看

    return 0;
}

暴力程序bf.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const double eps = 1e-5;
const int INF = (int)1e9;
const ll MAXN = 1e5 + 10, MOD = 1e9 + 7;
#define PI acos(-1)



int main(){
    freopen("data.in","r",stdin);
    freopen("data.ans","w",stdout);

    //像平常一样编程即可，不需要在意效率，只需要保证能输出正确结果
    //当然输出的时候也要保证格式的正确性
    //上面两句freopen语句是为了从data.in读入数据
    //并让输出的数据写入data.ans中

    return 0;
}

准备上交的程序sol.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
const double eps = 1e-5;
const int INF = (int)1e9;
const ll MAXN = 1e5 + 10, MOD = 1e9 + 7;
#define PI acos(-1)



int main(){
    // ios::sync_with_stdio(false);
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);

    //上面两句freopen语句是为了从data.in读入数据
    //并让输出的数据写入data.out中

    //system("pause");
    return 0;
}

接下来是对拍程序，用脚本文件也可以写，但用C++的话，可以获取更精确的时间以及其它信息。

对拍程序check.cpp

#include <cstdio>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(){
    //若需要改变测试次数，修改T的范围即可
    for (int T = 1; T <= 1000; T++){
        //执行random文件
        system("./random");
        //记时并执行准备上交的程序
        double st = clock();
        system("./sol");
        double ed = clock();
        //执行暴力程序
        system("./bf");
        //检验两个程序输出的结果是否相同
        if (system("diff data.out data.ans")){
            printf("Wrong Answer\n");
            return 0;
        }
        else{
            printf("Accepted, Case: %d, Time:%.0lfms.\n", T, ed - st);
        }
    }
    return 0;
}

脚本文件最常用的是op.sh，用于查看输出内容、调试程序。

g++开头的代码是编译对应的文件，并生成可执行文件，非常重要，一定要有可执行文件才能在终端中执行，即使不用VS Code，用其它的编辑器，也一样要生成，在Window下生成的是.exe文件。

另外，.sh脚本程序的运行方式是在终端输入bash xxx.sh。

g++ sol.cpp -o sol
./sol < data.in > data.out
cat data.out
echo ""

然后是mr.sh，用于测试写好的数据生成器，在终端运行后直接在终端显示出生成的数据，可以查看是否符合标准。

g++ random.cpp -o random
./random > data.in
cat data.in
echo ""

test.sh这个文件顾名思义就是一个测试文件，专门用来比对题目的样例输入输出，首先在把题目样例输入复制到data.in中，然后把样例输出复制到data.out下，运行即可。

g++ sol.cpp -o sol
./sol < data.in > data.out
diff data.out data.ans
if [[ $? = 0 ]];then
    echo "Accepted"
fi

run.sh这个文件不调用随机生成数据的程序，是单次检查，自己手动输入数据，然后分别运行暴力程序和待上交的程序，比对输出结果。

手动输入的方式是，打开data.in，然后按照格式输入，或者直接复制样例过来，如何运行run.sh即可，若输出结果没问题，则会显示Accepted，很爽，否则显示正确的和错误的输出对比。

这个程序如果不熟悉的话，可能会和上一个test.sh脚本混淆，其实区别在于test.sh中，我已经知道了输入和正确的输出，但run.sh我只有输入，并不知道正确的输出。

这个脚本可以配合mr.sh使用。

g++ sol.cpp -o sol
g++ bf.cpp -o bf
./bf < data.in > data.ans
./sol < data.in > data.out
diff data.out data.ans
if [[ $? = 0 ]];then
    echo "Accepted"
fi

ga.sh脚本只运行暴力程序，得到正确的结果。

这个脚本也可以配合mr.sh使用。

g++ bf.cpp -o bf
./bf < data.in > data.ans
cat data.ans
echo ""

ac.sh文件是完整的对拍脚本，通过调用check.cpp，所有文件都按照要求执行。

g++ sol.cpp -o sol
g++ bf.cpp -o bf
g++ random.cpp -o random
g++ check.cpp -o check
./check

最后是三个data文件

data.in是输入算法程序的输入，也就是随机数据生成程序的输出。

data.out是待上交文件的输出。

data.ans是暴力程序的输出。

对比是对比data.out和data.ans的内容。

使用方法

尽管在上面已经提到了部分文件的用法，但这里还是来一个小小的总结吧。

首先在sol.cpp中写好自己的算法程序。

如果只是想看程序的输出，或者在中间输出某些变量，可以调用op.sh，可以将输出显示在终端上，因为这套程序并没有配置调试环境，所以用输出变量的方式DeBug是挺好的方法。

如果是测试题目中给出的样例：把输入样例复制到data.in，样例输出复制到data.ans，然后运行test.sh，看结果，样例过不了那就不用往下了。

如果发现有问题，但代码看起来又找不到什么错误，就在bf.cpp中写一个保证正确的低效率程序，接下来可以正式使用对拍。

如果要自己手动输入数据对拍，可以在data.in中输入要程序的输入样例，接着运行run.sh。

如果要自动生成数据对拍，则先要设计一个随机数据生成器，注意输出格式也要一致，然后可以运行mr.sh查看生成的数据是否符合要求。确认无误后运行ac.sh，默认生成$1000$组数据，若要修改则在check.cpp中修改$T$的取值范围。

test.sh和run.sh的区别在于前者没有调用暴力程序，使用的是用户手动输出的结果来验证，后者使用的正确结果是用暴力程序生成的。另外，若要重新生成一次性的随机数据，可以调用mr.sh。

如果只想生成一些保证正确的结果，可以调用ga.sh输入可以手动输入或者生成随机数。

.sh脚本文件中的diff命令有很多选项，diff -w可以忽略空格进行比较，更多用法可以查资料。

其实暴力程序不一定是自己手写的暴力，在练习的时候，可以把别人的AC代码放到bf.cpp里面去。

命名方法

• sol.cpp意为solution
• bf.cpp意为brute force
• random.cpp意为生成随机数
• check.cpp意为检测程序
• op.sh意为output
• mr.sh意为make random，生成随机数
• test.sh意为刚刚写完程序，测试一下样例
• run.sh意为写好了暴力程序，对拍一下
• ga.sh意为get answer
• ac.sh意为一定会AC的
• data.in意为输入
• data.out意为输出
• data.ans意为answer，也就是这里面放一定是正确的

文件名都可以改，写出来只是为了让逻辑更清楚。

每个脚本的开头都不一样，在终端中使用TAB键可以自动补全。