【技巧】数据生成器&对拍_csp 对拍

目录

前言

关于对拍的引言

一、数据生成器

模板

如何构造数据

其他特殊类型数据的生成

二、对拍

模板

三、两个必需程序

四、开始对拍

五、例题

（一）题目

（二）分析

（三）代码实现

待测代码cheat.cpp——暴搜代码

正确代码bf.cpp——官方标程（考场上就是只有自己写暴力什么的了qwq）

数据生成器makedata.cpp

对拍器duipai.cpp

总结

---

前言

以前一直不会生成数据和对拍...这次花了一整晚终于大概懂了+练了一道例题

希望比赛时能助我一臂之力吧

参考博客&推荐：

https://blog.csdn.net/C20190102/article/details/60138907

https://blog.csdn.net/C20190102/article/details/82944384#_141

https://blog.csdn.net/CQBZLYTina/article/details/84852495

关于对拍的引言

考试时或比赛时，总会遇到一些题，我们不得不骗个分or打个暴力

但是打着打着可能会突然灵光乍现——想到了更优的做法or一个优化

可是我们有时不好手动造数据测试或者证明来保证它的正确性，甚至考虑错了的话，得分还不如直接打暴力高，这该怎么办呢，一个技巧孕育而生——对拍

简而言之，对拍就是将你对正确性没有把握的程序和有把握的程序进行比较

怎么比较？很简单的想法：输入相同数据，用一个程序比较它们的输出，若一模一样，则你优化后的程序就是正确的

这就是对拍的大致原理了

这个进行比较工作的程序就是“对拍器”

怎么非手动生成输入数据？那么就需要“数据生成器”

综上，进行对拍需要四个程序——你的需检测正确性的程序，答案正确的程序，一个数据生成器，和一个对拍器

一、数据生成器

【概览】生成数据，需要使用随机数生成函数rand( )

其实rand(  )生成的是伪随机数序列，
一般采用一次同余方程来生成随机数

例如：
X(0)=seed;
X(n+1) = (A * X(n) + C) % M;
显然，如何随机数种子seed相同，则产生的随机数序列也相同
如果在数据生成器中这样初始化随机数种子 ： srand(time(NULL))
在调用数据生成器的时间间隔非常小的情况下，生成的将会是相同的数据，导致对拍效率降低

形象来说，它就相当于一个脑子和一双手，脑子构造出数据后，手再把数据输出出来，以供你的程序读入并运行

一般写作“makedata#.cpp”

"#"处填1、2、3...表示不同的数据范围or类型（一般一道题里会有部分分，针对不同的部分分可写不同的数据生成器）

写数据生成器，你需要做以下两件事：

1.背住模板

2.写出能构造相应数据的代码

3.按题目格式输出

模板

#include<cstdio>
#include<ctime>//必写
#include<cstdlib>//必写
int main()
{
	srand(time(NULL));//必写
	/*以下是你的构造方法*/
}

如何构造数据

【概览】解决方法很简单，定义一个局部变量，把它的地址（操作系统在为本程序分配运行内存时，
会随机分配一段空间，保证不与之前的程序完全重合）与当前的机器时间作异或运算，将
得到一个不重复的seed，这样就可以连续调用数据生成器，产生不重复的数据了

#include<bits/stdc++.h>
int main()
{
    int a;
    int *aa = &a;
    freopen("data1.txt", "w", stdout);
    srand(time(NULL) ^ (unsigned long long)aa);
    for(int i = 1; i <= 10; i++)
        printf("%d ", rand() % 10);
    puts("");
}

例：构造两个n以内的非负整数（n=100000）

#include<cstdio>
#include<ctime>//必写
#include<cstdlib>//必写
int main()
{
	srand(time(NULL));//必写
        int n=100000;
	printf("%d %d\n",rand()%n,rand()%n);
}

若 2~n 呢？%( n-1 )+2即可

1.余数最小为0，0+2=2，符合>=2的要求

2.仍然%n的话，有可能余数为n-1，再+2就是n+1，不符合生成<=n的要求了，%( n-1 )余数最大为n-2，所以%( n-1 )刚好符合<=n的要求

