目录批量数据生成器rand() 和 srand()随机一个数一个 long long 范围的数一个 [m, n] 范围的数一个小数一个序列随机一个排列一棵树一棵普通的树一棵外（内）向树一张图一张无向联通图避免重边避免自环一个 DAG （有向无环图）附一个模板
可以配合如何快速的写出对拍程序食用qwq。
下面讲的方法本着简单快捷的原则，更多是为了方便大家在比赛中快速造出数据进行对拍。也是为了方便我随手取用。
如果有什么更牛逼的造数据方法，也可以跟我说/kel，欢迎补充。
批量数据生成器
感谢 @斜揽残箫 提供/qq。
#include
#include
using namespace std;
namespace rad {
mt19937_64 R(time(0));
inline int Rand(int l,int r) {
uniform_int_distribution
return distribution(R);
}
} using namespace rad;
int main() {
string in,out;
for(int i = 1;i <= 3;i ++) { // 序号
Sleep(1000);
in.clear();
int j = i;
while(j) {
char m = j % 10 + '0';
in = m + in;
j /= 10;
}
out = in;
in += ".in";
out += ".out";
string A = "name"; // 文件名
string B = "name";
A = A + in,B = B + out;
in = A,out = B;
freopen(in.data(),"w",stdout);
system("data.exe"); // 数据生成器
fclose(stdout);
string Str="std.exe < "+ in +" > "+ out; // 你的 std
system(Str.data());
}
}
rand() 和 srand()
rand() 函数用来产生随机数，但是，rand() 的内部实现是用线性同余法实现的，是伪随机数，由于周期较长，因此在一定范围内可以看成是随机的。
rand() 会返回一个范围在 0 到 RAND_MAX（一般是32767）之间的伪随机数（整数）。
srand() 函数则是设置随机数种子，如果没有 srand() 函数，rand() 默认的随机数种子为 \(1\)。随机种子相同，每次产生的随机数也会相同。
随机一个数
一般形式为 x = rand()。随机一个数（\(0 \sim 32767\)）并存入 \(x\) 内。
一个 long long 范围的数
因为 \(0 \sim 32767\) 在二进制下只占用了 \(15\) 位，所以我们可以把四个 rand() 拼起来。
long long Rand(long long n) { // 限定上界 n，生成一个 [0,n) 范围内的数
long long x = rand() * (1ll << 45) + rand() * (1ll << 30) + rand() * (1ll << 15) + rand();
return x % n;
}
注意这里产生的数的范围只在 \(0 \sim 2^{61}-1\)，并不是真正意义上的 long long 范围。不过这一般也够用了。
一个 [m, n] 范围的数
把上面的函数稍微修改一下，确定一个下界即可。或者理解为 “在 \(m\) 的基础上在加一个数 \(x\)，可加的 \(x\) 的大小为区间长度 \(n-m+1\)”。
long long Rand(long long n) { // 限定上界 n
long long x = rand() * (1ll << 45) + rand() * (1ll << 30) + rand() * (1ll << 15) + rand();
return x % (n - m + 1) + m;
}
一个小数
原理：如果你要一个 \(x\) 位小数，你可以先生成一个 \(x\) 位的数，然后除以 \(10^x\)。
double Rand(long long n) { // 限定上界 n = 10^x
long long x = rand() * (1ll << 45) + rand() * (1ll << 30) + rand() * (1ll << 15) + rand();
return (double)x / n;
}
一个序列
一个长度为 \(n\) 的序列直接输出 \(n\) 个随机数就好了吧。
随机一个排列
这里我使用 random_shuffle(a + 1, a + n + 1) 来打乱一个排列。
不过这个函数好像在 C++ 14 中被弃用了？
一棵树
一棵普通的树
Kruskal
利用 Kruskal 的思想打造即可。
int fa[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void Get_A_Tree(int n) {
int cnt = 0;
for(int i = 1; i <= n; ++i) fa[i] = i;
while(cnt < n - 1) {
int u = Rand(n) + 1, v = Rand(n) + 1;
while(find(u) == find(v)) v = Rand(n) + 1;
fa[find(u)] = find(v);
printf("%d %d\n", u, v);
++ cnt;
}
}
随机排列
感谢 @KnightL 提供/qq。
这里提供另外一种简单的方法：
随机一个排列，然后后面的一个点之和前面的某个点连边。
在这个方法下，内向树和外向树也同样非常方便构造，只需要在输出时确定连边方向即可。
int c[MAXN];
void Get_A_Tree(int n) {
for(int i = 1; i <= n; ++i) c[i] = i;
random_shuffle(c + 1, c + n + 1);
for(int i = 2; i <= n; ++i) {
printf("%d %d\n", Rand(i - 1) + 1, i);
}
}
一棵外（内）向树
在上面的一棵普通的数的基础上，需要还通过 dfs 来确立一个方向。
struct edge { int to, nxt; }e[MAXN << 2];
int head[MAXN], num_edge = 1;
int fa[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void add_edge(int from, int to) { e[++num_edge] = (edge){to, head[from]}, head[from] = num_edge; }
void dfs(int u, int fa) {
for(int i = head[u]; i; i = e[i],nxt) {
int v = e[i].to;
if(v == fa) continue;
printf("%d %d\n", u, v); // 外向树
// printf("%d %d\n", v, u); // 内向树
dfs(v, u);
}
}
void Get_A_Tree(int n, int m) {
int cnt = 0;
for(int i = 1; i <= n; ++i) fa[i] = i;
while(cnt < n - 1) {
int u = Rand(n) + 1, v = Rand(n) + 1;
while(find(u) == find(v)) v = Rand(n) + 1;
fa[find(u)] = find(v);
add_edge(u, v), add_edge(v, u);
++ cnt;
}
}
一张图
一张无向联通图
先随机生成一棵树，然后在添加边即可。
避免重边
一个暴力的方法，使用 map 判重。
需要注意的是效率会比较低。
避免自环
随机一条边的时候注意保持 u != v 即可。
一个 DAG （有向无环图）
你可以考虑随机一个拓扑序。
如果要保证图联通的话还是先随机一棵树，然后在随机其他边，否则直接随机若干条边就可以。
注意输出边 \((u,v)\) 的时候你要保证 topo[u] < topo[v]，即总是拓扑序前面的点向后面的点连边。
附一个模板
/*
造数据专用模板
write by 梓苏
*/
#include
#define int long long
#define orz cout << "tyy YYDS!!!\n"
using namespace std;
const int MAXN = 2e5 + 10;
const int INF = 1e9 + 7;
const int mod = 998244353;
int n, a[MAXN];
int read() {
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
int Rand(int l, int r) { // 返回值域区间在 [l,r] 内的一个（不完全）随机数，r < 2^60
int x = (rand() * (1ll << 45)) + (rand() * (1ll << 30)) + (rand() * (1ll << 15)) + (rand());
int len = r - l + 1;
return l + x % len;
}
void Get(int *a, int l, int r, int L, int R) { // 随机一个序列 a，放到 a[l] 到 a[r]，值域是 [L,R]
for(int i = l; i <= r; ++i) a[i] = Rand(L, R);
}
void Print(int *a, int l, int r) { // 输出 a[l] 到 a[r]
for(int i = l; i <= r; ++i) printf("%lld ", a[i]);
puts("");
}
void GetTree(int n, int k, int L = 0, int R = 0) { // k=0 不带权，k=1 带权
for(int i = 1; i <= n; ++i) a[i] = i;
random_shuffle(a + 1, a + n + 1);
if(k == 1) for(int i = 2; i <= n; ++i) printf("%lld %lld %lld\n", a[Rand(1, i - 1)], a[i], Rand(L,R));
else for(int i = 2; i <= n; ++i) printf("%lld %lld\n", a[Rand(1, i - 1)], a[i]);
}
signed main() {
srand(time(NULL));
return 0;
}