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;
}
鲁ICP备2025150228号