[C++知识库]OI生成随机题目数据，测试点集锦【C++】【有待完善】

0x00 前言

这篇文章是蒟蒻为了能使后来的 OIER 们可以更好的搞事情 为大家带来更优质的题目以及更好的写出合理的对拍程序，本蒟蒻在此写了一篇并不完善的文章，总结了出各种数据的代码；

各位Dalao若有更好的办法可以评论，以帮助蒟蒻更好的完成这篇文章，蒟蒻目前的方法其实有点笨，每次都需要手动改文件输入输出的输出文件名；

0x01 基础知识框架

在涉及到题目数据生成之前，要首先学会C++中的伪随机数生成；（不然就只能手打数据了 ）

标程和数据代码

在OI中，一个完整的测试点由输入数据(.in)和答案数据(.out/.ans但是这个得看每个OJ的配置，洛谷是.out文件)组成，其中，输入数据由数据代码随机生成并储存，答案数据由出题人的正确代码，即标程从输入数据中读入，在处理成答案输出储存；

这里我们重点讲的是数据代码，因为标程就是我们平时做题的AC代码，没有本质上的区别;

函数

c++中的伪随机数函数是一个叫做C的库函数，注意，rand()需要头文件 #include<stdlib.h>这里蒟蒻用的是c++的万能头文件#include<bits/stdc++.h>；

这个函数会返回一个整型数据（具体因种子而定，一般来说，int是32767，unsigned int是65535）,因而基本用法如下：(当然也可以直接输出)

 int num=rand();
 printf("%d",num);

具体用法

但是，当你用这段代码进行随机数输出时，你会惊人的发现他每次运行输出的“随机数”都是同一个数，为什么？

因为刚刚说过，rand()是一个伪随机数，它需要一个种子，这个种子默认为0，所以每次输出会一模一样；因而，为了达到目的，我们需要引入一个设置种子的函数 srand(种子（一个整数),但是，srand()设置的种子一样，那么rand()取到的随机数也会一摸一样，可是我们不能每次为srand()函数设置种子，所以我们需要一个活动的值，比如time()函数返回当前时间,这也是当今主流的写法；

所以就有了以下两种写法，但要注意一点srand()的赋值应当在程序中只有一次或两次赋值程序运行时间大于1s，不然每次随机数会一模一样：(第二种Dev-C++6.5本蒟蒻实测可以过，报错的话应该是个编译器之间有差异)

srand(time(0)); 
int num=rand();

srand((unsigned)time(NULL));
int num=rand();

但是，有的时候，会有数据范围的限制，这时候我们就需要取模来限定他的大小了；比如在我们需要$[l,r]$这个区间中的随机数，怎么办？其实很简单，我们先生成一个随机数num，再把这个num对于$(r?l+1)$取余，最后加上$l$就可以了；

证明:在num取余之后，它的值在 $[0,r?l]$之内，在加上 $l$后，num属于区间$[0+l,r?l+l]$等价于$[l,r]$，这就证明了这个算法的正确性；

其实现如下：

//注意,在函数外面应当提前写上srand((unsigned)time(NULL))或srand(time(0)) :
int newrand(int l,int r){
	int num=rand();
	return (num%(r-l+1)+l);
}

文件输入输出

一般c++的输出是在控制台中完成，但是在出数据的时候，我们就不可以输出到控制台中了（比较慢，而且不可以一步到位），因而我们需要一个可以吧输出或是输入弄到文件中的代码，即 freopen，代码格式如下：

• 输入：freopen("你的文件名.文件后缀名","r",stdin);
• 输出：freopen("你的文件名.文件后缀名","w",stdout);

（想必大家都很熟悉这个臭名昭著的在比赛里面不写爆零的函数了 谁没爆过）

这样，我们就掌握了基础知识，可以进行下一步了；

0x02 基础数据模板

P1001 A+B Problem

戳此

这道题非常万能，没有太多的数据限制，所以在做题时是入门练习题，在出题时也是一道很不错的练习题；

思路：生成两个在$[1,2^{32}]$中的数就可以了；(记得开 long long)

数据程序

#include<bits/stdc++.h>
#define int long long//这行是宏定义，可以吧代码中的“int”替换成“long long”
using namespace std;
int newrand(int l,int r){
	int num=rand();
	return (num%(r-l+1)+l);
}
signed main(){
	freopen("and_{该数据点编号}.in","w",stdout);
	srand((unsigned)time(NULL));
	printf("%lld %lld",newrand(1,4294967295/*2^32=4294967295*/),newrand(1,4294967295));
	return 0;
}

标程

#include<bits/stdc++.h>
using namespace std;
long long a,b;
signed main(){
	freopen("and_{该数据点编号}.in","r",stdin);
	freopen("and_{该数据点编号}.out","w",stdout);
	scanf("%lld%lld",&a,&b);
	printf("%lld",a+b);
	return 0;
}

P1031 [NOIP2002 提高组] 均分纸牌

戳此

思路：这道题与以往不同的是他有了一个线性的数组要输出，但也很简单，一个循环1可以完成，唯一需要注意的是数据范围；

数据程序

#include<bits/stdc++.h>
using namespace std;
long long newrand(){
	long long num=rand();
	return (num%(r-l+1)+l);
}
signed main(){
	freopen("and_{该数据点编号}.in","w",stdout);
	srand((unsigned)time(NULL));
	long long n=newrand(1,100);
	printf("%lld\n",n);//输出N 
	for(int i=1;i<=n;i++){
		printf("%lld ",newrand(1,10000));//输出Ai 
	}
	return 0;
}

