发表

造数据？拿脚造！

在一切的一切开始之前

优质的随机数？rand()

1
2
3
4
#include<chrono>
#include<random>
mt19937_64  rnd(chrono::steady_clock::now().time_since_epoch().count());//unsigned long long
mt19937  rnd(chrono::steady_clock::now().time_since_epoch().count());//unsigned int

简单一点？

1
2
3
4
#include<random>
#include<ctime>
mt19937_64  rnd(time(0));//unsigned long long
mt19937  rnd(time(0));//unsigned int

需要负数？

推出我们的梅森旋转引擎

1
2
3
mt19937_64 egn(time(0));
uniform_int_distribution<long long> rnd(l,r);/* 根据范围给出l,r */
cout<<rnd(egn)<<' ';

打乱序列？

1
2
3
4
int a[1024];
for(int i=0;i<1024;i++)a[i]=i;
srand(time(NULL));
random_shuffle(a,a+1024);

高质量的->

1
2
3
4
5
6
7
8
9
10
11
12
#include<chrono>
#include<random>
#include<iostream>
#include<algorithm>
using namespace std;
mt19937_64  rnd(chrono::steady_clock::now().time_since_epoch().count());
int main(){
    int a[10];
    for(int i=0;i<10;i++)a[i]=i;
    shuffle(a,a+10,rnd);
    for(int i=0;i<10;i++)cout<<a[i]<<endl;
}

在一切开始之前

脚本读出？

造数据的时候可能需要通过命令行脚本.bat如

1
2
3
4
DataMaker.exe num1 num2 > 1.in
DataMaker.exe num1 num2 >> 2.in
DataMaker.exe num3 num4 > 3.in
...

这时候我们需要将main()

1
2
3
int main(){

}

更改为

1
2
3
4
5
int main(int argc,char* argv[]){
    int a = atoi(argv[1]);
    long long b = atoll(argv[2]);
    double c = atof(argv[3]);
}

文件输入输出？

1
2
3
4
5
6
7
8
9
10
#include<fstream>
int main(int argc,char* argv[]){
    ifstream fin;
    ofstream fout;
    fin.open("your file");
    fout.open("your file");
    int n;
    fin>>n;
    fout<<n;
}

打开类型

常量 含义
ios_base::in 打开文件，读取
ios_base::out 打开文件，写入
ios_base::ate 打开文件，移到文件尾
ios_base::app 追加到文件尾
ios_base::trunc 如果文件存在，则截断文件
ios_base::binary 二进制文件

上面的fout.open()其实是有三个参数的，第一个是文件的路径，第二个是打开文件的类型，第三个是权限。如果不写的话，会采用默认参数，就是ios_base::out|ios_base::trunc；

开始之前

模仿testlib.h(Github)

我们给出一些常用的rand方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
mt19937_64  engll(chrono::steady_clock::now().time_since_epoch().count());
mt19937  engi(chrono::steady_clock::now().time_since_epoch().count());
long long randll(long long l=LLONG_MIN,long long r=LLONG_MAX){
    /* generate a random number from [l,r] */
    if(l>r)swap(l,r);
    uniform_int_distribution<long long> rnd(l,r);
    return rnd(engll);
}
long long tRandll(long long l=LLONG_MIN,long long r=LLONG_MAX,long long t=0){
    /* random abs(t)+1 times and get the max(opposite)/min(negtive) value from [l,r], */
    if(l>r)swap(l,r);
    uniform_int_distribution<long long> rnd(l,r);
    long long ans;
    if(t>=0){
        ans = l;
        for(long long i = 1;i<=t+1;i++){
            ans=max((long long)rnd(engll),ans);
        }
    }else{
        t = abs(t);
        ans = r;
        for(long long i = 1;i<=t+1;i++){
            ans=min((long long)rnd(engll),ans);
        }
    }
    return ans;
}
int randi(int l=INT32_MIN,int r=INT32_MAX){
    /* generate a random number from [l,r] */
    if(l>r)swap(l,r);
    uniform_int_distribution<int> rnd(l,r);
    return rnd(engi);
}
int tRandi(int l=INT32_MIN,int r=INT32_MAX,int t=0){
    /* random abs(t)+1 times and get the max(opposite)/min(negtive) value from [l,r], */
    if(l>r)swap(l,r);
    uniform_int_distribution<int> rnd(l,r);
    int ans;
    if(t>=0){
        ans = l;
        for(int i = 1;i<=t+1;i++){
            ans=max((int)rnd(engi),ans);
        }
    }else{
        t = abs(t);
        ans = r;
        for(int i = 1;i<=t+1;i++){
            ans=min((int)rnd(engi),ans);
        }
    }
    return ans;
}

