【實用】關于Ubuntu下的對拍程式

學了這麼久的OI還不會對拍，下定決心準備學對拍，上網一搜，全是在Windows下對拍的*.bat*檔案，然而Ubuntu表示水土不服，~~竟然有度娘搜不到的東西，~~最後還是找同機房cgz神犇要的對拍程式，衷心感謝

關于對拍

對拍可以找出自己找不出來的一些問題，有時候應該是大多時候樣例太水了，比如輸入1，輸出2，對拍自己出資料自己測，還可以控制資料範圍

如何對拍

對拍有四個程式，分别是

①自己的程式 -----正確性未知

②暴力程式 --------保證正确性卻不保證速度

③資料生成器 -----生成輸入資料

④對拍程式 --------用于重複執行對拍流程

假設 1. c p p 1.cpp 1.cpp為自己的程式， 2. c p p 2.cpp 2.cpp為标程或暴力， m a k e . c p p make.cpp make.cpp為資料生成器， d p . c p p dp.cpp dp.cpp為對拍程式

前兩個程式中應分别使用如下檔案輸入輸出：

1.cpp

freopen("in","r",stdin);
freopen("1.out","w",stdout);
           

2.cpp

freopen("in","r",stdin);
freopen("2.out","w",stdout);
           

資料生成器應使用srand語句以保證每次生成的資料不同，并保證資料生成的格式與題目要求一緻：

srand(time(0));
或
srand(time(NULL));
或
srand(你的生日);
           

對拍程式：

#include<bits/stdc++.h>
using namespace std;
int main(){
	int c=0;
	do{
		if(c)printf("#%d AC\n",c);
		++c;
		system("./make");
		system("./1");
		system("./2");
	}while(!system("diff 1.out 2.out"));
	printf("#%d WA\n",c);
	return 0;
}
           

例

對拍模闆以 [HAOI2006]受歡迎的牛為例題

1号為待測程式

2号為暴力程式||标程

make為資料生成器

dp為對拍程式

注意倆程式輸出格式必須相同，不省略行末空格，文尾回車

感謝cgz神犇提供dp模闆

十分美觀的 待測程式

#include<bits/stdc++.h>
using namespace std;
#define cl(x) memset(x,0,sizeof(x))

template <typename _Tp> inline void read(_Tp &x){
	char c11=getchar();x=0;bool booo=0;
	while(c11<'0'||c11>'9'){if(c11=='-')booo=1;c11=getchar();}
	while(c11>='0'&&c11<='9'){x=x*10+c11-'0';c11=getchar();}
	if(booo)x=-x;
	return ;
}

const int maxn=10050,maxm=50050;
struct node {int v,nxt;} a[maxm];
int head[maxn],p=0;
int low[maxn],dfn[maxn];
bool vis[maxn];
int num__=0;
int sta[maxn],top=0;
int colour=0;
int leaf[maxn];
int A[maxm],B[maxm];
int tot[maxn];
struct node1 {int v,nxt;} b[maxm];
int head1[maxn],pp=0;
int es[maxn];
int n,m;

inline void app(int x,int y);
inline void add(int u,int v);
void init();
void again();

void tarjan(int x){
	low[x]=dfn[x]=++num__;
	vis[x]=1;
	sta[++top]=x;
	for(int i=head[x];i;i=a[i].nxt){
		int v=a[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[x]=min(low[x],low[v]);
		}
		else if(vis[v])low[x]=min(low[x],dfn[v]);
	}
	if(dfn[x]==low[x]){
		vis[x]=0;
		leaf[x]=++colour;
		es[colour]++;
		for(;sta[top]!=x;top--){
			leaf[sta[top]]=colour;
			vis[sta[top]]=0;
			es[colour]++;
		}
		top--;
	}
	return ;
}

void work(){
	int temp=0,tem;
	for(int i=1;i<=colour;i++)
		if(!tot[i]){
			temp++;
			tem=i;
		}
	if(temp!=1)putchar('0');
	else printf("%d",es[tem]);
	return ;
}

int main(){freopen("in","r",stdin);freopen("1.out","w",stdout);
	init();
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	again();
	work();
	return 0;
}

