对拍是一种常用的竞赛技巧，主要是在 NOI 赛事中适用的。
目的是在无法得知评测结果的情况下，防止挂分。（例如你样例都过了，但是其实代码有大坑）
其原理是制造随机数据并写一个暴力，然后进行结果比对，倘若有差异则你成功的造出来一组 Hack 数据。
当然前提是你的暴力确定没有问题。
对拍的核心内容，主要用到 rand() 与 srand() 两个函数。
代码如下。
#include <bits/stdc++.h>
using namespace std;
int main()
{
srand(time(0));//让若去掉这一行的话，就无法达到随机数据。
int n,m,S;
n=rand()%100+1;
m=rand()%200+1;
S=1;
printf("%d %d\n",n,m);//制造有向图。
for (int i=1;i<=m;i++){
int u,v,w;
u=rand()%n+1;
v=rand()%n+1;//范围为 0~n
w=rand()%1000000;//范围为 0~1000000-1
printf("%d %d %d\n",u,v,w);
}
return 0;
}
以上是 最短路模板 的随机数据代码。
其实很容易理解的啦。
这是将所有代码连接起来的重要程序，全部写好之后，在这里查看运行结果。
#include<iostream>
#include<windows.h>
using namespace std;
int main()
{
int t=50;
while(t)//代表对拍次数。
{
t--;
system("data.exe > data.txt");
system("Floyd.exe < data.txt > Floyd.txt");
system("Dijkstra.exe < data.txt > Dijkstra.txt");
if(system("fc Dijkstra.txt Floyd.txt")) break;
}//以上请背下来。（也没有什么更好的方法啦）
if(t==0) cout<<"Accept"<<endl;
else cout<<"Wrong Answer"<<endl;
return 0;
}
就是酱紫。
用 Dijkstra.exe 当做运行程序。（即你的正解）
用 Floyd.exe 当做暴力程序。
以下给出我的两份代码。
Dijkstra：
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#define N 100010
#define M 1000010
#define maxd 1061109567
using namespace std;
int n,m;
int head[N],dis[N],cnt=0;
bool use[N];
struct node{
int next,to,val;
}edge[M];
priority_queue<pair<int,int> >q;
//为了避免重载小于号。
//pair的first用于存储dis[]的相反数（变小根堆），second用存储编号。
void addedge(int x,int y,int z){
cnt++;
edge[cnt].next=head[x];
edge[cnt].to=y;
edge[cnt].val=z;
head[x]=cnt;
return;
}
void dij(){
for(int i=1;i<=n;i++) dis[i]=maxd;
memset(use,false,sizeof(use));
q.push(make_pair(0,1));
dis[1]=0;
while(!q.empty()){
int now=q.top().second;
q.pop();
if(use[now]) continue;
use[now]=true;
for(int i=head[now];i;i=edge[i].next){
int y=edge[i].to;
int z=edge[i].val;
if(dis[y]>dis[now]+z){
dis[y]=dis[now]+z;
q.push(make_pair(-dis[y],y));
}
}
}
return;
}
int main(){
scanf("%d %d",&n,&m);
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&u,&v,&w);
addedge(u,v,w);
}
dij();
for(int i=1;i<=n;i++) printf("%d ",dis[i]);
//system("pause");
return 0;
}
Floyd：
#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=1000010;
int n,m,tot;
int edge[N][N];
int main(){
scanf("%d %d",&n,&m);
int u,v,w;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&u,&v,&w);
edge[u][v]=w;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(edge[i][j]>edge[i][k]+edge[k][j])
edge[i][j]=edge[i][k]+edge[k][j];
for(int i=1;i<=n;i++){
printf("%d ",edge[1][i]);
}
return 0;
}
可见这个暴力确实很暴力
然后就是愉快的对拍时间，结果大概是酱紫：
当然如果想要知道错误回事什么样子...自己故意放一个错误的代码吧。
是这个样子的。
脚本：
#include<cstdio>
#include<cstdlib>
#include<ctime>
using namespace std;
int main(){
for(int T=1;T<=100000;T++){
system("E:\\random.exe");
double st=clock();
system("E:\\sol.exe");
double ed=clock();
system("E:\\bf.exe");
if(system("fc E:\\data.out E:\\data.ans")){
printf("Wrong Answer");
}
else printf("Accepet,测试点 #%d,用时 %.0lfms\n",T,ed-st);
}
return 0;
}
数据生成器：
#include<cstdlib>
#include<ctime>
#include<cstdio>
using namespace std;
int a[100010],b[100010];
int random(int n){
return (long long)rand()*rand()%n;
}
int main(){
freopen("data.in","w",stdout);
srand((unsigned)time(0));
int m=20;
printf("%d %d\n",random(m),random(m));
fclose(stdout);
return 0;
}
来个暴力：（这也叫暴力？）
#include<cstdio>
using namespace std;
int main(){
freopen("data.in","r",stdin);
freopen("data.ans","w",stdout);
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",a+b);
fclose(stdin);fclose(stdout);
return 0;
}
放个错误代码：
#include<cstdio>
using namespace std;
int main(){
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",a+b);
if(a+b==20) printf("hahaha\n");//多了一行...
fclose(stdin);fclose(stdout);
return 0;
}
运行结果与上图差不多，就不上图片了。
Windows 下的对拍（但是考试是 NOI Linux 呀），所以...有待更新。未完待续。
原文：https://www.cnblogs.com/lpf-666/p/12629151.html