生成随机数（未完工）

参考

• 引用头文件（常用）

#include <stdlib.h>  //生成随机数、设定随机数种子
#include <ctime>  //生成随机数种子（1）
#include <time.h>  //生成随机数种子（2）
#include <unistd.h>  //等待（sleep(...)或usleep(...)），该头文件现在不常用

• 随机种子

srand(time(0) ^ clock());

注：随机种子为time(0) ^ clock()，这个随机种子可以再毫秒级别内生成（大概率）不同的随机种子。

• 取 $[l,r]$ 内的随机数

#define random(l, r) (rand() % ((LL)(r) - (LL)(l) + 1) + (LL)(l))

注：rand函数只能生成 $[1,32767]$ 内的随机数（见宏RAND_MAX），大概只能生成位数 $\leq 5$ 的随机数；测试程序：

LL ma = 0;
for(LL i = 1;i <= 200;i++){
    srand(time(0) ^ clock());
    LL t = rand();
    cout << t <<endl;
    ma = max(ma, t);
    usleep(10000);
}
cout << ma <<endl;

所以此处引用一个新方法：mt19937（2022/12/24：现在开始使用mt19937_64了，它可以生成 $[1,2^{64})$ 内的随机数，大一倍）。

其实它的语法和rand的语法差不多 （才怪），是这样的：

• 引用头文件（常用）

#include <random>  //生成随机数、设定随机数种子
#include <ctime>  //生成随机数种子（1）
#include <time.h>  //生成随机数种子（2）
#include <unistd.h>  //等待（sleep(...)或usleep(...)），该头文件现在不常用

• 随机种子

mt19937 _rand(time(0) ^ clock());

注：这个随机种子也可以再毫秒级别内生成（大概率）不同的随机种子

• 取 $[l,r]$ 内的随机数 （就差一个字符_而已）

#define random(l, r) (_rand() % ((LL)(r) - (LL)(l) + 1) + (LL)(l))

据测试，这个函数可以生成在unsigned int范围内的随机数（即可以生成 $[1,2^{32})$ 内的随机数），测试程序：

LL ma = 0;
for(LL i = 1;i <= 200;i++){
    mt19937 _rand(time(0) ^ clock());
    LL t = _rand();
    cout << t <<endl;
    ma = max(ma, t);
    usleep(10000);
}
cout << ma <<endl;

那就有人问了，很多人会把mt19937（这是一个类，即class）类型的_rand定义到外面，此时clock()=0，不就相当于随机种子是time(0)吗？那怎么样更好地取随机种子呢？其实C++里实现了这个类的。

这个类名叫random_device，用法如下：

random_device rand_seed;
mt19937 _rand(rand_seed());

这样随机种子就可以更好地生成了。

random_shuffle介绍 （待补）

shuffle介绍 （待补）

上面是一些语法，下面是一些模板和应用。

（下述文章需完善）

• 取一个长度在 $[milen,malen]$ 内的随机小写字母字符串

string get_rand_string_lower(LL milen, LL malen){
    string ret;
    LL len = random(milen, malen);
    for(LL i = 1;i <= len;i++) ret += 'a' + random(0, 25);
    return ret;
}

• 取一个长度在 $[milen,malen]$ 内的随机大写字母字符串

string get_rand_string_upper(LL milen, LL malen){
    string ret;
    LL len = random(milen, malen);
    for(LL i = 1;i <= len;i++) ret += 'A' + random(0, 25);
    return ret;
}

• 取一个长度在 $[milen,malen]$ 内的随机大小写字母+数字+下划线字符串

string get_rand_string_alpha_number_underline(LL milen, LL malen){
    string ret;
    LL len = random(milen, malen);
    for(LL i = 1;i <= len;i++){
        LL val = random(1, 63);
        if(val <= 26) ret += 'A' + val - 1;
        else if(val <= 52) ret += 'a' + val - 27;
        else if(val <= 62) ret += '0' + val - 53;
        else ret += '_';
    }
    return ret;
}