#include<cstdio>
#include<ctime>//必写
#include<cstdlib>//必写
int main()
{
	srand(time(NULL));//必写
        int n=100000;
	printf("%d %d\n",rand()%(n-1)+2,rand()%(n-1)+2);
}

其他特殊类型数据的生成

生成随机排列：先生成1~n，再random_shuffle()
生成集合：用set
生成无根树：随机生成一条树边，并查集检验连通性，合法的加入，不合法的忽略
                        如果要限制每个结点的度，可加上deg[ ]数组，统计各点的度
生成无向图：邻接矩阵存图，随机生成边，加在图上，做至少n*(n-1)/2次
生成DAG：先生成无向图，再DFS，输出编号小的结点指向编号大的结点的边

for(int i = 1; i <= n; i++)
{
    sort(G[i].begin(), G[i].end());
    for(int j = 0; j < G[i].size(); j++)
    {
        int k = G[i][j];
        if(k > i)
            printf("%d %d\n", i, k);
    }
}

---

二、对拍

【概览】在windows操作中对拍需要写批处理程序。

一个简单的对拍批处理程序如下：

echo off
:loop
    makedata.exe >data.in
    bf.exe <data.in>data.out
    std.exe <data.in>data.txt
    fc data.out data.txt
    IF ERRORLEVEL 1 GOTO stop
    IF ERRORLEVEL 0 GOTO loop
:stop
pause

对拍就是帮你比对两个程序的输出结果是否相同

一般写作“dp.cpp”or“duipai.cpp”

模板

限制对拍次数的版本：

#include<iostream>
#include<windows.h>
using namespace std;
int main()
{
	/*有对拍次数的版本*/
	int t=这里是检查（对拍）次数;
	while(--t)
    {
		system("数据生成器名称.exe > 数据生成器名称.txt");
		system("程序1名称.exe < 数据生成器名称.txt > 程序1名称.txt");
		system("程序2名称.exe < 数据生成器名称.txt > 程序2名称.txt");
		if(system("fc 程序2名称.txt 程序1名称.txt"))
			break;
	}
	if(t==0)
		cout<<"no error"<<endl;
	else
		cout<<"error"<<endl;
	return 0;
}

直到有错才停止的版本：

#include<iostream>
#include<windows.h>
using namespace std;
int main()
{
        /*直到错了才停止的版本*/
        while(1)
        {
	    system("数据生成器名称.exe > 数据生成器名称.txt");
	    system("程序1名称.exe < 数据生成器名称.txt > 程序1名称.txt");
	    system("程序2名称.exe < 数据生成器名称.txt > 程序2名称.txt");
	    if(system("fc 程序2名称.txt 程序1名称.txt"))
		break;
        }
	return 0;
}

三、两个必需程序

一个你待检测的程序，一个保证了正确性的程序（一般是暴力）

---

四、开始对拍

将所有东西放进一个文件夹（主要是需要exe），运行对拍程序即可

运行结果样板图：

如果对拍显示有问题，就直接打开data.txt，里面有数据，1.txt和2.txt中分别是你程序1的答案和程序2的答案

如果你的对拍程序一出错就关闭了，就在return 0前加一个getchar()，让程序停一下，头文件：cstdio

---

五、例题

（一）题目

原题：http://codeforces.com/problemset/problem/932/F

NOIP/CSP-S考试 骗分对拍生成数据训练

JUMP TO LEAF

给定一棵树，有n个节点（从1到n编号），以节点1为根。每个节点

都有两个与之关联的权值。 第i个节点的权值为ai和bi。
你可以从一个节点跳到其子树中的任何节点。
从节点x跳到节点y的成本是ax和by的乘积。 由一个或多个跳跃形成

的路径的总成本是单个跳跃成本的总和。 对于每个节点，计算从该

节点到达任意一个叶结点的最小总成本。
请注意，根不是叶结点，不能从节点跳到自身。

Input
第1行：1个正整数n，表示树的结点数
第2行：n个空格分开的整数，表示ai
第3行：n个空格分开的整数，表示bi
接下来n-1行：每行两个整数ui, vi，表示树上的一条边

