造数据相关知识
__Aha__
·
2025-04-25 15:38:22
·
科技·工程
有错误请指出，立马修改！
如果有想添加的函数或函数伪随机请私信。
Python
CYaRon（头文件）
CYaRon：测试数据生成利器
C++
注意事项
Testlib（头文件）
Testlib——最强出题辅助工具库
批量生成数据
推荐使用命令行参数 + bat/sh 的方法。
例如：
gen.cpp:
#include "testlib.h"
using namespace std;
int n, m, k;
vector
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
#include
using namespace std;
namespace rad {
mt19937_64 R(time(0));
inline int Rand(int l,int r) {
uniform_int_distribution
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
#include
#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;
__int128 _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 = a;
_max = b;
}
/**
* @brief 生成一个指定范围内的随机__int128整数
* @details 通过组合两个64位随机数生成128位随机数，并将其映射到指定范围。
* @return 返回一个在[min, max]范围内的__int128类型随机整数
*/
__int128 operator()() {
u128 range = static_cast
u128 rand_val = (static_cast
return _min + static_cast<__int128>(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
T Rand(T l, T r) {
static_assert(is_integral
uniform_int_distribution
return dis(R);
}
/**
* @brief 生成指定范围内的随机浮点数（long double特化版本）
* @details 该函数生成范围为[l, r]的随机浮点数，基于C++的均匀分布随机数生成器。
* @param l 随机数范围下限
* @param r 随机数范围上限
* @return 返回一个在[l, r]范围内的随机浮点数
*/
template<>
long double Rand
uniform_real_distribution
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
void Shuffle(vector
shuffle(v.begin(), v.end(), R);
}
/**
* @brief 从向量中随机选择一个元素
* @details 该函数从非空向量v中随机选择一个元素并返回其引用。
* @tparam T 向量元素类型
* @param v 待选择的向量（const引用，不会修改原向量）
* @return 返回随机选择的元素的const引用
* @throws runtime_error 如果向量为空
*/
template
const T& RandChoice(const vector
if (v.empty()) throw runtime_error("Cannot choose from empty vector");
return v[Rand
}
/*
* 树生成器类
* 支持生成多种树结构
*/
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
if (n <= 0) throw invalid_argument("Node count must be positive");
vector
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
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) edges.emplace_back(Rand(1LL, i - 1), 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";
break;
}
case ADJ_LIST: { // 邻接表格式
// 构建邻接表
vector
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
vector
// 使用 BFS 确定父节点关系
vector
for (const auto& e : edges) {
adj[e.u].emplace_back(e.v, e.w);
adj[e.v].emplace_back(e.u, e.w); // 无向图，双向添加
}
queue
vector
int root = 1; // 固定选择节点1作为根
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根节点: " << root << "\n节点 | 父节点 | 到父节点的边权\n";
for (int i = 1; i <= n; ++i) if (i != root && 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
if (edges.empty()) return;
// 生成 1 到 n 的随机排列
vector
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);
}
};
/*
* 图生成器类
* 支持生成多种图结构
*/
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
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
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
set
while (edges.size() < m) {
int u = Rand(1LL, n), 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";
for (const auto& e : edges) cout << e.u << " "; cout << "\n";
for (const auto& e : edges) cout << e.v << " "; cout << "\n";
for (const auto& e : edges) cout << e.w << " "; cout << "\n";
break;
case COLUMNAR: {
if (verbose) cout << "列式存储：\n";
vector
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
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
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
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), 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
if (n <= 0) throw invalid_argument("Node count must be positive");
if (m < 0) throw invalid_argument("Edge count must be non-negative");
vector
iota(ord.begin(), ord.end(), 1);
Shuffle(ord);
set
while (edges.size() < m) {
int u = Rand(0LL, n - 2);
int v = Rand(u + 1, n - 1);
edges.insert({ord[u], ord[v]});
}
vector
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";
}
}
/**
* @brief 生成用于挑战SPFA算法的菊花链图 (Daisy Chain Graph)
* @details 该函数生成一种特殊的有向图，旨在使SPFA算法达到其O(V*E)的最坏时间复杂度。
* 其结构为：一个源点(1)，一个中心节点(n)，以及k条连接它们的“链”。
* 1. 源点1连接到第一条链的开头。
* 2. 每条链由若干节点串联而成，边权较小。
* 3. 每条链的末端连接到中心节点n，边权也较小。
* 4. 中心节点n再连接回除第一条链外的所有链的开头，形成“菊花瓣”间的通路。
* 这种结构会导致SPFA在更新中心节点n的距离后，需要沿着“通路”反复更新所有链上节点的距离，
* 从而导致节点被大量重复入队，性能急剧下降。
* 通常，以节点1为源点运行SPFA会触发最坏情况。
* @param n 节点总数，节点编号为 1 到 n。
* @param k “菊花”的“花瓣”数量，即链的数量。推荐 k 约为 sqrt(n)。
* @param min_w 最小边权，默认为0。
* @param max_w 最大边权，默认为100。建议使用较小的非负权值。
* @return 返回一个包含所有边的向量，专门用于测试SPFA。
* @throws invalid_argument 如果参数不合法 (e.g., n, k 太小)。
*/
static vector
if (n < 3 || k < 2 || n <= k) throw invalid_argument("For Hack-SPFA graph: n must be >= 3, k >= 2, n > k.");
if ((n - 2) / k < 1) throw invalid_argument("Each chain must have at least one node.");
vector
int center_node = n, current_node_idx = 1;
int base_chain_len = (n - 2) / k, remainder = (n - 2) % k;
vector
for (int i = 0; i < k; ++i) {
int chain_start = current_node_idx;
chain_starts.push_back(chain_start);
int current_chain_len = base_chain_len + (i < remainder ? 1 : 0);
int u = chain_start;
for (int j = 0; j < current_chain_len - 1; ++j) {
int v = u + 1;
edges.push_back({u, v, (int)Rand(min_w, max_w)});
u = v;
}
edges.push_back({u, center_node, (int)Rand(min_w, max_w)});
current_node_idx = u + 1;
}
for (size_t i = 1; i < chain_starts.size(); ++i)
edges.push_back({center_node, chain_starts[i], (int)Rand(min_w, max_w)});
return edges;
}
/**
* @brief 生成并打印用于挑战SPFA算法的图
* @details 调用 hack_spfa 函数生成图，并根据verbose参数选择带文字描述或无文字描述的输出。
* @param n 节点总数
* @param k 链的数量
* @param min_w 最小边权
* @param max_w 最大边权
* @param verbose 是否输出带文字描述的版本，默认为true
*/
static void generate_and_print_hack_spfa(int n, int k, int min_w = 0, int max_w = 100, bool verbose = true) {
auto edges = hack_spfa(n, k, min_w, max_w);
int m = edges.size();
if (verbose) {
cout << "SPFA-Hack (菊花链图) 边列表格式 (u -> v 边权: w):\n总节点数: " << n << ", 总边数: " << m << "\n建议以节点 1 作为源点进行最短路计算。\n";
for (const auto& e : edges) cout << e.u << " -> " << e.v << " 边权: " << e.w << "\n";
} else {
cout << n << " " << m << "\n";
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
if (n <= 0) throw invalid_argument("Size must be positive");
vector
for (int i = 0; i < n; ++i) res[i] = Rand(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";
}
/**
* @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
static vector
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
while (s.size() < n) s.insert(Rand(min_v, max_v));
vector
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
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";
}
/**
* @brief 生成山峰数组
* @details 该函数生成一个包含n个元素的山峰数组，数组先递增后递减或先递减后递增，
* 元素值在[min_val, max_val]范围内随机生成。如果峰值位置选择不当，会尝试不同的位置。
* @param n 元素个数
* @param min_val 最小值限制，默认为0
* @param max_val 最大值限制，默认为1e9
* @param is_peak_max 是否生成峰值最大的数组（true为先增后减，false为先减后增），默认为true
* @param strict 是否严格单调，默认为true
* @return 返回一个包含山峰数组的向量
* @throws invalid_argument 如果元素个数n <= 0 或n < 2 或 min_val >= max_val 或无法生成满足条件的序列
*/
static vector
if (n <= 0 || n < 2 || min_val >= max_val) throw invalid_argument("Invalid parameters for mountain array");
if (strict && (long long)max_val - min_val < n - 1) throw invalid_argument("Range too small for strict monotonic sequence");
vector
int peak = Rand(1LL, n - 2); // 确保峰值不在两端
if (is_peak_max) {
res[peak] = max_val;
for (int i = peak - 1; i >= 0; --i) res[i] = strict ? res[i + 1] - Rand(1LL, (max_val - min_val) / (peak + 1)) : Rand(min_val, res[i + 1]);
for (int i = peak + 1; i < n; ++i) res[i] = strict ? res[i - 1] - Rand(1LL, (max_val - min_val) / (n - peak)) : Rand(min_val, res[i - 1]);
} else {
res[peak] = min_val;
for (int i = peak - 1; i >= 0; --i) res[i] = strict ? res[i + 1] + Rand(1LL, (max_val - min_val) / (peak + 1)) : Rand(res[i + 1], max_val);
for (int i = peak + 1; i < n; ++i) res[i] = strict ? res[i - 1] + Rand(1LL, (max_val - min_val) / (n - peak)) : Rand(res[i - 1], max_val);
}
return res;
}
/**
* @brief 生成山峰数组并打印
* @details 该函数生成一个山峰数组，并根据verbose参数选择带文字描述或无文字描述的输出。
* @param n 元素个数
* @param min_val 最小值限制，默认为0
* @param max_val 最大值限制，默认为1e9
* @param is_peak_max 是否生成峰值最大的数组，默认为true
* @param strict 是否严格单调，默认为true
* @param verbose 是否输出带文字描述的版本，默认为true
* @throws invalid_argument 如果元素个数n <= 0 或n < 2 或 min_val >= max_val 或无法生成满足条件的序列
*/
static void generate_and_print_mountain(int n, int min_val = 0, int max_val = 1e9, bool is_peak_max = true, bool strict = true, bool verbose = true) {
auto arr = mountain(n, min_val, max_val, is_peak_max, strict);
if (verbose) cout << (is_peak_max ? "山峰" : "山谷") << "数组: ";
for (int x : arr) cout << x << " ";
cout << "\n";
}
};
/**
* @class StringGenerator
* @brief 字符串生成器类
* @details 提供生成各类字符串及字符串集合的功能，包括随机字符串，
* 以及专门用于导致标准库哈希表（如 std::unordered_map）哈希碰撞的特殊字符串集。
*/
class StringGenerator {
public:
/**
* @brief 生成一个指定长度的随机字符串。
* @param len 要生成的字符串的长度。
* @param charset 用于生成字符串的字符集，默认为大小写字母。
* @return 一个随机生成的字符串。
*/
static string random(int len, const string& charset = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ") {
if (len < 0 || charset.empty()) throw invalid_argument("Invalid parameters for random string");
string result;
result.reserve(len);
for (int i = 0; i < len; ++i) result += charset[Rand(0LL, (int)(charset.length() - 1))];
return result;
}
/**
* @brief 生成一个随机字符串列表。
* @param count 要生成的字符串数量。
* @param min_len 每个字符串的最小长度。
* @param max_len 每个字符串的最大长度。
* @param charset 使用的字符集。
* @return 一个包含随机字符串的向量。
*/
static vector
if (count < 0 || min_len < 0 || max_len < min_len) throw invalid_argument("Invalid parameters for random list");
vector
result.reserve(count);
for (int i = 0; i < count; ++i) result.push_back(random(Rand(min_len, max_len), charset));
return result;
}
/**
* @brief 生成一组旨在导致哈希碰撞的字符串
* @details 通过生成短字符串并按哈希值低位分组，构造一组长字符串，增加在 std::unordered_map 中落入同一桶的概率。
* @param count 要生成的字符串数量
* @param base_len 每个字符串的大致长度
* @param charset 用于生成字符串的字符集
* @return 返回一个可能导致哈希碰撞的字符串向量
* @throws invalid_argument 如果参数无效
*/
static vector
if (count < 0 || base_len < 0 || charset.empty()) throw invalid_argument("无效的参数");
if (count == 0) return {};
// 生成短字符串（长度为3）并按哈希值低位分组
const int short_len = 3;
const size_t mask = (1ULL << 20) - 1; // 使用低20位进行分组，假设桶数为2的幂
map
// 生成所有可能的长度为3的字符串（限制样本量以提高效率）
size_t max_samples = min((size_t)1000000, (size_t)pow(charset.size(), short_len));
set
vector
for (size_t i = 0; i < max_samples; ++i) {
string s;
for (int j = 0; j < short_len; ++j) {
s += chars[Rand(0LL, (int)charset.size() - 1)];
}
if (used_strings.insert(s).second) {
size_t hash = std::hash
hash_groups[hash].push_back(s);
}
}
// 找到包含最多字符串的组
size_t max_size = 0;
size_t selected_hash = 0;
for (const auto& [hash, group] : hash_groups) {
if (group.size() > max_size) {
max_size = group.size();
selected_hash = hash;
}
}
// 如果没有找到至少有两个字符串的组，回退到随机字符串
if (max_size < 2) {
vector
set
while (result.size() < count) {
string s = random(Rand(base_len, base_len + 2), charset);
if (result_set.insert(s).second) {
result.push_back(s);
}
}
return result;
}
// 使用选定的组生成长字符串
vector
set
const auto& group = hash_groups[selected_hash];
while (result.size() < count) {
string s;
while (s.length() < base_len) {
s += RandChoice(group);
}
// 裁剪到接近 base_len 的长度
if (s.length() > base_len) {
s = s.substr(0, base_len);
}
if (result_set.insert(s).second) {
result.push_back(s);
}
}
return result;
}
};
/*
* 实用工具函数
*/
/**
* @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
}
/**
* @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);
cout << (verbose ? "随机高精度浮点数 (保留 " + to_string(x) + " 位小数): " : "") << 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") {
return StringGenerator::random(len, charset);
}
/**
* @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);
cout << (verbose ? "随机字符串: " : "") << s << "\n";
}
/**
* @brief 生成随机颜色（十六进制格式）
* @details 该函数生成一个随机的十六进制颜色代码，格式为 #RRGGBB。
* @return 返回一个随机颜色代码字符串
*/
string RandColorHex() {
char buf[8];
snprintf(buf, sizeof(buf), "#%02X%02X%02X", (int)Rand(0LL, 255LL), (int)Rand(0LL, 255LL), (int)Rand(0LL, 255LL));
return string(buf);
}
/**
* @brief 生成随机颜色并打印
* @details 该函数生成一个随机颜色代码，并根据verbose参数选择带文字描述或无文字描述的输出。
* @param verbose 是否输出带文字描述的版本，默认为true
*/
void generate_and_print_randcolor(bool verbose = true) {
string color = RandColorHex();
cout << (verbose ? "随机颜色 (十六进制): " : "") << 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" : "");
{
// 常规测试用例
Graph::generate_and_print_random_graph(5, 7, Graph::EDGE_LIST, false, 1, 20, false, verbose);
Graph::generate_and_print_random_graph(4, 6, Graph::TRIPLE_LINES, true, 1, 50, true, verbose);
// 边界测试用例
if (extreme) {
cout << (verbose ? "\n[边界测试] 稠密图生成：\n" : "");
Graph::generate_and_print_random_graph(1000, 499500, 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, 1LL, 10LL, verbose);
Array::generate_and_print_mountain(6, 0, 10, true, false, verbose);
// 边界测试用例
if (extreme) {
cout << (verbose ? "\n[边界测试] 大规模山峰数组：\n" : "");
Array::generate_and_print_mountain(6, 0, (int)1e9, true, true, verbose);
}
}
// ===== 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" : "");
// 6. 哈希碰撞字符串示例
cout << (verbose ? "\n6. 哈希碰撞字符串示例：\n" : "");
{
auto strings = StringGenerator::hack_hash_table(5, 10);
if (verbose) cout << "哈希碰撞字符串：\n";
for (const auto& s : strings) cout << s << "\n";
}
cout << (verbose ? "\n===== 示例演示结束 =====\n" : "");
}
void ZExample(bool extreme) {
// 运行所有示例，带文字描述
cout << "运行所有示例（带文字描述）：\n";
Example(true, extreme);
// 运行所有示例，无文字描述
cout << "\n运行所有示例（无文字描述）：\n";
Example(false, extreme);
}
}
/**
* @brief 主函数：运行示例并生成数据
*/
signed main() {
// rad::ZExample(false) ;
return 0 ;
}
随机数生成命名空间 rad
函数名
功能描述
参数说明
返回值
异常/限制
Rand
生成指定范围的随机整数
T l: 下限
T r: 上限
类型 T 的随机整数
static_assert 检查整数类型，确保 T 为整数类型
Rand
生成指定范围的随机浮点数
long double l: 下限
long double r: 上限
long double 随机浮点数
无
Rand128(l, r)
生成128位随机整数
__int128 l: 下限
__int128 r: 上限
__int128 随机整数
需用 write() 输出，l 和 r 必须在 __int128 可表示范围内
Shuffle(v)
随机打乱容器元素
vector
无（原地修改）
无
RandChoice(v)
从容器中随机选择元素
const vector
const T& 随机元素
runtime_error 如果容器为空
RandX(l, r, x)
生成保留 x 位小数的随机浮点数
long double l: 下限
long double r: 上限
int x: 小数位数
long double 随机浮点数
无，x 为负时可能截断为整数
RandString(len, charset)
生成指定长度的随机字符串
int len: 字符串长度
const string& charset: 字符集（默认小写字母）
string 随机字符串
invalid_argument 如果 len < 0 或 charset 为空
RandColorHex()
生成随机十六进制颜色
无
string 格式 #RRGGBB
无
树生成器类 rad::Tree
函数名
功能描述
参数说明
返回值
异常/限制
generate(n, type, min_w, max_w)
生成指定类型的树
n: 节点数
type: 树类型
min_w: 边权下限
max_w: 边权上限
vector
invalid_argument 如果 n ≤ 0 或 min_w > max_w
generate_and_print_tree(n, type, format, min_w, max_w, verbose)
生成并输出树
同 generate 增加：
format: 输出格式
verbose: 是否显示描述
无（输出到 stdout）
同 generate，format 必须为支持的枚举值
树类型枚举 Type
RANDOM: 随机树（默认，基于 Prufer 序列）
CHAIN: 链状结构（线性树）
STAR: 星型结构（一个中心节点连接所有其他节点）
BINARY: 近似二叉树（每个节点最多两个子节点）
输出格式枚举 OutputFormat
EDGE_LIST: 边列表（默认），格式为 u v w
ADJ_LIST: 邻接表，每行表示一个节点的邻接节点和边权
PARENT_ARRAY: 父节点数组，表示每个节点的父节点及到父节点的边权
图生成器类 rad::Graph
函数名
功能描述
参数说明
返回值
异常/限制
random(n, m, min_w, max_w, directed)
生成包含 n 个节点和 m 条边的完全随机图，边的端点和权值随机，不保证连通性
n: 节点数 (1 to n)
m: 边数
min_w/max_w: 边权范围
directed: 是否有向
vector
invalid_argument 如果 n ≤ 0，或 m 超出理论最大值（有向：n*(n-1)，无向：n*(n-1)/2）
connected(n, m, min_w, max_w, directed)
生成保证连通的随机图，先生成一棵树（n-1 条边），再添加剩余边
同 random
vector
invalid_argument 如果 n ≤ 0，m < n-1（无法连通），或 m 超过最大值
DAG(n, m, min_w, max_w)
生成有向无环图 (DAG)，通过随机拓扑序确保无环
n: 节点数
m: 边数
min_w/max_w: 边权范围
vector
invalid_argument 如果 n ≤ 0，m < 0，或 m > n*(n-1)/2
hack_spfa(n, k, min_w, max_w)
生成挑战 SPFA 算法的菊花链图，测试最坏时间复杂度
n: 节点总数
k: “花瓣”数（链的数量）
min_w/max_w: 边权范围
vector
invalid_argument 如果 n < 3，k < 2，或每条链节点数不足
generate_and_print_random_graph(n, m, output_format, sorted, min_w, max_w, directed, verbose)
生成并打印随机图
同 random，增加：
output_format: 输出格式
sorted: 是否按边权排序
verbose: 是否带描述
无（输出到 stdout）
同 random
generate_and_print_graph(n, m, min_w, max_w, directed, verbose)
生成并打印连通图
同 connected，增加：
verbose: 是否带描述
无（输出到 stdout）
同 connected
generate_and_print_dag(n, m, min_w, max_w, verbose)
生成并打印有向无环图 (DAG)
同 DAG，增加：
verbose: 是否带描述
无（输出到 stdout）
同 DAG
generate_and_print_hack_spfa(n, k, min_w, max_w, verbose)
生成并打印挑战 SPFA 的菊花链图
同 hack_spfa，增加：
verbose: 是否带描述
无（输出到 stdout）
同 hack_spfa
输出格式枚举 OutputFormat
EDGE_LIST: 每行 u v w（默认）
TRIPLE_LINES: 三行分别输出 u/v/w 数组
COLUMNAR: 列式存储（所有 u 一行，所有 v 一行等）
INTERLEAVED_LINE: 单行交错格式，如 u1 v1 w1 u2 v2 w2
ADJACENCY_LIST: 邻接表格式，显示每个节点的邻接节点和边权
数组生成器类 rad::Array
函数名
功能描述
参数说明
返回值
异常/限制
permutation(n, l, r)
生成 l 到 r 的随机排列
n: 元素个数
l: 下限
r: 上限
vector
invalid_argument 如果 n ≤ 0 或 r - l + 1 < n
unique(n, min_v, max_v)
生成唯一元素数组
n: 元素个数
min_v: 最小值
max_v: 最大值
vector
invalid_argument 如果 n ≤ 0 或值域 (max_v - min_v + 1) < n
mountain(n, min_val, max_val, is_peak_max, strict)
生成山峰或山谷数组（先增后减或先减后增，可选严格单调）
n: 元素个数
min_val/max_val: 值域
is_peak_max: 峰值最大（true 为先增后减）
strict: 是否严格单调
vector
invalid_argument 如果 n ≤ 0，n < 2，或值域不足
generate_and_print_permutation(n, l, r, verbose)
生成并打印随机排列
同 permutation，增加：
verbose: 是否带描述
无（输出到 stdout）
同 permutation
generate_and_print_unique(n, min_v, max_v, verbose)
生成并打印唯一元素数组
同 unique，增加：
verbose: 是否带描述
无（输出到 stdout）
同 unique
generate_and_print_mountain(n, min_val, max_val, is_peak_max, strict, verbose)
生成并打印山峰或山谷数组
同 mountain，增加：
verbose: 是否带描述
无（输出到 stdout）
同 mountain
字符串生成器类 rad::StringGenerator
函数名
功能描述
参数说明
返回值
异常/限制
random(len, charset)
生成指定长度的随机字符串
len: 字符串长度
charset: 字符集（默认大小写字母）
string 随机字符串
invalid_argument 如果 len < 0 或 charset 为空
random_list(count, min_len, max_len, charset)
生成随机字符串列表，字符串长度在 [min_len, max_len] 范围内
count: 字符串数量
min_len/max_len: 长度范围
charset: 字符集
vector
invalid_argument 如果 count < 0，min_len < 0，max_len < min_len
hack_hash_table(count, base_len, charset)
生成一组导致哈希碰撞的字符串，用于测试哈希表性能
count: 字符串数量
base_len: 目标长度
charset: 字符集
vector
runtime_error 如果无法在字符集中找到碰撞块
辅助函数
函数名
功能描述
参数说明
返回值
备注
read()
读取128位整数
无
__int128
支持负数输入
write(x)
输出128位整数
__int128 x: 要输出的数
无
支持负数输出
generate_and_print_randx(l, r, x, verbose)
生成并打印保留 x 位小数的随机浮点数
l: 下限
r: 上限
x: 小数位数
verbose: 是否带描述
无（输出到 stdout）
无
generate_and_print_randstring(len, charset, verbose)
生成并打印随机字符串
len: 字符串长度
charset: 字符集
verbose: 是否带描述
无（输出到 stdout）
同 RandString
generate_and_print_randcolor(verbose)
生成并打印随机十六进制颜色
verbose: 是否带描述
无（输出到 stdout）
无
造数据模板