1.何为对拍？

对拍：通过暴力程序去验证优化后的程序是否正确，称之为对拍（优化后的程序不知道正确性，但是可以通过暴力程序去验证优化后的程序是否正确）

2.什么时候用对拍？

a.没有测试数据的情况。
b.可以网络评测，但交上去后不知道自己错在哪里的的情况。比如ABC347的C题。很多同学错了几遍也找不到错误的原因。

3.怎么写对拍？

需要准备的原材料： - a.待检验的程序。 - b.一个保证正确的暴力程序 - c.数据生成器

先生成小数据，大数据不利于查错，小数据无错的情况，再试试边界数据等特殊情况。都过的话再测试大数据。 - d.对拍程序

把这四个程序都编译完成，生成EXE文件。

4.实战演练

例题：ABC347C

a.待检验的程序。zhyt的C题代码，总是错一个点。文件名abc347c.CPP

#include <bits/stdc++.h>
using namespace std;
#define TRACE 1
#define tcout TRACE && cout

#define int long long
int n,a,b;
int x[1000005];
signed main()
{
     cin>>n>>a>>b;
     for(int i=1;i<=n;i++)
     {
         cin>>x[i];
         x[i]%=(a+b);
         /*if(x[i]==0)
         {
             x[i]=a+b;
         }*/
     }
     sort(x+1,x+n+1);
     if(x[n]-x[1]+1<=a){
         cout<<"Yes";      
     }    
     else{    
         cout<<"No";
     }
    return 0;
}

b.一个保证正确的暴力程序，文件名abc347c-baoli.cpp

//暴力思路，枚举当前是星期几，挨个算那些日期是不是在周末。
#include <bits/stdc++.h>
using namespace std;
#define TRACE 1
#define tcout TRACE && cout

#define int long long
int n,a,b;
int x[1000005];
bool check(int k){
    for(int i=1;i<=n;i++){
        if((k+x[i])%(a+b)>=a)return false;
    }
    return true;
}
signed main()
{
     cin>>n>>a>>b;
     for(int i=1;i<=n;i++)
     {
         cin>>x[i];
         x[i]--;
         x[i]%=(a+b);
     }
     for(int i=0;i<a+b;i++){
         if(check(i)){
             cout<<"Yes";
             return 0;
         }
     }
     cout<<"No";

    return 0;
}

c.数据生成器

#include<bits/stdc++.h>
using namespace std;

int main() {
    srand((int)time(NULL));
    int n=rand()%4+2;
    int a=rand()%5+1,b=rand()%5+1;
    cout<<n<<" "<<a<<" "<<b<<endl;
    for(int i=1;i<=n;i++){
        cout<<rand()%(a+b)+1<<" "; 
    }    
}

d.对拍程序

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

int main()
{   long s,t;
    while(1){
        system("cls");
        do{
            system("makedata.exe> try.in"); //data是数据生成程序
            s=clock();
            system("abc347c.exe< try.in > try1.out");  //a是要交的程序
            t=clock();
            system("abc347c-baoli.exe< try.in > try2.out");  //b是正确的程序
            if(system("fc try1.out try2.out > nul"))
                break;
            else printf("AC time: %ldms\n",t-s);
        }while(1);
        printf("WA time: %ldms\n",t-s);  //运行时间 
        system("fc try1.out try2.out");
        system("pause>nul");
    }
    return 0;
}

运行检验

本次出现的结果如下： ``` AC time: 367ms AC time: 254ms AC time: 129ms AC time: 131ms AC time: 181ms AC time: 129ms WA time: 136ms 正在比较文件 try1.out 和 TRY2.OUT * try1.out No * TRY2.OUT Yes


- 找出错误数据：然后我们打开try.in文件看看

2 3 4 7 6

## 错误调试
现在可以发现0和6的差值>=a,但也是可以都安排在休假范围内的。，错误的原因是要转圈看是否可以都在假期范围内。
- $x_1,x_2,...x_n$,这时候$x_n-x_1+1$
- $x_2,x_3,...x_n,x_1$，这时候$x1-x_2+1$,排序后会$\leq 0$,因此需要再加上$a+b$.

变换到一般话的情况

- $x_{i+1},...x_n,x_1,...x_i$,这时候判断 $x_i-x_{i+1}+1+a+b \leq a$
那你会修改自己的程序了吗？快来试试吧。

## 修改后的代码

```cpp
#include <bits/stdc++.h>

using namespace std;

#define TRACE 1
#define tcout TRACE && cout

#define int long long
int n,a,b;
int x[1000005];
signed main()
{
     cin>>n>>a>>b;
     for(int i=1;i<=n;i++)
     {
         cin>>x[i];
         x[i]%=(a+b);
     }
     sort(x+1,x+n+1);
     if(x[n]-x[1]+1<=a){
         cout<<"Yes";
          return 0;
     }
     else {
         for(int i=1;i<n;i++)
             if(x[i]+a+b-x[i+1]+1<=a){ 
             cout<<"Yes";
              return 0;
         }
     }        
    cout<<"No";

    return 0;
}

数据生成器

参考链接

lxn的博客

博客

OIER对拍的使用