Output
第1行：n个空格分开的整数，表示每个结点跳到任意的叶结点的最

小总代价

Sample input 1
3
2 10 -1
7 -7 5
2 3
2 1

Sample output 1
10 50 0

sample 1 detail
节点3已经是叶子，因此成本为0。对于节点2，跳转到节点3的成本

为a2×b3 = 50；对于节点1，直接跳转到节点3的成本为a1×b3 = 10。

Sample input 2
4
5 -10 5 7
-8 -80 -3 -10
2 1
2 4
1 3

Sample output 2
-300 100 0 0

数据规模
对于 30% 的数据，n ≤ 5*10^3。
对于另外 20% 的数据，Bi = 1。
对于另外 20% 的数据，树是一条链，且除 1 号点外，i 号点的父亲

是 i-1。
对于 100% 的数据，2 ≤ n ≤ 10^5，|Ai|,|Bi|≤ 10^5。

练习要求：
1. 按要求生成指定特征的数据，共10组，数据生成器统一命名为

makedata#.cpp(#表示1,2,3,4),对于极限规模的数据，要保证树的深度

不小于n/10。
用你的暴力程序尽量跑出正确答案。对于极限数据，有可能跑不出

答案，可以放弃。
数据名称为：
leaf#.in
leaf#.out

2. 写一个能得到50~70分的骗分程序，程序名称为cheat.cpp

3. 写一个正解或者暴力程序，进行对拍。如果你写的是正解，程序

名称为std.cpp。如果你写的是暴力，程序名称为bf.cpp

4. 写一个对拍的批处理程序, 文件名为dp.bat，对你的std.cpp 与

bf.cpp或cheat.cpp进行对拍

5. 最后，按照你的CSP考号，建立文件夹，把上述的生成的数据放

在data子文件夹中。其余的放在考号文件夹中。
提交给我。

附录：
随机生成一棵树的代码

（二）分析

这道题用来训练对拍，于是就愉快暴搜吧=。=...

（以为自己可以暴力+特殊数据=50~70分
后来发现特殊数据是那么的难搞=。=  
所以出现了一个骗分代码与暴力代码没啥区别的尴尬场面... ）

---

1.第一遍DFS搜出各点的父亲

这样搜索的时候就直接知道该点的儿子是谁了

2.第二遍dfs搜出【该点到叶节点的最小距离】和更新【该节点的儿子往上变成该节点同辈】

Ps.搜到叶节点后直接返回“0”

解析：

求“最小距离”可以用递归的思想，即在其儿子中找出 “ 儿子到叶节点距离+儿子与自己的距离 ” 的最小值

再加上“记忆化”的技巧：

if(dis[u]!=INF)	
	dis[u]=min(dis[u],dis[i]+a[u]*b[i]);
else
	dis[u]=min(dis[u],dfs(i,u)+a[u]*b[i]);

接下来有个难题——怎么知道当前点u的所有子孙？

全部存下来似乎不太现实，空间又大、又花时间...

所以可以——实时更新！也就是一边搜索距离、一边更新各点子孙：

我们在搜索到点u的时候，将点u的所有儿子的祖先设为u的父亲

for(int i=head[u];i;i=nxt[i])
	if(E[i].v!=father)
	{
		dfs(E[i].v,u);
		old[E[i].v]=father;
		//类似并查集，把u的儿子往上变成father的儿子(与u同级) 
		//这样一边算出dis[]一边实时更新儿子数 
	}

然后更新距离时，就从点u的儿子（fa[ v ]=u）和孙子（old[ v ]=u）中选取

这样做的意义在于：做到了类似“01搜索”，也就是“该点选或不选”

例如下图：

已搜到点5，父亲为2，儿子分别为6,3,8，继续向下搜，回溯回来时将儿子上移一层：old[ 6,3,8 ] = 2，然后更新答案

已回溯到点2，父亲为1，儿子为5，将儿子上移一层：old[ 5 ] = 1，

然后更新答案：dis[ 2 ]=min( dis[ 2 ] , dis[ 5,6,3,8 ] + a[ 2 ] * b[ 5,6,3,8 ] )