P1007 独木桥

戳此

这道题也是一个线性结构，但是每个士兵所占的位置不能重复，因此我们需要一个vis数组，用来保存这个位置是否被一个士兵占用了，并且要注意 $N\le L$；

数据程序

#include<bits/stdc++.h>
#define int long long
using namespace std;
int L,n,vis[3005];
int newrand(int l,int r){
	int num=rand();
	return (num%(r-l+1)+l);
}
signed main(){
	freopen("and_{该数据点编号}.in","w",stdout);
	srand((unsigned)time(NULL));
	memset(vis,0,sizeof(vis));
	L=newrand(1,5000);//生成L 
	n=newrand(1,L);// N<=L的实现 
	printf("%lld\n%lld\n",L,n);//输出L,N 
	for(int i=1;i<=n;i++){
		int dis=newrand(1,L);//士兵要在桥上 
		if(!vis[dis]){//这个位置没有站士兵 
			printf("%lld ",dis);
			vis[dis]=1;//标记 
		}
	}
	return 0;
}

0x03 图论数据模板

[蒟蒻还没学会出最大最小流，所以并不是很全，而且也不能保证无环，只能保证联通]

随机生成树[根节点为1]

随机生成树我们可以倒着思考从后往前连边，因为一个点最多只有一个父节点，所以我们只需要对于点$i$往$[1,i?1]$点的区间中拉一条边，即往它可能存在的父节点建边，根节点不用建边，最后一定可以得到一棵树；

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int newrand(int l,int r){
	int num=rand();
	return (num%(r-l+1)+l);
}
signed main(){
	freopen("and_{该数据点编号}.in","w",stdout);
	srand((unsigned)time(NULL));
	memset(vis,0,sizeof(vis));
	n=newrand(1,10000);//生成n 
	printf("%lld\n",n); 
	for(int i=1+1;i<n+1;i++){
	    int fi=newrand(1,i);//生成点i的父节点 
	    int dis=newrand(1,1e9);//生成这条边的权值 
	    printf("%lld %lld %lld\n",fi,i,dis);//输出 
	}
	return 0;
}

随机连通图

连通图的根本一定是一个树，连通图一定有一个或多个生成树，所以我们只需要先生成一个树，再在这个树上添加边就可以保证出来的图是一个连通图;

无向图

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
map<pair<int,int>,bool> vis;//用点u和点v边的关系映射是否被占用的bool值 
int newrand(int l,int r){
	int num=rand();
	return (num%(r-l+1)+l);
}
signed main(){
	freopen("and_{该数据点编号}.in","w",stdout);
	srand((unsigned)time(NULL));
	memset(vis,0,sizeof(vis));
	n=newrand(1,10000);//生成n 
	m=newrand(n-1,n*(n-1)-1);//生成m(保证至少可以构成一个树,至多是一个完全图) 
	printf("%lld\n",n); 
	for(int i=2;i<=n;i++){
	    int fi=newrand(1,i);//生成点i的父节点 
	    int dis=newrand(1,1e9);//生成这条边的权值
	    vis[make_pair(fi,dis)]=true;//标记
	    printf("%lld %lld %lld\n",fi,i,dis);//输出 
	} 
	for(int i=n;i<=m;i++){
		int u=newrand(1,n),v=newrand(1,n); 
		while(u==v||vis[make_pair(u,v)]){//生成u,v并判断是否可以出现 
			u=newrand(1,n);v=newrand(1,n);
		}
		vis[make_pair(u,v)]=vis[make_pair(v,u)]=true;//标记,是有向图就去掉后面的vis[make_pair(v,u)] 
		printf("%lld %lld %lld\n",u,v,newrand(1,1e9));
	}
	return 0;
}

有向图

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
map<pair<int,int>,bool> vis;//用点u和点v边的关系映射是否被占用的bool值 
int newrand(int l,int r){
	int num=rand();
	return (num%(r-l+1)+l);
}
signed main(){
	freopen("and_{该数据点编号}.in","w",stdout);
	srand((unsigned)time(NULL));
	memset(vis,0,sizeof(vis));
	n=newrand(1,10000);//生成n 
	m=newrand(n-1,n*(n-1)-1);//生成m(保证至少可以构成一个树,至多是一个完全图) 
	printf("%lld\n",n); 
	for(int i=2;i<=n;i++){
	    int fi=newrand(1,i);//生成点i的父节点 
	    int dis=newrand(1,1e9);//生成这条边的权值
	    vis[make_pair(fi,dis)]=true;//标记
	    printf("%lld %lld %lld\n",fi,i,dis);//输出 
	} 
	for(int i=n;i<=m;i++){
		int u=newrand(1,n),v=newrand(1,n); 
		while(u==v||vis[make_pair(u,v)]){//生成u,v并判断是否可以出现 
			u=newrand(1,n);v=newrand(1,n);
		}
		vis[make_pair(u,v)]=true;//标记,是有向图就去掉后面的vis[make_pair(v,u)] 
		printf("%lld %lld %lld\n",u,v,newrand(1,1e9));
	}
	return 0;
}

目前文章更新到此，若各位Dalao有补充或蒟蒻学了更多算法，将会及时更新