void init(){
	cl(head);cl(low);cl(dfn);cl(vis);cl(tot);cl(es);
	read(n);read(m);
	for(int i=1;i<=m;i++){
		read(A[i]);read(B[i]);
		add(A[i],B[i]);
	}
	return ;
}

inline void app(int x,int y){
	if(leaf[x]==leaf[y])return ;
	b[++pp].v=leaf[y];
	b[pp].nxt=head1[leaf[x]];
	head1[leaf[x]]=leaf[y];
	tot[leaf[x]]++;
	return ;
}

void again(){
	for(int i=1;i<=m;i++){
		app(A[i],B[i]);
	}
	return ;
}

inline void add(int u,int v){
	a[++p].v=v;
	a[p].nxt=head[u];
	head[u]=p;
	return ;
}
           

醜陋的 标程

#include<cstdio>
#include<algorithm>
#define N  10009
#define M  50009
using namespace std;
int en,en1,n;
struct edge{                          
    int e;
    edge *next;
}*v[N],*v1[N],ed[M],ed1[M];
void add_edge(int s,int e){            
    en++;
    ed[en].next = v[s],v[s] = ed+en,v[s]->e = e;
}
void add_edge1(int s,int e){          
    en1++;
    ed1[en1].next = v1[s],v1[s] = ed1+en1,v1[s]->e =e;
}
int t,cnt,low[N],dfn[N],belong[N],siz[N],out[N],sta[N],stop = 1;
bool instack[N];
void dfs(int now){                    
    t++;
    low[now] = dfn[now] = t;
    instack[now] = true;
    sta[++stop] = now;
    for(edge *e = v[now];e;e=e->next)
      if(!dfn[e->e]){
            dfs(e->e);
            low[now] = min(low[now],low[e->e]);
      }
      else if(instack[e->e])low[now] = min(low[now],dfn[e->e]);
    if(dfn[now] == low[now]){
        cnt++;
        int si = 0;
        while(sta[stop] != now){
            int j  = sta[stop];
            belong[j] = cnt;
            instack[j] = false;
            stop--;
            si++;
        }
        si++;
        stop--;
        instack[now] = false;
        belong[now] = cnt;
        siz[cnt] = si;
    }
}
int  tarjan(){
    for(int a = 1; a <= n; a++)
       if(!dfn[a])dfs(a);
    for(int a =  1; a <= n; a++)
      for(edge *e = v[a];e;e=e->next)
        if(belong[a] != belong[e->e])               
           add_edge1(belong[a],belong[e->e]);
    for(int a = 1; a <= cnt; a++)
      for(edge *e =v1[a];e;e=e->next)            
        out[a]++;
    int ans = 0,b_hao = 0;
    for(int a = 1; a<= cnt; a++)
      if(out[a] == 0){
            if(b_hao != 0){                       
                ans = 0;
                break;
            }
            ans += siz[a];
            b_hao = a;
      }
    return ans;
}
int read(){                                  
    int x = 0;
    char ch  =getchar();
    while(ch < '0' || ch > '9')ch = getchar();
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
int main(){
	freopen("in","r",stdin);
	freopen("2.out","w",stdout);
    int m;
    n = read(),m = read();
    for(int a = 1;a <= m; a++){
        int u = read(),v = read();
        add_edge(u,v);                            
    }
    int ans = tarjan();
    printf("%d",ans);                          
    return 0;
}
           

強悍的 資料生成器

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("in","w",stdout);
	srand(time(0));
	int n=rand()%10000;
	while(n==1)n=rand()%10000;
	int m=rand()%50000;
	printf("%d %d\n",n,m);
	for(int i=1;i<=m;i++){
		int a=rand()%n+1;
		int b=rand()%n+1;
		while(a==b)b=rand()%n+1;
		printf("%d %d\n",a,b);
	}
	return 0;
}
           

神奇的也是最最重要的 對拍程式

#include<bits/stdc++.h>
using namespace std;
int main(){
	int cases=0;
	do{
		if(cases)
			printf("#%d AC\n",cases);
		cases++;
		system("./make");
		system("./1");
		system("./2");
	}while(!system("diff 1.out 2.out"));
	printf("#%d WA",cases);
	return 0;
}