OIer对拍的使用

wflengxuenong · 2024-03-31 10:06:52 · 个人记录

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
```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;
}