好戏开场

造一棵树

普通树（链/菊花）

$\textbf{Code}$ 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//tree.cpp

/* #define IOFILE *///Optional
int main(int argc,char* argv[]){
    int n = atoi(argv[1]);
    int t = atoi(argv[2]);
    #ifdef IOFILE
    ofstream fout;
    fout.open(argv[3]);
    #endif

    vector<int>fa(n);
    for(int i = 1;i<n;i++){
        fa[i] = tRandi(0,i-1,t);
    }

    vector<int>id(n);
    for(int i = 0;i<n;i++)id[i]=i+1;
    shuffle(id.begin(),id.end(),engi);

    struct EDGE{int a,b;};
    vector<EDGE>edge;

    for(int i = 1;i<n;i++){
        int fat = id[fa[i]],pos=id[i];
        if(randi()>0)swap(fat,pos);
        edge.push_back((EDGE){fat,pos});
    }
    shuffle(edge.begin(),edge.end(),engi);
    #ifdef IOFILE
    fout<<n<<"\n";
    for(EDGE i:edge){
        fout<<i.a<<" "<<i.b<<"\n";
    }
    #endif
    #ifndef IOFILE
    printf("%d\n",n);
    for(EDGE i:edge){
        printf("%d %d\n",i.a,i.b);
    }
    #endif
    return 0;
}

$\textbf{Require}$ 你需要喂给我：

1
2
tree.exe N T F
<!-- N节点个数, T随机次数(正的越大越链，负的越小越菊花), F(可选，若在程序中定义了IOFILE，则填入输出文件名) -->

蒲公英

造两棵树，一个是链，另一个是菊花
把链的端点和菊花的花心连起来

$\textbf{Code}$ 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//Dandelion.cpp
struct EDGE{int a,b;};
vector<EDGE>edge;

void makeTree1(int n,int l,vector<int> id){
    vector<int>fa(n);
    for(int i = 2;i<n;i++){
        fa[i] = i-1;
    }
    edge.push_back((EDGE){id[l],id[0]});
    for(int i = 2;i<n;i++){
        int fat = id[fa[i]+l-1],pos=id[i+l-1];
        if(randi()>0)swap(fat,pos);
        edge.push_back((EDGE){fat,pos});
    }
}
void makeTree2(int n,int l,vector<int> id){
    vector<int>fa(n);
    for(int i = 1;i<n;i++){
        int fat = id[0],pos=id[l+i-1];
        if(randi()>0)swap(fat,pos);
        edge.push_back((EDGE){fat,pos});
    }
}

int main(int argc,char* argv[]){
    int n = atoi(argv[1]);
    int root = atoi(argv[2]);
    #ifdef IOFILE
    ofstream fout;
    fout.open(argv[3]);
    #endif

    int lian = randi(1,n);
    int juhua = n-lian+1;

    vector<int>id(n);
    for(int i = 0;i<n;i++)id[i]=i+1;
    shuffle(id.begin(),id.end(),engi);

    for(int i = 0;i<n;i++){
        if(id[i]==root){
            swap(id[i],id[0]);
            break;
        }
    }
    makeTree1(lian,1,id);
    makeTree2(juhua,lian,id);

    shuffle(edge.begin(),edge.end(),engi);
    #ifdef IOFILE
    fout<<n<<" "<<root<<"\n";
    for(EDGE i:edge){
        fout<<i.a<<" "<<i.b<<"\n";
    }
    #endif
    #ifndef IOFILE
    printf("%d %d\n",n,root);
    for(EDGE i:edge){
        printf("%d %d\n",i.a,i.b);
    }
    #endif
    return 0;
}

$\textbf{Require}$ 你需要喂给我：

1
2
Dandelion.exe N R F
<!-- N节点个数, R(菊花的花心和链的端点), F(可选，若在程序中定义了IOFILE，则填入输出文件名) -->

造一张图

#

目录

归档

标签

English4
Git1
IT9
Linux2
Python1
Ubuntu2
Windows2
技巧7
数学16
生活6
算法28
语文1
题解13
×