随机数生成工具
随机数生成工具
一句话工具
用 mt19937 生成可控范围内的随机整数，主要用于造数据、对拍和构造压力测试。
为什么需要它
算法竞赛里写随机数，最常见的用途不是“随机算法”，而是“检查程序”。
当你写了一个高效解法，但不确定它是否正确时，可以再写一个暴力解法，然后不断随机生成小数据，让两个程序跑同一组输入。如果输出不同，就说明至少有一个程序错了。这个过程通常叫对拍。
随机数据生成器需要满足三个要求：
- 能方便地生成指定区间内的数。
- 每次运行的数据尽量不同，便于覆盖更多情况。
- 必要时可以固定种子，复现某一次错误数据。
mt19937 比 rand() 更稳定，周期更长，分布质量也更适合竞赛中的数据生成。
核心接口
模板里最常用的函数是：
1
int rnd(int l, int r);
它返回闭区间 [l, r] 中的一个随机整数。
典型用法：
1
2
int n = rnd(1, 10);
int x = rnd(-100, 100);
注意这里的右端点 r 是能取到的，这一点和很多半开区间写法不同。
使用步骤
- 先确定题目的数据规模，把随机范围设小一点，便于暴力解法跑得动。
- 随机生成输入数据。
- 把数据喂给暴力解法和正解。
- 比较输出，一旦不同就保存这组数据。
例如要测试一个数组算法，可以先生成：
1
2
3
4
int n = rnd(1, 8);
for (int i = 1; i <= n; ++i) {
cout << rnd(-10, 10) << " \n"[i == n];
}
小范围数据更容易暴露边界错误，也更方便手动分析。
代码实现
模板文件位置：/code/utils/random.cpp。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
// 生成 [l, r] 之间的随机整数。
int rnd(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
int main() {
int n = rnd(4, 7);
cout << n << "\n";
return 0;
}
常见改法
固定随机种子
模板默认用当前时间作为种子，每次运行生成的数据通常不同。调试某一次错误时，可以把种子改成固定值：
1
mt19937 rng(114514);
这样每次运行都会生成同一批数据，方便复现。
生成 long long
如果需要生成更大的整数，可以把接口改成：
1
2
3
long long rndll(long long l, long long r) {
return uniform_int_distribution<long long>(l, r)(rng);
}
生成随机排列
随机排列常用于测试排序、图论编号、序列操作：
1
2
3
vector<int> p(n);
iota(p.begin(), p.end(), 1);
shuffle(p.begin(), p.end(), rng);
按概率生成事件
如果需要让某个事件以概率 p 发生，可以使用：
1
2
3
bool hit(double p) {
return uniform_real_distribution<double>(0.0, 1.0)(rng) <= p;
}
随机图模板里就使用了这个写法。
注意事项
rnd(l, r)要求l <= r，否则行为不符合预期。- 对拍时优先生成小数据，不要一开始就把数据范围拉满。
- 固定种子适合复现错误；时间种子适合扩大随机覆盖面。
- 随机测试不能证明程序一定正确，它只能帮你更快发现错误。
- 如果题目边界很特殊，要手写边界数据补充测试，例如全相等、严格递增、全部为负数、最小规模等。
应用分类详解
随机数生成工具主要服务于“测试”，不是直接服务于某个算法模型。
一、对拍数据生成
典型模式： 有一个容易写但很慢的暴力解法，同时有一个复杂但高效的正解。
识别信号： 题目数据范围很大，但小范围下可以枚举；正解涉及贪心、数据结构、动态规划优化、复杂分类讨论。
核心建模： 把原题限制缩小，用随机数生成大量小样例，让暴力和正解相互校验。
二、边界压力测试
典型模式： 程序容易在极端输入上出错，例如数组长度为 1、全部元素相同、值域为负数、图没有边。
识别信号： 代码里有下标、区间、除法、取模、连通性判断、空集合判断。
核心建模： 用随机数生成普通数据，再手动混入极端数据，检查程序是否在所有分支上都能稳定运行。
三、构造随机操作序列
典型模式： 数据结构题需要支持多种操作，例如插入、删除、查询、区间修改。
识别信号： 题目输入由很多条操作组成，操作之间会改变后续状态。
核心建模： 随机选择操作类型，并维护一个合法状态，避免生成违反题意的操作。例如集合为空时不要生成删除操作。
参考
参考文档：