本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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

\/\/暴力思路，枚举当前是星期几，挨个算那些日期是不是在周末。
#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$ 那你会修改自己的程序了吗？快来试试吧。

修改后的代码

#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对拍的使用