• 取一个长度在 $[milen,malen]$ 内的随机字符字符串

string get_rand_string_char(LL milen, LL malen){
    string ret;
    LL len = random(milen, malen);
    for(LL i = 1;i <= len;i++) ret += random(32, 126);
    return ret;
}

• 每 $0.01$ 秒（非严格）输出一个随机“密码”（包含大小写字母、数字、下划线）

while(true){
    mt19937 _rand(time(0) ^ clock());
    
    cout << get_rand_string_alpha_number_underline(5, 10) <<endl;
    
    usleep(10000);
}

• 输出严格单调递增序列（值域在 $[l,r]$ 内，一共要生成 $1 \leq x \leq r - l + 1$ 个数）

     //PriNT Strictly Monotonically Increasing Sequence
void pnt_smis(LL l, LL r, LL x){
    LL last = l - 1, cur;
    for(LL i = 1;i <= x;i++){
        cur = random(last + 1, r - (x - i));
        printf("%lld ", cur);
        last = cur;
    }
    puts("");
}

• 输出非严格单调递增序列（值域在 $[l,r]$ 内，一共要生成 $x$ 个数）

     //PriNT Non Strictly Monotonic Increasing Sequence
void pnt_nsmis(LL l, LL r, LL x){
    LL last = l, cur;
    for(LL i = 1;i <= x;i++){
        cur = random(last, r);
        printf("%lld ", cur);
        last = cur;
    }
    puts("");
}

• 输出“随机树”（点数为 $n$）

PII e[EDGES];
void pnt_random_tree(LL n){
    printf("%lld\n", n);
    for(LL i = 2;i <= n;i++) e[i - 1] = {random(1, i - 1), i};
    random_shuffle(e + 1, e + (n - 1) + 1);
    for(LL i = 1;i < n;i++){
        LL t = random(0, 1);
        if(t) swap(e[i].first, e[i].second);
    }
    for(LL i = 1;i < n;i++) printf("%lld %lld\n", e[i].first, e[i].second);
}

• 输出随机DAG（点数为 $n$）

  • 方法1（未经过测试，而且此处只用于纪念，可以直接忽略）：

  LL n;
  
  struct Node{ LL from, to, next; };
  Node a[M];
  LL ind;
  LL pre[N];
  void add(LL u, LL v){ ind++; a[ind] = {u, v, pre[u]}; pre[u] = ind; }
  
  bool flag = true, ret_flag = false;
  bool vis[N];
  void dfs(LL x){
      if(ret_flag) return;
      vis[x] = true;
      for(LL i = pre[x];i;i = a[i].next){
          LL to = a[i].to;
          if(vis[to]){ flag = false, ret_flag = true; return; }
          dfs(to);
          if(ret_flag) return;
      }
  }
  bool check(){
      flag = true, ret_flag = false;
      for(LL i = 1;i <= n;i++){
          if(!vis[i]) dfs(i);
          if(!flag) return false;
      }
      return true;
  }
  void pnt_random_DAG(){
      while(true){
          ind = 0;
          memset(pre, 0, sizeof(pre));
  
          memset(vis, false, sizeof(vis));
  
          n = random(1, 10);
          printf("%lld\n", n);
          for(LL i = 1;i <= n;i++){
              LL s = random(1, 5);
              printf("%lld ", s);
              while(s--){
                  LL to = random(1, n);
                  printf("%lld ", to);
                  add(i, to);
              }
              puts("");
          }
  
          if(check()) break;
          else system("cls");
      }
  }
  

  • 方法2 （推荐）：

  void pnt_random_DAG(){
      LL n = random(1, 1e5);
      printf("%lld %lld\n", n, random(1, 10));
      for(LL i = 1;i <= n;i++){
          LL s = random(1, 5);
          printf("%lld ", s);
          while(s--){
              LL to = random(i + 1, n);
              printf("%lld ", to);
          }
          puts("");
      }
  }