算法模板对拍算法模板对拍测试

随机数据生成器模板详解

靖2025-01-072025-01-07

随机数据生成器模板详解

1. 简介

随机数据生成器是对拍系统中的核心组件，用于生成高质量的测试数据。一个好的生成器应该能够产生多样化的测试用例，覆盖各种边界情况。

主要特点：

高质量随机数生成
可控的数据分布
支持多种数据类型
易于定制和扩展

2. 实现原理

2.1 基本概念

随机数引擎：
- 使用 mt19937_64
- 基于时间戳的种子
数据生成：
- 范围控制
- 分布控制

2.2 核心策略

随机性保证：
- 使用高质量随机数引擎
- 避免伪随机性
数据分布：
- 均匀分布
- 特殊情况构造

3. 模板代码

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
    // input your code
    
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    freopen("in.txt", "w", stdout);

    int t = 1;
    while (t--) {
        solve();
    }

    return 0;
}

4. 常用生成函数

4.1 基础随机数

// 生成[l, r]范围内的随机整数
template<typename T>
T rnd(T l, T r) {
    return std::uniform_int_distribution<T>(l, r)(rng);
}

// 生成随机浮点数
double rndReal(double l, double r) {
    return std::uniform_real_distribution<double>(l, r)(rng);
}

4.2 数据结构生成

// 生成随机数组
vector<int> rndArray(int n, int l, int r) {
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        a[i] = rnd(l, r);
    }
    return a;
}

// 生成随机排列
vector<int> rndPerm(int n) {
    vector<int> p(n);
    iota(p.begin(), p.end(), 1);
    shuffle(p.begin(), p.end(), rng);
    return p;
}

5. 常用生成模式

5.1 数组生成

void genArray() {
    int n = rnd(1, 100000);
    cout << n << "\n";
    
    // 生成随机数组
    auto a = rndArray(n, 1, 1000000);
    for (int x : a) {
        cout << x << " ";
    }
    cout << "\n";
}

5.2 图生成

void genTree() {
    int n = rnd(2, 100000);
    cout << n << "\n";
    
    // 生成随机树
    vector<pair<int,int>> edges;
    for (int i = 2; i <= n; i++) {
        int p = rnd(1, i-1);
        edges.emplace_back(p, i);
    }
    shuffle(edges.begin(), edges.end(), rng);
    
    for (auto [u, v] : edges) {
        cout << u << " " << v << "\n";
    }
}

6. 特殊数据生成

6.1 边界情况

void genEdgeCases() {
    // 最大数据
    int n = 100000;
    cout << n << "\n";
    for (int i = 0; i < n; i++) {
        cout << 1000000000 << " ";
    }
    cout << "\n";
}

6.2 退化情况

void genDegenerateCase() {
    // 生成链状树
    int n = 100000;
    cout << n << "\n";
    for (int i = 2; i <= n; i++) {
        cout << i-1 << " " << i << "\n";
    }
}