admin 管理员组

文章数量: 1184232

【技巧】数据生成器对拍

目录

前言

关于对拍的引言

一、数据生成器

模板

如何构造数据

其他特殊类型数据的生成

二、对拍

模板

三、两个必需程序

四、开始对拍

五、例题

（一）题目

（二）分析

（三）代码实现

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

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

数据生成器makedata.cpp

对拍器duipai.cpp

总结

---

前言

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

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

参考博客&推荐：

关于对拍的引言

考试时或比赛时，总会遇到一些题，我们不得不骗个分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
:loopmakedata.exe >data.inbf.exe <data.in>data.outstd.exe <data.in>data.txtfc data.out data.txtIF ERRORLEVEL 1 GOTO stopIF 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;elsecout<<"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

---

五、例题

（一）题目

原题：

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]);
elsedis[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]=0return 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]);elsedis[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]));elseprintf("%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... ...

//参考博客： 
//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<=100000printf("%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;elsecout<<"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加油！

本文标签： 技巧数据生成器对拍