随机数据生成与对拍¶

适用场景：

OI赛制比赛验证“高分解法”
OJ做题无法下载数据或下载数据规模过大
出题

随机数据生成¶

基础知识：

头文件cstdlib：

RAND_MAX：常量，Windows下一般为32767，Unix下一般为2147483647
rand()：返回\(0\sim RAND\_MAX\)之间的随机整数
srand(unsigned seed)：将seed用作随机种子，seed确定后随机序列便确定；不执行srand时seed默认为1

头文件ctime：

time(0)：返回Unix纪元(1970/1/1)到现在的秒数

随机数生成模板：

#include <cstdlib>
#include <ctime>
int random(int n) { return (long long)rand() * rand() % n; } // [0, n-1]
int main() {
  srand((unsigned)time(0));
  // ...
}

注：

生成随机实数：较大随机整数除以10的次幂

生成正数与负数：生成\([0,2n]\)间的随机整数，再减n

例1 随机生成整数序列：随机生成\(n\leqslant 10^5\)个绝对值小于等于\(10^9\)的整数。

int n = random(1e5) + 1; // [1, 10^5]
int m = 1e9;
for (int i = 1; i <= n; i++)
  a[i] = random(2 * m + 1) - m; // [-10^9, 10^9]

例2 随机生成区间列：随机生成\(m\)个\([1,n]\)的子区间（用于数据结构题）

for (int i = 1; i <= m; i++) {
  int l = random(n) + 1, r = random(n) + 1; // [1, n]
  if (l > r) swap(l, r);
  printf("%d %d\n", l, r);
}

例3 随机生成树：随机生成一棵\(n\)个点的树，用\(n\)点\(n-1\)边无向图形式输出，每条边附带\(10^9\)内的正整数权值

for (int i = 2; i <= n; i++) {
  int fa = random(i - 1) + 1; // ∀i∈[2, n]向fa∈[1, i-1]随机连一条边i<-fa
  int val = random(1e9) + 1;
  printf("%d %d %d\n", fa, i, val);
}

例4 随机生成图：随机生成一张\(n\)点\(m\)边的无向图，保证不存在重边、自环，且连通(\(5\leqslant n\leqslant m\leqslant \dfrac{n(n-1)}{4}\leqslant10^6\))

const int N = 1e6 + 5;
pair<int, int> e[N]; // 存边
map<pair<int, int>, bool> h; // 去重
for (int i = 1; i < n; i++) { // 生成树,保证连通
  int fa = random(i) + 1;
  e[i] = make_pair(fa, i + 1);
  h[e[i]] = h[make_pair(i + 1, fa)] = 1; // 正反向置1
}
for (int i = n; i <= m; i++) { // 生成剩余边
  int x, y;
  do {
    x = random(n) + 1, y = random(n) + 1;
  } while (x == y || h[make_pair(x, y)]); // 自环,重边
  e[i] = make_pair(x, y);
  h[e[i]] = h[make_pair(y, x)] = 1; // 正反向置1
}
random_shuffle(e + 1, e + m + 1); // 随机打乱
for (int i = 1; i <= m; i++)
  printf("%d %d\n", e[i].first, e[i].second);

注：

\(n\)过小时直接特判：此时完全图中边数与树的相差不大

\(m\)过大时效率过低：生成补图（完全图-原图）

树、图结构三类极端数据： + 链形数据：\(N\)节点\(N-1\)条边的长链——造成很大的递归深度：卡点分治 + 菊花形数据：\(1\)号为中心，\(2\sim N\)与之相连使得\(1\)号点度为\(N-1\)——卡缩点 + 蒲公英形数据：链+菊花

对拍¶

准备工作：sol.cpp,bf.cpp,random.cpp

sol.cpp->sol.exe(test)

graph LR;
    A(data.in)--input-->B[sol.exe]
    B-- output-->C(data.out)

bf.cpp->bf.exe(std)

graph LR;
    A(data.in)--input-->B[bf.exe]
    B-- output-->C(data.ans)

random.cpp->random.exe(generator)

graph LR;
    random.exe-- output-->C(data.in)

Windows系统对拍程序(cpp)：

for (int T = 1; T <= MAX_PADDING_ROUND; T++) {
  system("C:\\random.exe");
  double st = clock(); // Windows(ms),Unix(s)
  system("C:\\sol.exe");
  double ed = clock();
  system("C:\\bf.exe");
  if (system("fc C:\\data.out C:\\data.ans")) { // 一旦WA立即停止,此时data.in为引发错误的数据
    puts("Wrong Answer");
    return 0;
  }
  printf("Accepted, Test #%d, Time used %.0lfms\n", T, ed - st);
}

Windows系统对拍程序(python)：

import random
import os
import time
import filecmp

MAX_PADDING_ROUND = 1000


def compile():
    fp = os.path.dirname(__file__) # 获取当前路径
    os.system(f"cd {fp} && g++ std.cpp -o std.exe") # &&连接两条指令
    os.system(f"cd {fp} && g++ test.cpp -o test.exe")


def generate(n): # 将random.cpp的逻辑放在这里(n为数据规模)
    fp = os.path.dirname(__file__)
    with open(f"{fp}/in", "w") as f:
       # print(...,file=f)


if __name__ == "__main__":
    fp = os.path.dirname(__file__)
    compile() # 动态编译
    for i in range(MAX_PADDING_ROUND):
        print(f"TEST #{i}:")
        generate(i) # 可设定数据规模随对拍轮数变化
        os.system(f"cd {fp} && std.exe <in >ans") # 输入输出重定向,原程序可直接与stdin,stdout交互
        print("ans prepared") # 防止暴力或std卡死
        st = time.time() # 单位s
        os.system(f"cd {fp} && test.exe <in >out")
        ed = time.time()
        if not filecmp.cmp(f"{fp}/ans", f"{fp}/out"): # 文件内容比对
            print(f"WA!")
            break
        print(f"Time:{ed-st}sec")