对拍详解

对拍是算法竞赛中除了瞪眼法以外 最有效的 $debug$ 利器
它可以通过随机数据大体验证算法的正确性
比测大水样例有效多了

---

这里我拿洛谷P3628 [APIO2010]特别行动队（一道斜优板子）作为例题
要想对拍，首先你需要准备：

1. 一个写好的暴力（一定要保证正确）
2. 一个写好待测的正解
3. 一个datamaker
4. 一个checker

暴力：

写出暴力是对拍的必要条件
对于例题我们需要先写一个暴力 $dp$
代码：

#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int maxn=1e6+5;
int n,dp[maxn],a,b,c,sum[maxn];
inline ll read()
{ll ret=0;char ch=' ',c=getchar();while(!(c<='9'&&c>='0')) ch=c,c=getchar();while(c<='9'&&c>='0') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();return ch=='-'?-ret:ret;
}
signed main()
{n=read();a=read();b=read();c=read();for(int i=1;i<=n;i++) sum[i]=sum[i-1]+read();for(int i=1;i<=n;i++) dp[i]=-2e18;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++) dp[i]=max(dp[i],dp[j]+a*(sum[i]-sum[j])*(sum[i]-sum[j])+b*(sum[i]-sum[j])+c);printf("%lld",dp[n]);return 0;	
}

并起名为 $dp.cpp$

正解

然后我们写出斜优正解
代码：

