对拍详解

对拍详解 ——HM

对拍是家中写题、考场中写题判断自己的程序答案是否正确的一种技巧，当打完时可以写一个对拍程序来判断一下自己的代码。大体思路就是：写一个暴力，写一个数据生成器，将生成的数据分别输入在你的正解与暴力中，因为暴力的程序一定对，所以只要将暴力得来的答案与你写的代码得到的答案相比较，若有不对立刻跳出，从而做到保证程序答案的正确性。

对拍以下几点不适用：

1、对拍只能保证正确性，不能保证最优性，即只能保证答案正确，不能保证TLE或MLE等。

2、对拍无法使正解就是暴力的题目答案正确。

下面来讲如何实现对拍：

首先写一个正解、一个保证答案正确的暴力（在家做题可以贴一个题解，答案正确就行），再写一个数据随机生成器（下面会有样例），然后背一个对拍程序（cpp文件），编译一遍正解、暴力、数据生成器生成3个exe，将上述所有放入一个文件夹中（建议不要放在桌面），运行对拍程序直接根据运行结果判断即可。

有点难懂，举个例子：

假如我编了一个Dijkstra优先级队列优化最短路（顺便宣传一下自己的博客），不能确定正确性，于是编了一个Floyd，并写了一个对拍程序、一个数据生成器，将Dijkstra、Floyd分别命名为Dijkstra.cpp、Floyd.cpp，按照输入格式编了一个数据生成器：

#include <bits/stdc++.h>
using namespace std;int main()
{srand(time(0));int n,m,S;n=rand()%1000+1;m=rand()%2000+1;S=1;printf("%d %d %d\n",n,m,S);for (int i=1;i<=m;i++){int u,v,w;u=rand()%n+1;v=rand()%n+1;w=rand()%1000000000;printf("%d %d %d\n",u,v,w);}return 0;
}

解释一下rand()函数用来生成随机数，但若不加srand(time(0))这个语句，则所有生成的数据都是一样的，就没有意义了；随机数模一个数在加一个数可以确定其范围，比如随机数x，x=x%n+1可以使x在1到n的范围内。其实这就是将原来的输入全部改为输出即可。

然后编一个对拍程序：

#include<iostream>  
#include<windows.h>  
using namespace std;  
int main()  
{  int t=10;while(t)  {  t--;  system("data.exe > data.txt");  system("Floyd.exe < data.txt > Floyd.txt");  system("Dijkstra.exe < data.txt > Dijkstra.txt");  if(system("fc Dijkstra.txt Floyd.txt"))   break;  }  if(t==0) cout<<"no error"<<endl;  else cout<<"error"<<endl;  return 0;  
}

变量t指的是你要测试数据的组数，将数据生成器命名为data.cpp，按上面的程序打一遍就行了，大概意思就是运行一遍另外三个程序exe，将数据生成器生成的数据放在data.txt中，标程与暴力分别读入数据，并进行比较，若不同，则直接跳出，此时t未减到0，故最后判断出错误，因为“fc”函数，会将两个程序的输出打印出来。

全部编译一遍，效果如下图所示