对拍简介

目录
  • Windows 下
    • 简介
    • 随机数据
    • 脚本
    • 运行
    • 另外方法
  • NOI Linux 下
  • 总结

Windows 下

简介

对拍是一种常用的竞赛技巧，主要是在 NOI 赛事中适用的。

目的是在无法得知评测结果的情况下，防止挂分。（例如你样例都过了，但是其实代码有大坑）

其原理是制造随机数据并写一个暴力，然后进行结果比对，倘若有差异则你成功的造出来一组 Hack 数据。

当然前提是你的暴力确定没有问题。

随机数据

对拍的核心内容，主要用到 rand() 与 srand() 两个函数。

代码如下。

#include 
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  
#include  
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"<

就是酱紫。

  1. 用 Dijkstra.exe 当做运行程序。（即你的正解）

  2. 用 Floyd.exe 当做暴力程序。

运行

以下给出我的两份代码。

Dijkstra：

#include
#include
#include
#include
#include
#include
#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 >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
#include
#include
#include
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;
}

可见这个暴力确实很暴力

然后就是愉快的对拍时间，结果大概是酱紫：

批注 2020-04-03 213456.png

当然如果想要知道错误是什么样子...自己故意放一个错误的代码吧。

另外方法

是这个样子的。

脚本：

#include
#include
#include
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
#include
#include
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
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
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;
}

运行结果与上图差不多，就不上图片了。

NOI Linux 下

考试的时候，我们用的是可爱的 NOI Linux，那么怎么对拍呢？

其实大体与上面介绍的对拍方法几乎一模一样，只有运行脚本有一些区别。

#include
using namespace std;

int main(){
    for(int i=1;i<=n;i++){
        system("./make");// 注释 1
        system("./std > std.out");// 注释 1
        system("./my > my.out");// 注释 1
        if(system(diif -bB std.out my.out)){// 注释 2
            printf("error in %d\n",i);
            return 0;
        }
        else{
            printf("Accept %d\n",i);
            system("sleep 1");// 注释 3
        }
    }
    return 0;
}

注释：

  1. 与 Windows 系统不同，Linux 系统的打开文件用的是 ./文件名。
  2. 采用忽略行位空格与换行，一般考试都是采用这种方法进行比较。
  3. 与 Windows 系统不同，Linux 系统的时间是以 “秒” 为单位（Windows 是用 ms），所以要减少无意义的对拍，即 “睡眠 1 秒”。当然，它的效率相较于 Windows 下较为逊色，只能 1 秒 1 拍。

总结

考试必备技巧，防爆 0 神奇的介绍就到此为止啦。

推荐两篇博文：

  1. 。
  2. 给NOI Linux的小白们。

完结撒花。

随笔

相关

python学习随笔day15

工作随笔

这是小兜兜的第一篇随笔

第八次随笔

elastic-search随笔

java学习随笔源码day01

周末随笔_有关变化

深夜随笔(11.28)

openspiel 随笔 05.05

单元测试使用Mock随笔

第一篇随笔

刘一辰的软件工程随笔

标签