造数据相关知识
Python
CYaRon（头文件）
CYaRon：测试数据生成利器
C++
注意事项
Testlib（头文件）
Testlib——最强出题辅助工具库
批量生成数据
推荐使用命令行参数 + bat/sh 的方法。
例如：
gen.cpp:
#include "testlib.h"
using namespace std;
int n, m, k;
vector<int> p;
int main(int argc, char* argv[]) {
registerGen(argc, argv, 1);
int i;
n = atoi(argv[1]);
m = atoi(argv[2]);
k = rnd.next(1, n);
for (i = 1; i <= n; ++i) p.push_back(i);
shuffle(p.begin(), p.end());
// 使用 rnd.next() 进行 shuffle
printf("%d %d %d\n", n, m, k);
for (i = 0; i < n; ++i) {
printf("%d%c", p[i], " \n"[i == n - 1]);
// 把字符串当作数组用，中间空格，末尾换行，是一个造数据时常用的技巧
}
return 0;
}gen_scripts.bat:
gen 10 10 > 1.in
gen 1 1 > 2.in
gen 100 200 > 3.in
gen 2000 1000 > 4.in
gen 100000 100000 > 5.in这样做的好处是，对于不同的数据只需要写一个 generator，并且可以方便地修改某个测试点的参数。
----OI Wiki 出题
造数据（模板）
data1.cpp:（批量生成数据）
#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
namespace rad {
mt19937_64 R(time(0));
inline int Rand(int l, int r) {
uniform_int_distribution<int> distribution(l, r);
return distribution(R);
}
} using namespace rad;
int main() {
string in, out;
for (int i = 1; i <= 3; i ++) { // 序号
in.clear();
int j = i;
while (j) {
char m = j % 10 + '0';
in = m + in;
j /= 10;
}
out = in;
in += ".in";
out += ".out";
string A = "name"; // 文件名
string B = "name";
A = A + in, B = B + out;
in = A, out = B;
freopen(in.data(), "w", stdout);
system("data.exe"); // 数据生成器
fclose(stdout);
string Str = "std.exe < " + in + " > " + out; // 你的 std
system(Str.data());
}
}data.cpp:（模板）
#include <bits/stdc++.h>
#define int long long
using namespace std;
/*
* __int128 读写支持
* 注意：部分编译器可能不支持__int128类型
*/
/**
* @brief 从标准输入读取一个__int128类型的整数
* @details 该函数从标准输入中读取字符序列，解析为__int128类型的整数，支持负数。
* 它会跳过非数字字符，直到遇到数字或负号，并正确处理多位数字。
* @return 返回读取到的__int128类型整数
* @warning 如果输入超出__int128范围，可能导致未定义行为
*/
__int128 read() {
__int128 x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
/**
* @brief 将__int128类型的整数输出到标准输出
* @details 该函数将__int128类型的整数按十进制形式输出到标准输出，支持负数。
* 它通过递归方式处理多位数字，逐位输出。
* @param x 要输出的__int128类型整数
* @return 无返回值
*/
void write(__int128 x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
/*
* 128位整数随机生成器
* 功能：生成指定范围的128位整数
* 原理：组合两个64位随机数生成完整128位空间
*/
/**
* @brief 128位整数均匀分布随机数生成器类
* @details 该类用于生成指定范围内的__int128类型随机整数，利用两个64位随机数拼接生成128位随机数。
* 它基于C++的随机数引擎mt19937_64实现。
*/
class uniform_int128_distribution {
private:
using u128 = unsigned __int128;
u128 _min, _max; // 范围边界
mt19937_64 _gen; // 64位随机引擎
public:
/**
* @brief 构造函数，初始化随机数生成器的范围
* @details 验证输入范围的有效性，并初始化随机数引擎。
* @param a 随机数范围下限
* @param b 随机数范围上限
* @throws invalid_argument 如果范围无效（a > b）
*/
uniform_int128_distribution(__int128 a, __int128 b) : _gen(mt19937_64(random_device{}())) {
if (a > b) throw invalid_argument("Invalid range");
_min = static_cast<u128>(a);
_max = static_cast<u128>(b);
}
/**
* @brief 生成一个指定范围内的随机__int128整数
* @details 通过组合两个64位随机数生成128位随机数，并将其映射到指定范围。
* @return 返回一个在[min, max]范围内的__int128类型随机整数
*/
__int128 operator()() {
u128 rand_val = (static_cast<u128>(_gen()) << 64) | _gen();
u128 range = _max - _min + 1;
if (range == 0) return static_cast<__int128>(rand_val); // 处理全范围
return static_cast<__int128>(_min + rand_val % range);
}
};
/*
* 随机数生成命名空间
* 包含各种数据结构的随机生成方法
*/
namespace rad {
mt19937_64 R(random_device{}()); // 全局随机引擎
/*
* 基础随机数生成函数
* 模板参数：整数类型
* 参数：l-范围下限，r-范围上限
*/
/**
* @brief 生成指定范围内的随机整数
* @details 该函数生成类型为T的随机整数，范围为[l, r]，基于C++的均匀分布随机数生成器。
* @tparam T 整数类型（如int, long long等）
* @param l 随机数范围下限
* @param r 随机数范围上限
* @return 返回一个在[l, r]范围内的随机整数
* @throws static_assert 如果T不是整数类型
*/
template<typename T>
T Rand(T l, T r) {
static_assert(is_integral<T>::value, "T must be integral type");
uniform_int_distribution<T> dis(l, r);
return dis(R);
}
/**
* @brief 生成指定范围内的随机浮点数（long double特化版本）
* @details 该函数生成范围为[l, r]的随机浮点数，基于C++的均匀分布随机数生成器。
* @param l 随机数范围下限
* @param r 随机数范围上限
* @return 返回一个在[l, r]范围内的随机浮点数
*/
template<>
long double Rand<long double>(long double l, long double r) {
uniform_real_distribution<long double> dis(l, r);
return dis(R);
}
/*
* 生成128位整数
* 参数：l-下限，r-上限
* 注意：输出需使用write函数
*/
/**
* @brief 生成指定范围内的随机__int128整数
* @details 该函数利用uniform_int128_distribution类生成范围为[l, r]的随机__int128整数。
* @param l 随机数范围下限
* @param r 随机数范围上限
* @return 返回一个在[l, r]范围内的随机__int128整数
*/
__int128 Rand128(__int128 l, __int128 r) {
static uniform_int128_distribution gen(l, r);
return gen();
}
/*
* 容器操作函数
* Shuffle：随机打乱容器元素
* RandChoice：从容器中随机选取元素
*/
/**
* @brief 随机打乱向量中的元素
* @details 该函数使用C++的shuffle算法，基于全局随机引擎R，随机打乱向量v中的元素。
* @tparam T 向量元素类型
* @param v 待打乱的向量（引用传递，会修改原向量）
* @return 无返回值
*/
template<typename T>
void Shuffle(vector<T>& v) {
shuffle(v.begin(), v.end(), R);
}
/**
* @brief 从向量中随机选择一个元素
* @details 该函数从非空向量v中随机选择一个元素并返回其引用。
* @tparam T 向量元素类型
* @param v 待选择的向量（const引用，不会修改原向量）
* @return 返回随机选择的元素的const引用
* @throws runtime_error 如果向量为空
*/
template<typename T>
const T& RandChoice(const vector<T>& v) {
if (v.empty()) throw runtime_error("Cannot choose from empty vector");
return v[Rand<size_t>(0, v.size() - 1)];
}
/*
* 树生成器类
* 支持生成多种树结构
*/
class Tree {
public:
enum Type {
RANDOM, // 随机树（默认）
CHAIN, // 链状结构
STAR, // 星型结构
BINARY // 近似二叉树结构
};
// 边结构体：u起点，v终点，w边权
struct Edge {
int u, v, w;
Edge(int _u, int _v, int _w = 1) : u(_u), v(_v), w(_w) {}
};
/**
* @brief 生成指定类型的树结构
* @details 该函数根据指定的树类型生成一棵包含n个节点的树，支持随机树、链状树、星型树和近似二叉树。
* 边的权值在[min_w, max_w]范围内随机生成。
* @param n 节点数
* @param type 树类型，默认为随机树（RANDOM）
* @param min_w 最小边权，默认为1
* @param max_w 最大边权，默认为1e9
* @return 返回一个包含所有边的向量，每条边由Edge结构体表示
* @throws invalid_argument 如果节点数n <= 0
*/
static vector<Edge> generate(int n, Type type = RANDOM,
int min_w = 1, int max_w = 1e9) {
if (n <= 0) throw invalid_argument("Node count must be positive");
vector<Edge> edges;
switch (type) {
case CHAIN: // 链状生成
for (int i = 2; i <= n; ++i)
edges.emplace_back(i - 1, i, Rand(min_w, max_w));
break;
case STAR: // 星型生成
for (int i = 2; i <= n; ++i)
edges.emplace_back(1, i, Rand(min_w, max_w));
break;
case BINARY: { // 二叉树生成
queue<int> q;
q.push(1);
int cnt = 1;
while (cnt < n) {
int u = q.front();
q.pop();
int left = ++cnt;
edges.emplace_back(u, left, Rand(min_w, max_w));
q.push(left);
if (cnt >= n) break;
int right = ++cnt;
edges.emplace_back(u, right, Rand(min_w, max_w));
q.push(right);
}
break;
}
default: // 随机生成（Prufer序列方式）
for (int i = 2; i <= n; ++i) {
int fa = Rand(1LL, i - 1); // 使用 long long 字面量
edges.emplace_back(fa, i, Rand(min_w, max_w));
}
}
shuffle_edges(edges, n); // 打乱节点编号和边顺序
return edges;
}
// 定义输出方式的枚举
enum OutputFormat {
EDGE_LIST, // 边列表（默认）
ADJ_LIST, // 邻接表
PARENT_ARRAY // 父节点数组
};
/**
* @brief 封装的树生成和输出函数
* @details 该函数生成指定类型的树，并根据指定的输出格式打印树结构。
* 支持带文字描述和无文字描述的输出，通过verbose参数控制。
* @param n 节点数
* @param type 树类型
* @param format 输出格式
* @param min_w 最小边权，默认为1
* @param max_w 最大边权，默认为1e9
* @param verbose 是否输出带文字描述的版本，默认为true
* @throws invalid_argument 如果节点数n <= 0或输出格式无效
*/
static void generate_and_print_tree(int n, Type type, OutputFormat format,
int min_w = 1, int max_w = 1e9, bool verbose = true) {
// 生成树
auto edges = generate(n, type, min_w, max_w);
// 根据选择的格式输出树
switch (format) {
case EDGE_LIST: { // 边列表格式
if (verbose) {
cout << "边列表格式 (u - v 边权: w):\n";
for (const auto& e : edges) {
cout << e.u << " - " << e.v << " 边权: " << e.w << "\n";
}
} else {
// 无文字描述，仅输出数据
for (const auto& e : edges) {
cout << e.u << " " << e.v << " " << e.w << "\n";
}
}
break;
}
case ADJ_LIST: { // 邻接表格式
// 构建邻接表
vector<vector<pair<int, int >>> adj(n + 1); // 邻接表，pair<邻居, 边权>
for (const auto& e : edges) {
adj[e.u].emplace_back(e.v, e.w);
adj[e.v].emplace_back(e.u, e.w); // 无向图，双向添加
}
if (verbose) {
cout << "邻接表格式:\n";
for (int i = 1; i <= n; ++i) {
if (!adj[i].empty()) {
cout << "节点 " << i << " 的邻居: ";
for (const auto& [v, w] : adj[i]) {
cout << "(" << v << ", 边权: " << w << ") ";
}
cout << "\n";
}
}
}
else {
// 无文字描述，仅输出数据
// 每行格式：节点编号 邻居数量 邻居1 边权1 邻居2 边权2 ...
for (int i = 1; i <= n; ++i) {
if (!adj[i].empty()) {
cout << i << " " << adj[i].size();
for (const auto& [v, w] : adj[i]) {
cout << " " << v << " " << w;
}
cout << "\n";
}
}
}
break;
}
case PARENT_ARRAY: { // 父节点数组格式
// 构建父节点数组
vector<int> parent(n + 1, -1); // 父节点数组，-1 表示根节点
vector<int> weights(n + 1, 0); // 记录到父节点的边权
// 使用 BFS 确定父节点关系
vector<vector<pair<int, int >>> adj(n + 1); // 邻接表，用于 BFS
for (const auto& e : edges) {
adj[e.u].emplace_back(e.v, e.w);
adj[e.v].emplace_back(e.u, e.w); // 无向图，双向添加
}
// BFS 确定树的层次结构
queue<int> q;
vector<bool> visited(n + 1, false);
int root = edges[0].u; // 假设第一条边的起点是根（可以改进）
q.push(root);
visited[root] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
for (const auto& [v, w] : adj[u]) {
if (!visited[v]) {
visited[v] = true;
parent[v] = u;
weights[v] = w;
q.push(v);
}
}
}
if (verbose) {
cout << "父节点数组格式 (parent[i] 表示节点 i 的父节点):\n";
cout << "根节点: " << root << "\n";
cout << "节点 | 父节点 | 到父节点的边权\n";
for (int i = 1; i <= n; ++i) {
if (i != root) { // 根节点没有父节点
if (parent[i] != -1) { // 确保节点已访问
cout << i << " | " << parent[i] << " | " << weights[i] << "\n";
}
}
}
} else {
// 无文字描述，仅输出数据
// 格式：根节点编号\n节点编号 父节点编号 边权（仅非根节点）
cout << root << "\n";
for (int i = 1; i <= n; ++i) {
if (i != root && parent[i] != -1) {
cout << i << " " << parent[i] << " " << weights[i] << "\n";
}
}
}
break;
}
default:
throw invalid_argument("Unknown output format");
}
}
private:
/**
* @brief 边随机化处理：打乱节点编号和边顺序
* @details 该函数打乱树的节点编号和边顺序，确保节点编号在 [1, n] 内，增加随机性。
* @param edges 待处理的边向量（引用传递，会修改原向量）
* @param n 节点数
* @return 无返回值
*/
static void shuffle_edges(vector<Edge>& edges, int n) {
if (edges.empty()) return;
// 生成 1 到 n 的随机排列
vector<int> perm(n);
iota(perm.begin(), perm.end(), 1);
shuffle(perm.begin(), perm.end(), R);
// 映射节点编号
for (auto& e : edges) {
if (Rand(0LL, 1LL)) swap(e.u, e.v); // 随机方向
e.u = perm[e.u - 1]; // 映射到随机节点编号
e.v = perm[e.v - 1];
}
// 随机化边顺序
rad::Shuffle(edges); // 显式指定 rad 命名空间
}
};
/*
* 图生成器类
* 支持生成多种图结构
*/
class Graph {
public:
enum OutputFormat {
EDGE_LIST, // 默认边列表(每行u v w)
TRIPLE_LINES, // 三行分别输出u、v、w数组
COLUMNAR, // 列式存储：所有u一行，所有v一行，所有w一行
INTERLEAVED_LINE,// 所有边数据挤在一行
ADJACENCY_LIST // 邻接表格式
};
struct Edge {
int u, v, w;
};
static void print_array(const vector<int>& arr, const string& prefix, bool verbose) {
if(verbose) cout << prefix;
for(int x : arr) cout << x << " ";
cout << "\n";
}
/**
* @brief 生成完全随机图
* @details 该函数生成包含n个节点和m条边的随机图，边的权值在[min_w, max_w]范围内随机生成
* 支持有向图和无向图，通过directed参数控制
* @param n 节点数
* @param m 边数
* @param min_w 最小边权，默认为1
* @param max_w 最大边权，默认为1e9
* @param directed 是否生成有向图，默认为false
* @return 返回一个包含所有边的向量
* @throws invalid_argument 如果参数不合法
*/
static vector<Edge> random(int n, int m,
int min_w = 1, int max_w = 1e9,
bool directed = false) {
if (n <= 0) throw invalid_argument("Node count must be positive");
int max_edges = directed ? n*(n-1) : n*(n-1)/2;
if (m < 0 || m > max_edges)
throw invalid_argument("Invalid edge count");
vector<Edge> edges;
set<pair<int, int>> edge_set;
while (edges.size() < m) {
int u = Rand(1LL, n);
int v = Rand(1LL, n);
if (u == v) continue;
// 无向图统一方向存储
if (!directed && u > v) swap(u, v);
if (edge_set.count({u, v})) continue;
edges.push_back({u, v, Rand(min_w, max_w)});
edge_set.insert({u, v});
}
return edges;
}
/**
* @brief 生成并打印随机图（多格式版）
* @param output_format 输出格式枚举值
* @param sorted 是否按边权排序后输出
*/
static void generate_and_print_random_graph(
int n, int m,
OutputFormat output_format = EDGE_LIST,
bool sorted = false,
int min_w = 1, int max_w = 1e9,
bool directed = false,
bool verbose = true)
{
auto edges = random(n, m, min_w, max_w, directed);
// 预处理排序
if(sorted) {
sort(edges.begin(), edges.end(),
[](const Edge& a, const Edge& b){ return a.w < b.w; });
}
// 根据格式输出
switch(output_format) {
case EDGE_LIST:
if(verbose) cout << "边列表格式：\n";
for(const auto& e : edges)
cout << e.u << " " << e.v << " " << e.w << "\n";
break;
case TRIPLE_LINES: {
if(verbose) cout << "三行格式：\n";
// 生成u数组
for(const auto& e : edges) cout << e.u << " ";
cout << "\n";
// 生成v数组
for(const auto& e : edges) cout << e.v << " ";
cout << "\n";
// 生成w数组
for(const auto& e : edges) cout << e.w << " ";
cout << "\n";
break;
}
case COLUMNAR: {
if(verbose) cout << "列式存储：\n";
vector<int> us, vs, ws;
for(const auto& e : edges) {
us.push_back(e.u);
vs.push_back(e.v);
ws.push_back(e.w);
}
print_array(us, "U: ", verbose);
print_array(vs, "V: ", verbose);
print_array(ws, "W: ", verbose);
break;
}
case INTERLEAVED_LINE:
if(verbose) cout << "单行交错格式：\n";
for(const auto& e : edges)
cout << e.u << " " << e.v << " " << e.w << " ";
cout << "\n";
break;
case ADJACENCY_LIST: {
if(verbose) cout << "邻接表格式：\n";
map<int, vector<pair<int, int>>> adj;
for(const auto& e : edges) {
adj[e.u].emplace_back(e.v, e.w);
if(!directed)
adj[e.v].emplace_back(e.u, e.w);
}
for(const auto& [u, neighbors] : adj) {
cout << u << ": ";
for(const auto& [v, w] : neighbors)
cout << "(" << v << "," << w << ") ";
cout << "\n";
}
break;
}
}
}
/**
* @brief 生成连通图
* @details 该函数生成一个包含n个节点和m条边的连通图，边的权值在[min_w, max_w]范围内随机生成。
* 支持有向图和无向图，通过directed参数控制。
* @param n 节点数
* @param m 边数（必须 >= n-1 以保证连通性）
* @param min_w 最小边权，默认为1
* @param max_w 最大边权，默认为1e9
* @param directed 是否生成有向图，默认为false
* @return 返回一个包含所有边的向量，每条边由Edge结构体表示
* @throws invalid_argument 如果节点数n <= 0 或边数m < n-1
*/
static vector<Edge> connected(int n, int m,
int min_w = 1, int max_w = 1e9,
bool directed = false) {
if (n <= 0) throw invalid_argument("Node count must be positive");
if (m < n - 1) throw invalid_argument("Edge count must be at least n-1 for connectivity");
auto tree = Tree::generate(n); // 先生成树保证连通
vector<Edge> edges;
set<pair<int, int >> edge_set; // 用于去重
// 添加树边
for (auto& e : tree) {
edges.push_back({e.u, e.v, Rand(min_w, max_w)});
if (directed) {
edge_set.insert({e.u, e.v});
}
else {
edge_set.insert({min(e.u, e.v), max(e.u, e.v)});
}
}
// 补充剩余边
while ((int)edges.size() < m) {
int u = Rand(1LL, n);
int v = Rand(1LL, n);
if (u == v) continue; // 排除自环
if (!directed && u > v) swap(u, v); // 无向图统一顺序
if (edge_set.count({u, v})) continue; // 排除重边
edges.push_back({u, v, Rand(min_w, max_w)});
edge_set.insert({u, v});
}
return edges;
}
/**
* @brief 生成连通图并打印
* @details 该函数生成连通图，并根据verbose参数选择带文字描述或无文字描述的输出。
* @param n 节点数
* @param m 边数
* @param min_w 最小边权，默认为1
* @param max_w 最大边权，默认为1e9
* @param directed 是否生成有向图，默认为false
* @param verbose 是否输出带文字描述的版本，默认为true
* @throws invalid_argument 如果节点数n <= 0 或边数m < n-1
*/
static void generate_and_print_graph(int n, int m,
int min_w = 1, int max_w = 1e9,
bool directed = false, bool verbose = true) {
auto edges = connected(n, m, min_w, max_w, directed);
if (verbose) {
cout << "连通图边列表格式 (" << (directed ? "u -> v" : "u - v") << " 边权: w):\n";
for (const auto& e : edges) {
cout << e.u << (directed ? " -> " : " - ") << e.v << " 边权: " << e.w << "\n";
}
} else {
// 无文字描述，仅输出数据
for (const auto& e : edges) {
cout << e.u << " " << e.v << " " << e.w << "\n";
}
}
}
/**
* @brief 生成有向无环图（DAG）
* @details 该函数生成一个包含n个节点和m条边的有向无环图，边的权值在[min_w, max_w]范围内随机生成。
* 通过拓扑排序生成边，确保无环。
* @param n 节点数
* @param m 边数
* @param min_w 最小边权，默认为1
* @param max_w 最大边权，默认为1e9
* @return 返回一个包含所有边的向量，每条边由Edge结构体表示
* @throws invalid_argument 如果节点数n <= 0 或边数m < 0
*/
static vector<Edge> DAG(int n, int m, int min_w = 1, int max_w = 1e9) {
if (n <= 0) throw invalid_argument("Node count must be positive");
if (m < 0) throw invalid_argument("Edge count must be non-negative");
vector<int> ord(n);
iota(ord.begin(), ord.end(), 1);
Shuffle(ord); // 随机拓扑序
set<pair<int, int >> edges;
while (edges.size() < m) {
int u = Rand(0LL, n - 2); // 保证边的方向性
int v = Rand(u + 1, n - 1);
edges.insert({ord[u], ord[v]});
}
vector<Edge> res;
for (auto& [u, v] : edges)
res.push_back({u, v, Rand(min_w, max_w)});
return res;
}
/**
* @brief 生成有向无环图（DAG）并打印
* @details 该函数生成有向无环图，并根据verbose参数选择带文字描述或无文字描述的输出。
* @param n 节点数
* @param m 边数
* @param min_w 最小边权，默认为1
* @param max_w 最大边权，默认为1e9
* @param verbose 是否输出带文字描述的版本，默认为true
* @throws invalid_argument 如果节点数n <= 0 或边数m < 0
*/
static void generate_and_print_dag(int n, int m, int min_w = 1, int max_w = 1e9, bool verbose = true) {
auto edges = DAG(n, m, min_w, max_w);
if (verbose) {
cout << "有向无环图边列表格式 (u -> v 边权: w):\n";
for (const auto& e : edges) {
cout << e.u << " -> " << e.v << " 边权: " << e.w << "\n";
}
} else {
// 无文字描述，仅输出数据
for (const auto& e : edges) {
cout << e.u << " " << e.v << " " << e.w << "\n";
}
}
}
};
/*
* 数组生成器类
* 生成特殊结构的数组
*/
class Array {
public:
/**
* @brief 生成随机排列
* @details 该函数生成一个包含1到n的随机排列。
* @param n 元素个数
* @return 返回一个包含随机排列的向量
* @throws invalid_argument 如果元素个数n <= 0
*/
static vector<int> permutation(int n , int l , int r) {
if (n <= 0) throw invalid_argument("Size must be positive");
vector<int> res(n);
for(int i = 0 ; i < n ; i++) res[i] = Rand(l , r) ; // 生成l~r
Shuffle(res);
return res;
}
/**
* @brief 生成随机排列并打印
* @details 该函数生成一个包含1到n的随机排列，并根据verbose参数选择带文字描述或无文字描述的输出。
* @param n 元素个数
* @param verbose 是否输出带文字描述的版本，默认为true
* @throws invalid_argument 如果元素个数n <= 0
*/
static void generate_and_print_permutation(int n , int l , int r , bool verbose = true) {
auto perm = permutation(n , l , r);
if (verbose) {
cout << "随机排列: ";
for (int x : perm) cout << x << " ";
cout << "\n";
} else {
// 无文字描述，仅输出数据
for (int x : perm) cout << x << " ";
cout << "\n";
}
}
/**
* @brief 生成唯一元素数组（无重复）
* @details 该函数生成一个包含n个唯一元素的数组，元素值在[min_v, max_v]范围内随机生成。
* @tparam T 元素类型
* @param n 元素个数
* @param min_v 最小值
* @param max_v 最大值
* @return 返回一个包含唯一元素的向量
* @throws invalid_argument 如果元素个数n <= 0 或范围不足以生成n个唯一元素
*/
template<typename T>
static vector<T> unique(int n, T min_v, T max_v) {
if (n <= 0) throw invalid_argument("Size must be positive");
if (max_v - min_v + 1 < n) throw invalid_argument("Range too small for unique elements");
set<T> s;
while (s.size() < n)
s.insert(Rand(min_v, max_v));
vector<T> res(s.begin(), s.end());
Shuffle(res);
return res;
}
/**
* @brief 生成唯一元素数组并打印
* @details 该函数生成一个包含n个唯一元素的数组，并根据verbose参数选择带文字描述或无文字描述的输出。
* @tparam T 元素类型
* @param n 元素个数
* @param min_v 最小值
* @param max_v 最大值
* @param verbose 是否输出带文字描述的版本，默认为true
* @throws invalid_argument 如果元素个数n <= 0 或范围不足以生成n个唯一元素
*/
template<typename T>
static void generate_and_print_unique(int n, T min_v, T max_v, bool verbose = true) {
auto arr = unique(n, min_v, max_v);
if (verbose) {
cout << "唯一元素数组: ";
for (const auto& x : arr) cout << x << " ";
cout << "\n";
} else {
// 无文字描述，仅输出数据
for (const auto& x : arr) cout << x << " ";
cout << "\n";
}
}
/**
* @brief 生成山峰数组（先递增后递减）
* @details 该函数生成一个包含n个元素的山峰数组，数组先严格递增后严格递减，元素值在[1, max_val]范围内随机生成。
* @param n 元素个数
* @param max_val 最大值限制，默认为1e9
* @return 返回一个包含山峰数组的向量
* @throws invalid_argument 如果元素个数n <= 0 或n < 2
*/
static vector<int> mountain(int n, int max_val = 1e9) {
if (n <= 0) throw invalid_argument("Size must be positive");
if (n < 2) throw invalid_argument("Size must be at least 2 for mountain array");
vector<int> res(n);
int peak = Rand(1LL, n - 2); // 随机山峰位置
// 生成递增部分
for (int i = 0; i <= peak; ++i) res[i] = Rand(1LL, max_val);
// 生成递减部分
for (int i = peak + 1; i < n; ++i) res[i] = Rand(1LL, res[i - 1]);
// 排序形成山峰
sort(res.begin(), res.begin() + peak + 1);
sort(res.begin() + peak + 1, res.end(), greater<>());
return res;
}
/**
* @brief 生成山峰数组并打印
* @details 该函数生成一个山峰数组，并根据verbose参数选择带文字描述或无文字描述的输出。
* @param n 元素个数
* @param max_val 最大值限制，默认为1e9
* @param verbose 是否输出带文字描述的版本，默认为true
* @throws invalid_argument 如果元素个数n <= 0 或n < 2
*/
static void generate_and_print_mountain(int n, int max_val = 1e9, bool verbose = true) {
auto arr = mountain(n, max_val);
if (verbose) {
cout << "山峰数组: ";
for (int x : arr) cout << x << " ";
cout << "\n";
} else {
// 无文字描述，仅输出数据
for (int x : arr) cout << x << " ";
cout << "\n";
}
}
};
/*
* 实用工具函数
*/
/**
* @brief 生成高精度浮点数（保留x位小数）
* @details 该函数生成一个范围为[l, r]的高精度浮点数，保留x位小数。
* @param l 范围下限
* @param r 范围上限
* @param x 小数位数
* @return 返回一个保留x位小数的随机浮点数
*/
long double RandX(long double l, long double r, int x) {
long double scale = pow(10, x);
return round(Rand<long double>(l * scale, r * scale)) / scale;
}
/**
* @brief 生成高精度浮点数并打印
* @details 该函数生成一个高精度浮点数，并根据verbose参数选择带文字描述或无文字描述的输出。
* @param l 范围下限
* @param r 范围上限
* @param x 小数位数
* @param verbose 是否输出带文字描述的版本，默认为true
*/
void generate_and_print_randx(long double l, long double r, int x, bool verbose = true) {
long double val = RandX(l, r, x);
if (verbose) {
cout << "随机高精度浮点数 (保留 " << x << " 位小数): " << fixed << setprecision(x) << val << "\n";
} else {
// 无文字描述，仅输出数据
cout << fixed << setprecision(x) << val << "\n";
}
}
/**
* @brief 生成随机字符串
* @details 该函数生成一个长度为len的随机字符串，字符从charset中随机选择。
* @param len 字符串长度
* @param charset 字符集，默认为小写字母
* @return 返回一个随机字符串
* @throws invalid_argument 如果长度len < 0
*/
string RandString(int len, const string& charset = "abcdefghijklmnopqrstuvwxyz") {
if (len < 0) throw invalid_argument("Length must be non-negative");
string s;
for (int i = 0; i < len; ++i)
s += charset[Rand<size_t>(0, charset.size() - 1)];
return s;
}
/**
* @brief 生成随机字符串并打印
* @details 该函数生成一个随机字符串，并根据verbose参数选择带文字描述或无文字描述的输出。
* @param len 字符串长度
* @param charset 字符集，默认为小写字母
* @param verbose 是否输出带文字描述的版本，默认为true
* @throws invalid_argument 如果长度len < 0
*/
void generate_and_print_randstring(int len, const string& charset = "abcdefghijklmnopqrstuvwxyz", bool verbose = true) {
string s = RandString(len, charset);
if (verbose) {
cout << "随机字符串: " << s << "\n";
} else {
// 无文字描述，仅输出数据
cout << s << "\n";
}
}
/**
* @brief 生成随机颜色（十六进制格式）
* @details 该函数生成一个随机的十六进制颜色代码，格式为 #RRGGBB。
* @return 返回一个随机颜色代码字符串
*/
string RandColorHex() {
char buf[8];
snprintf(buf, sizeof(buf), "#%02X%02X%02X",
static_cast<int>(Rand(0LL, 255LL)),
static_cast<int>(Rand(0LL, 255LL)),
static_cast<int>(Rand(0LL, 255LL)));
return string(buf);
}
/**
* @brief 生成随机颜色并打印
* @details 该函数生成一个随机颜色代码，并根据verbose参数选择带文字描述或无文字描述的输出。
* @param verbose 是否输出带文字描述的版本，默认为true
*/
void generate_and_print_randcolor(bool verbose = true) {
string color = RandColorHex();
if (verbose) {
cout << "随机颜色 (十六进制): " << color << "\n";
} else {
// 无文字描述，仅输出数据
cout << color << "\n";
}
}
/*
* 示例程序：展示如何使用上述功能生成数据
*/
/**
* @brief 展示所有数据生成功能的完整示例
* @param verbose 是否显示详细描述
* @param extreme 是否包含边界测试用例
*/
void Example(bool verbose = true, bool extreme = false) {
cout << (verbose ? "===== 数据生成器示例演示 =====\n" : "");
// ===== 1. 树生成示例 =====
cout << (verbose ? "\n1. 树结构生成示例：\n" : "");
{
// 常规测试用例
Tree::generate_and_print_tree(5, Tree::RANDOM, Tree::EDGE_LIST, 1, 10, verbose);
Tree::generate_and_print_tree(6, Tree::CHAIN, Tree::ADJ_LIST, 1, 100, verbose);
Tree::generate_and_print_tree(4, Tree::STAR, Tree::PARENT_ARRAY, 1, 50, verbose);
// 边界测试用例
if(extreme) {
cout << (verbose ? "\n[边界测试] 大树生成：\n" : "");
Tree::generate_and_print_tree(100000, Tree::BINARY, Tree::EDGE_LIST, 1, 1e9, false);
}
}
// ===== 2. 图生成示例 =====
cout << (verbose ? "\n2. 图结构生成示例：\n" : "");
{
// 常规测试用例
rad::Graph::generate_and_print_random_graph(5, 7, rad::Graph::EDGE_LIST, false, 1, 20, false, verbose);
rad::Graph::generate_and_print_random_graph(4, 6, rad::Graph::TRIPLE_LINES, true, 1, 50, true, verbose);
// 边界测试用例
if(extreme) {
cout << (verbose ? "\n[边界测试] 稠密图生成：\n" : "");
rad::Graph::generate_and_print_random_graph(1000, 499500, rad::Graph::COLUMNAR, false, 1, 1e9, false, false);
}
}
// ===== 3. 数组生成示例 =====
cout << (verbose ? "\n3. 特殊数组生成示例：\n" : "");
{
// 常规测试用例
Array::generate_and_print_permutation(5 , 1 , 5 , verbose);
Array::generate_and_print_unique(5, 1, 10, verbose);
Array::generate_and_print_mountain(6, 100, verbose);
// 边界测试用例
if(extreme) {
cout << (verbose ? "\n[边界测试] 大规模山峰数组：\n" : "");
Array::generate_and_print_mountain(1000000, 1e9, false);
}
}
// ===== 4. 高级功能示例 =====
cout << (verbose ? "\n4. 高级功能示例：\n" : "");
{
// 128位整数
cout << (verbose ? "128位随机整数: " : "");
write(Rand128(1e18, 1e20));
cout << "\n";
// 高精度浮点数
generate_and_print_randx(0.0, 1.0, 5, verbose);
// 随机字符串
generate_and_print_randstring(10, "ACGT", verbose); // DNA序列
// 特殊测试用例
if(extreme) {
cout << (verbose ? "\n[压力测试] 超长随机字符串：\n" : "");
generate_and_print_randstring(1000000, "01", false); // 1MB二进制数据
}
}
// ===== 5. 连通性测试示例 =====
cout << (verbose ? "\n5. 连通性测试示例：\n" : "");
{
auto edges = Graph::connected(10, 15, 1, 100);
if(verbose) {
cout << "连通图验证（边数=" << edges.size() << "）：\n";
for(auto& e : edges)
cout << e.u << "-" << e.v << "(" << e.w << ") ";
cout << "\n";
} else {
for(auto& e : edges)
cout << e.u << " " << e.v << " " << e.w << "\n";
}
}
cout << (verbose ? "\n===== 示例演示结束 =====\n" : "");
}
void ZExample() {
// 运行所有示例，带文字描述
cout << "运行所有示例（带文字描述）：\n";
Example(true , 0);
// 运行所有示例，无文字描述
cout << "\n运行所有示例（无文字描述）：\n";
Example(false , 0);
}
}
/**
* @brief 主函数：运行示例并生成数据
*/
signed main(){
// rad :: ZExample() ;
return 0;
}随机数生成命名空间 rad
| 函数名 | 功能描述 | 参数说明 | 返回值 | 异常/限制 |
|---|---|---|---|---|
Rand<T>(l, r) |
生成指定范围的随机整数 | T l: 下限<br>T r: 上限 |
类型 T 的随机整数 |
static_assert 检查整数类型 |
Rand<long double>(l, r) |
生成指定范围的随机浮点数 | long double l: 下限<br>long double r: 上限 |
long double 随机浮点数 |
无 |
Rand128(l, r) |
生成128位随机整数 | __int128 l: 下限<br>__int128 r: 上限 |
__int128 随机整数 |
需用 write() 输出 |
Shuffle(v) |
随机打乱容器元素 | vector<T>& v: 待打乱的容器 |
无（原地修改） | 无 |
RandChoice(v) |
从容器中随机选择元素 | const vector<T>& v: 非空容器 |
const T& 随机元素 |
runtime_error 如果容器为空 |
RandX(l, r, x) |
生成保留x位小数的随机浮点数 | long double l: 下限<br>long double r: 上限<br>int x: 小数位数 |
long double 随机浮点数 |
无 |
RandString(len, charset) |
生成随机字符串 | int len: 长度<br>const string& charset: 字符集（默认小写字母） |
string 随机字符串 |
invalid_argument 如果长度<0 |
RandColorHex() |
生成随机十六进制颜色 | 无 | string 格式 #RRGGBB |
无 |
树生成器类 Tree
| 函数名 | 功能描述 | 参数说明 | 返回值 | 异常/限制 |
|---|---|---|---|---|
generate(n, type, min_w, max_w) |
生成指定类型的树 | n: 节点数<br>type: 树类型<br>min_w/max_w: 边权范围 |
vector<Edge> 边列表 |
invalid_argument 如果节点数≤0 |
generate_and_print_tree(...) |
生成并输出树 | 同 generate 增加：<br>format: 输出格式<br>verbose: 是否显示描述 |
无（输出到stdout） | 同 generate |
树类型枚举 Type:
RANDOM: 随机树（默认）CHAIN: 链状结构STAR: 星型结构BINARY: 近似二叉树
输出格式枚举 OutputFormat:
EDGE_LIST: 边列表（默认）ADJ_LIST: 邻接表PARENT_ARRAY: 父节点数组
图生成器类 Graph
| 函数名 | 功能描述 | 参数说明 | 返回值 | 异常/限制 |
|---|---|---|---|---|
random(n, m, min_w, max_w, directed) |
生成完全随机图 | n: 节点数<br>m: 边数<br>min_w/max_w: 边权范围<br>directed: 是否有向 |
vector<Edge> 边列表 |
invalid_argument 如果边数超过理论最大值 |
connected(...) |
生成连通图 | 同 random |
vector<Edge> 边列表 |
invalid_argument 如果边数<节点数-1 |
DAG(...) |
生成有向无环图 | 同 random |
vector<Edge> 边列表 |
invalid_argument 如果边数<0 |
generate_and_print_*(...) |
生成并输出图（多种格式） | 增加：<br>output_format: 输出格式<br>sorted: 是否按边权排序 |
无（输出到stdout） | 同对应生成函数 |
输出格式枚举 OutputFormat:
EDGE_LIST: 每行u v w（默认）TRIPLE_LINES: 三行分别输出u/v/w数组COLUMNAR: 列式存储（所有u一行，所有v一行...）INTERLEAVED_LINE: 单行交错格式ADJACENCY_LIST: 邻接表格式
数组生成器类 Array
| 函数名 | 功能描述 | 参数说明 | 返回值 | 异常/限制 |
|---|---|---|---|---|
permutation(n, l, r) |
生成l~r的随机排列 | n: 元素个数<br>l/r: 值域范围 |
vector<int> 随机排列 |
invalid_argument 如果n≤0 |
unique(n, min_v, max_v) |
生成唯一元素数组 | n: 元素个数<br>min_v/max_v: 值域范围 |
vector<T> 唯一元素数组 |
invalid_argument 如果值域不足以生成n个唯一元素 |
mountain(n, max_val) |
生成山峰数组（先增后减） | n: 元素个数<br>max_val: 最大值限制 |
vector<int> 山峰数组 |
invalid_argument 如果n<2 |
辅助函数
| 函数名 | 功能描述 | 参数说明 | 返回值 | 备注 |
|---|---|---|---|---|
read() |
读取128位整数 | 无 | __int128 |
支持负数输入 |
write(x) |
输出128位整数 | __int128 x: 要输出的数 |
无 | 支持负数输出 |
generate_and_print_*(...) |
各类型的生成并输出快捷函数 | 对应生成函数的参数+verbose控制输出格式 |
无 | 简化输出流程 |
使用场景示例
// 1. 生成随机树（10节点，边权1~100）
auto tree = rad::Tree::generate(10, rad::Tree::RANDOM, 1, 100);
// 2. 生成连通图（100节点，200边，无向）
auto graph = rad::Graph::connected(100, 200, 1, 100);
// 3. 输出128位大整数
__int128 big_num = rad::Rand128(1e30, 1e40);
rad::write(big_num);
// 4. 快速测试（带描述）
rad::Example(true, true); // 启用边界测试造数据模板