10.7更新：见最下面
离NOIP2018没剩多长时间了，我突然发现我连对拍还不会，于是赶紧到网上找资料，找了半天发现了一个特别妙的程序，用c++写的！
不过先讲讲随机数据生成吧。
很简单，就是写一个程序模拟输入数据，然后利用rand()编写随机数。
在头文件cstdlib中，有rand(), srand()函数，以及常量RAND_MAX.
RAND_MAX在windos系统中为 0x7fff = 2^15-1 = 32767；在Unix（可以理解为linux，只不过linux是unix一种，是”类unix“）下为 2^31-1 = 2147483647（都是32位），加上一个正数最高位就为1，就变成了负数，即 -RAND_MAX = RAND_MAX + 1,所以 - rand() / RAND_MAX = rand() / (RAND_MAX + 1)。
rand()返回一个在0~RAND_MAX之间的整数。
srand(seed)函数接受一个unsigned int类型的参数seed,以seed为“随机种子”。
rand()函数基于线性同余递推式（就是某种递推式吧~）生成随机数，“随机种子“相当于这个递推式的初始参数，若不执行srand(),则种子默认为1.
当种子确定后，生成的随机数列也是固定的，因此这种随机方法是”伪随机“，所以一般要在开始调用srand()，且以当前时间为随机种子。
怎么写呢？ctime里有一个tim函数，调用time(0)可以返回从1970年1月1日0时0分0秒（Unix纪元）到现在的秒数。然后写这么一句就行了：srand((unsigned)time(0));
接下来才是重点：对拍~~
对拍是啥我就不多说了，直接讲怎么写。
首先，得有这么几个程序：
1.随机数据生成程序random.cpp.
2.自己的美妙算法程序sol.cpp
3.暴力程序bf.cpp (bf:brute force 暴力)
然后我们要写一个脚本，循环执行以下过程：
1.运行random.exe.
2.运行sol.exe
3.运行bf.exe
4.比对sol.out和bf.out的内容是否一致。
虽然Windos和类unix分别有bat批处理脚本和bash脚本，然而因为我太懒不想学别的语言，就废了半天功夫找到了一个用c++写的（你这道勤快）。
还是在cstdlib中，有一个system函数，他接受一个字符串作为参数，然后把这个字符串作为系统命令执行，栗如：system("C:\\Users\\Administrator\\Desktop\\random.exe")，执行windos桌面上的random.exe。
比对的话，windows用fc，类Unix用diff，他们接受两个文件路径，比较二者是否一致，若一致返回0，否则返回非0值。
下面放出windos的对拍程序，程序都是在桌面上的
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const int eps = 1e-;
//const int maxn = ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int main()
{
for(int t = ; t <= ; ++t)
{
system("C:\\Users\\Administrator\\Desktop\\random.exe");
db Beg = clock(); //记录sol.exe的运行时间
system("C:\\Users\\Administrator\\Desktop\\sol.exe");
db End = clock();
system("C:\\Users\\Administrator\\Desktop\\bf.exe");
if(system("fc C:\\Users\\Administrator\\Desktop\\sol.out C:\\Users\\Administrator\\Desktop\\bf.out"))
{
puts("WA"); return ;
}
else printf("AC, #%d, Time : %.0lfms\n", t, End - Beg);
}
return ;
}
类unix上的对拍程序，只需要更改上面的代码system中的路径格式，把fc改成diff，用时单位该为”秒“（windos是毫秒）。
于是我又写了一个linux下的，奇特的是，双斜杠单斜杠竟然都行，而且时间还是以毫秒为单位……
#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;
typedef double db; int main()
{
for(int i = ; i <= ; ++i)
{
system("//home//noilinux//Desktop//random");
db Beg = clock();
system("//home//noilinux//Desktop//sol");
db End = clock();
system("//home//noilinux//Desktop//bf");
if(system("diff //home//noilinux//Desktop//sol.out //home/noilinux//Desktop//bf.out"))
{
puts("WA"); return ;
}
else printf("AC #%d, Time : %.0lfms\n", i, End - Beg);
}
return ;
}
这里给一个a + b的对拍程序：
首先是random.cpp
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const int eps = 1e-;
//const int maxn = ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int main()
{
freopen("random.in", "w", stdout);
srand((unsigned)time());
write(rand() % rand()); space; write(rand() % rand());
return ;
}
然后是sol.cpp（随便拷的一份LCT的……巨啊）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
int data,rev,sum;
node *son[],*pre;
bool judge();
bool isroot();
void pushdown();
void update();
void setson(node *child,int lr);
}lct[];
int top,a,b;
node *getnew(int x)
{
node *now=lct+ ++top;
now->data=x;
now->pre=now->son[]=now->son[]=lct;
now->sum=;
now->rev=;
return now;
}
bool node::judge(){return pre->son[]==this;}
bool node::isroot()
{
if(pre==lct)return true;
return !(pre->son[]==this||pre->son[]==this);
}
void node::pushdown()
{
if(this==lct||!rev)return;
swap(son[],son[]);
son[]->rev^=;
son[]->rev^=;
rev=;
}
void node::update(){sum=son[]->sum+son[]->sum+data;}
void node::setson(node *child,int lr)
{
this->pushdown();
child->pre=this;
son[lr]=child;
this->update();
}
void rotate(node *now)
{
node *father=now->pre,*grandfa=father->pre;
if(!father->isroot()) grandfa->pushdown();
father->pushdown();now->pushdown();
int lr=now->judge();
father->setson(now->son[lr^],lr);
if(father->isroot()) now->pre=grandfa;
else grandfa->setson(now,father->judge());
now->setson(father,lr^);
father->update();now->update();
if(grandfa!=lct) grandfa->update();
}
void splay(node *now)
{
if(now->isroot())return;
for(;!now->isroot();rotate(now))
if(!now->pre->isroot())
now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now)
{
node *last=lct;
for(;now!=lct;last=now,now=now->pre)
{
splay(now);
now->setson(last,);
}
return last;
}
void changeroot(node *now)
{
access(now)->rev^=;
splay(now);
}
void connect(node *x,node *y)
{
changeroot(x);
x->pre=y;
access(x);
}
void cut(node *x,node *y)
{
changeroot(x);
access(y);
splay(x);
x->pushdown();
x->son[]=y->pre=lct;
x->update();
}
int query(node *x,node *y)
{
changeroot(x);
node *now=access(y);
return now->sum;
}
int main()
{
freopen("random.in", "r", stdin);
freopen("sol.out", "w", stdout);
scanf("%d%d",&a,&b);
node *A=getnew(a);
node *B=getnew(b);
//连边 Link
connect(A,B);
//断边 Cut
cut(A,B);
//再连边orz Link again
connect(A,B);
printf("%d\n",query(A,B));
return ;
}
最后是bf.cpp
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const int eps = 1e-;
//const int maxn = ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int main()
{
freopen("random.in", "r", stdin);
freopen("bf.out", "w", stdout);
int a = read(), b = read();
write(a + b); enter;
}
把三个程序分别运行一下，得到三个exe。然后运行上面的对拍程序就行啦~~
附一下效果
如果把bf改成write(a +b + 1)的话：
这时候出错的数据就是当前的random.in了~~
***10月7日更新***
小云彩（tql）告诉我了一个更简便的写法。
在调用system的时候，里面可以不用写的那么复杂。如果这些东西在同一目录下，我们只用这么写：
#include<cstdio>
#include<cstdlib>
#include<ctime>
typedef double db;
using namespace std; int main()
{
for(int t = ; t <= ; ++t)
{
system(".\\random.exe");
db Beg = clock();
system(".\\ac.exe");
db End = clock();
system(".\\bf.exe");
if(system("fc .\\ac.out .\\bf.out"))
{
printf("WA\n"); return ;
}
else printf("#%d AC %.2lfms\n", t, End - Beg);
}
return ;
}
windos下用 .//，linux下是 ~\\。
方便。
对拍讲完啦~~~祝各位继续AKIOI~~