#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int maxn=1e6+5;
int n,dp[maxn],a,b,c,sum[maxn],q[maxn];
inline ll read()
{ll ret=0;char ch=' ',c=getchar();while(!(c<='9'&&c>='0')) ch=c,c=getchar();while(c<='9'&&c>='0') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();return ch=='-'?-ret:ret;
}
int X(int i) {return 2*a*sum[i];}
int Y(int i) {return dp[i]+a*sum[i]*sum[i]-b*sum[i]+c;}
int deltaX(int i,int j) {return X(i)-X(j);}
int deltaY(int i,int j) {return Y(i)-Y(j);}
signed main()
{n=read();a=read();b=read();c=read();for(int i=1;i<=n;i++) sum[i]=sum[i-1]+read();for(int i=1;i<=n;i++) dp[i]=-2e18;int head=0,tail=0;for(int i=1;i<=n;i++){while(head<tail&&deltaY(q[head+1],q[head])>=sum[i]*deltaX(q[head+1],q[head])) head++;dp[i]=dp[q[head]]+a*(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+b*(sum[i]-sum[q[head]])+c;while(head<tail&&deltaY(q[tail],q[tail-1])*deltaX(i,q[tail])>=deltaY(i,q[tail])*deltaX(q[tail],q[tail-1])) tail--;q[++tail]=i;}printf("%lld",dp[n]);return 0;	
}

并命名为 $std.cpp$

datamaker

然后问我们就要写datamaker了
我们通过 $rand$ 函数（具体用法请自行百度）来造随机数据
代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a,b,c;
inline ll read()
{ll ret=0;char ch=' ',c=getchar();while(!(c<='9'&&c>='0')) ch=c,c=getchar();while(c<='9'&&c>='0') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();return ch=='-'?-ret:ret;
}
int main()
{srand(time(0));n=rand()%10000;a=rand()%4-5;b=rand()%20000000-10000000;c=rand()%20000000-10000000;printf("%d\n%d %d %d\n",n,a,b,c);while(n--) printf("%d ",rand()%100+1);return 0;
}

并命名为 $datamaker.cpp$

checker

最关键的就是 $checker$
它起到类似评测机的作用

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{ll ret=0;char ch=' ',c=getchar();while(!(c<='9'&&c>='0')) ch=c,c=getchar();while(c<='9'&&c>='0') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();return ch=='-'?-ret:ret;
}
int main()
{for(int i=1;i<=10000;i++){system("datamaker.exe>data.txt");system("dp.exe<data.txt>dp.txt");double st=clock();system("std.exe<data.txt>std.txt");double ed=clock();if(system("fc dp.txt std.txt")) {printf("WA\n");break;}else printf("AC #%d Time:%.3lfms\n",i,ed-st);}return 0;
}

然后我们运行 $checker$ 即可完成对拍
注意：我们每次改完正解后要重新编译！！！

这是在 $windows$ 环境下
在 $linux$ 环境下也类似
dp:

#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int maxn=1e6+5;
int n,dp[maxn],a,b,c,sum[maxn];
inline ll read()
{ll ret=0;char ch=' ',c=getchar();while(!(c<='9'&&c>='0')) ch=c,c=getchar();while(c<='9'&&c>='0') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();return ch=='-'?-ret:ret;
}
signed main()
{freopen("data.in","r",stdin);freopen("test.out","w",stdout);n=read();a=read();b=read();c=read();for(int i=1;i<=n;i++) sum[i]=sum[i-1]+read();for(int i=1;i<=n;i++) dp[i]=-2e18;for(int i=1;i<=n;i++)for(int j=0;j<=i;j++) dp[i]=max(dp[i],dp[j]+a*(sum[i]-sum[j])*(sum[i]-sum[j])+b*(sum[i]-sum[j])+c);printf("%lld",dp[n]);return 0;	
}

std:

#include<bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int maxn=1e6+5;
int n,dp[maxn],a,b,c,sum[maxn],q[maxn];
inline ll read()
{ll ret=0;char ch=' ',c=getchar();while(!(c<='9'&&c>='0')) ch=c,c=getchar();while(c<='9'&&c>='0') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();return ch=='-'?-ret:ret;
}
int X(int i) {return 2*a*sum[i];}
int Y(int i) {return dp[i]+a*sum[i]*sum[i]-b*sum[i]+c;}
int deltaX(int i,int j) {return X(i)-X(j);}
int deltaY(int i,int j) {return Y(i)-Y(j);}
signed main()
{freopen("data.in","r",stdin);freopen("std.out","w",stdout);n=read();a=read();b=read();c=read();for(int i=1;i<=n;i++) sum[i]=sum[i-1]+read();for(int i=1;i<=n;i++) dp[i]=-2e18;int head=0,tail=0;for(int i=1;i<=n;i++){while(head<tail&&deltaY(q[head+1],q[head])>=sum[i]*deltaX(q[head+1],q[head])) head++;dp[i]=dp[q[head]]+a*(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+b*(sum[i]-sum[q[head]])+c;while(head<tail&&deltaY(q[tail],q[tail-1])*deltaX(i,q[tail])>=deltaY(i,q[tail])*deltaX(q[tail],q[tail-1])) tail--;q[++tail]=i;}printf("%lld",dp[n]);return 0;	
}

datamaker：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a,b,c;
inline ll read()
{ll ret=0;char ch=' ',c=getchar();while(!(c<='9'&&c>='0')) ch=c,c=getchar();while(c<='9'&&c>='0') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();return ch=='-'?-ret:ret;
}
int main()
{freopen("data.in","w",stdout);srand(time(0));n=rand()%10000;a=rand()%4-5;b=rand()%20000000-10000000;c=rand()%20000000-10000000;printf("%d\n%d %d %d\n",n,a,b,c);while(n--) printf("%d ",rand()%100+1);return 0;
}

checker：

#include<bits/stdc++.h>
using namespace std;
int main()
{for(int i=1;;i++){printf("The result of No. %d Case is:  ",i);system("./datamaker");system("./std");system("./dp");if(system("diff std.out test.out")) {printf("Wrong Answer\n");break;}else printf("Accepted\n");}return 0;
}

最后：

对拍是个技术活，造数据时要考虑数据特性（比如树就需要拿并查集维护），如果时间不是很充裕不要强写对拍，这样只会得不偿失