已回溯到点4，父亲为1，儿子为7，将儿子上移一层：old[ 7 ] = 1，

然后更新答案：dis[ 4 ]=min( dis[ 4 ] , dis[ 7 ] + a[ 4 ] * b[ 7 ] )

已回溯到点1，父亲为0，儿子为2,4，将儿子上移一层：old[ 2,4 ] = 0，

然后更新答案：dis[ 1 ]=min( dis[ 1 ] , dis[ 2,4,5,7 ] + a[ 1 ] * b[ 2,4,5,7 ] )

结束搜索，输出答案

应该讲解清楚了吧...连打个暴搜都不容易...累shi ...=。=

（三）代码实现

待测代码cheat.cpp——暴搜代码

（这道题我只会暴力...所以就拿暴力来对拍了...本来因该是用有优化或者做法更优的代码）

/*以为自己可以暴力+特殊数据=50~70分 
后来发现特殊数据是那么的难搞=。=  
所以出现了一个骗分代码与暴力代码没啥区别的尴尬场面... */
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5,MAXM=4e5,INF=0x3f3f3f3f;
int head[MAXN+5],nxt[MAXM+5],fa[MAXN+5],old[MAXN+5];
int a[MAXN+5],b[MAXN+5],dis[MAXN+5];
int n,ecnt; 
struct Edge
{
	int u,v;
	Edge(int _u=0,int _v=0){u=_u,v=_v;}
	Edge(Edge &e){u=e.u,v=e.v;} 
}E[MAXM+5];
void Addedge(int u,int v)
{
	E[++ecnt]=Edge(u,v);
	nxt[ecnt]=head[u];
	head[u]=ecnt;
}
void DFS(int u,int father)
{
	bool flag=false;
	old[u]=fa[u]=father;
	for(int i=head[u];i;i=nxt[i])
	{
		int v=E[i].v;
		if(v!=father)
			flag=true,DFS(v,u);
	}
	if(!flag)
		dis[u]=0;
}
int dfs(int u,int father)
{
	if(!dis[u])//是叶节点,dis[u]=0
		return dis[u];
	for(int i=head[u];i;i=nxt[i])
		if(E[i].v!=father)
		{
			dfs(E[i].v,u);
			old[E[i].v]=father;
			//类似并查集，把u的儿子往上变成father的儿子(与u同级) 
			//这样一边算出dis[]一边实时更新儿子数 
		}
 
	for(int i=1;i<=n;i++)
		if(old[i]==u||fa[i]==u)//在u的子树内 
		{
			if(dis[u]!=INF)	
				dis[u]=min(dis[u],dis[i]+a[u]*b[i]);
			else
				dis[u]=min(dis[u],dfs(i,u)+a[u]*b[i]);
		}
	return dis[u];
}
int main()
{
	memset(dis,0x3f,sizeof(dis));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
		fa[i]=i;	
	for(int i=1;i<=n-1;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		Addedge(u,v);
		Addedge(v,u);
	}
	DFS(1,0);
	for(int i=1;i<=n;i++)
		if(i==n)
			printf("%d\n",dfs(i,fa[i]));
		else
			printf("%d ",dfs(i,fa[i]));
	return 0;
}

正确代码bf.cpp——官方标程（考场上就是只有自己写暴力什么的了qwq）

#include "bits/stdc++.h"
#define ll          long long
#define pb          push_back
#define mp          make_pair
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (int)x.size()
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b)    for(int i=a;i<b;i++)
using namespace std;
 
bool Q;
struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const {
        return Q ? p < o.p : k < o.k;
    }
};
struct LineContainer : multiset<Line> {
    const ll inf = LLONG_MAX;
    ll div(ll a, ll b){
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) {
        if (y == end()) { x->p = inf; return false; }
        if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(ll k, ll m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    ll query(ll x) {
        assert(!empty());
        Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;
        return l.k * x + l.m;
    }
};
 
vector<int> x,y;
vector<vi> adj;
vector<ll> ans;
vector<int> subsize;
void dfs1(int u,int v){
    subsize[u]=1;
    for(auto i:adj[u]){
        if(i==v)continue;
        dfs1(i,u);
        subsize[u]+=subsize[i];
    }
}
 
void dfs2(int v, int p,LineContainer& cur){
    int mx=-1,bigChild=-1;
    bool leaf=1;
    for(auto u:adj[v]){
        if(u!=p and subsize[u]>mx){
            mx=subsize[u];
            bigChild=u;
            leaf=0;
        }
    }
    if(bigChild!=-1){
        dfs2(bigChild,v,cur);
    }
    for(auto u:adj[v]){
        if(u!=p and u!=bigChild){
            LineContainer temp;
            dfs2(u,v,temp);
            for(auto i:temp){
                cur.add(i.k,i.m);
            }
        }
    }
    if(!leaf)ans[v]=-cur.query(x[v]);
    else ans[v]=0;
    cur.add(-y[v],-ans[v]);
}
void solve(){
    int n;
    cin>>n;
    x.resize(n+1);
    y.resize(n+1);
    ans.resize(n+1);
    subsize.resize(n+1);
    adj.resize(n+1);
    rep(i,1,n+1)cin>>x[i];
    rep(i,1,n+1)cin>>y[i];
    rep(i,1,n){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    dfs1(1,0);
    LineContainer lc;
    dfs2(1,0,lc);
    rep(i,1,n+1)cout<<ans[i]<<" ";
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
//    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

数据生成器makedata.cpp

这里我只拍了部分分，若有多个部分分，可写多个对应的数据生成器，如：makedata1.cpp，makedata2.cpp... ...

//参考博客：https://blog.csdn.net/sslz_fsy/article/details/83064905 
//30%:n<=5000
#include<cstdio>
#include<ctime>
#include<cstdlib>
const int MAXN=5000;
int n,m,cnt,fa[MAXN+5];
int find(int x)//并查集版本 
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
} 
int main()
{
	srand(time(NULL));
	n=rand()%MAXN+2;//2<=n<=100000
	printf("%d\n",n);
	for(int i=1;i<=n;i++)
		printf("%d ",rand()%MAXN-rand()%MAXN);//题目要求有负数 
	printf("\n");
	for(int i=1;i<=n;i++)
		printf("%d ",rand()%MAXN-rand()%MAXN);
	printf("\n");
	for(int i=1;i<=n;i++)
		fa[i]=i;
	while(cnt<n-1)
	{
		int x=rand()%n+1,y=rand()%n+1;//生成两个点 
		int X=find(x),Y=find(y);
		if(X!=Y)//如果不是同一个祖先就连边 
		{
			fa[X]=Y,cnt++;
			printf("%d %d\n",x,y);
		}
	}
	return 0;
}

对拍器duipai.cpp

#include<iostream>
#include<windows.h>
using namespace std;
int main()
{
	//有对拍次数的版本： 
	int t=1000;
	while(--t)
	{
		system("makedata.exe > makedata.txt");
		system("bf.exe < makedata.txt > bf.txt");
		system("cheat.exe < makedata.txt > cheat.txt");
		if(system("fc cheat.txt bf.txt"))
			break;
	}
	if(t==0)
		cout<<"no error"<<endl;
	else
		cout<<"error"<<endl;
	return 0;
}
/*
直到错了才停止的版本：
while(1)
{
	system("数据生成器名称.exe > 数据生成器名称.txt");
	system("程序1名称.exe < 数据生成器名称.txt > 程序1名称.txt");
	system("程序2名称.exe < 数据生成器名称.txt > 程序2名称.txt");
	if(system("fc 程序2名称.txt 程序1名称.txt"))
		break;
}
*/

把他们放一起然后运行就可以开始 愉快地  对拍了~

总结

花了近一天终于讲解清楚了...QAQ...

对拍是个好东西，特别是防止你考试时思路的遗漏疏忽导致失分（我当年B题六七十分，就是因为有个小情况没考虑到orz）

考试时合理运用可助你飞升哦2333

但是平时要多做对拍相关的练习，熟悉自己的做题节奏、合理分配做题+对拍时间（一不小心就会发现时间在狂奔而去...）

CSP2019加油！