浅谈出题者如何造数据

__Aha__ · 2026-02-10 11:58:47 · 算法·理论

概括一下：这篇文章列举了每种数据的构造方式，没有的可以提出哦！

有笔误也请提出。

代码均由 Gemini 编写，一些逻辑也询问了 Ta。

请注意文中的板块都没有讲的很详细，如果想深度学习内容，可以移步其他文章。

计划：后续添加图和树。

随机种子

所有的随机数生成都离不开随机种子。

通常我们会使用 time(0)（秒级）获取当前时间来充当随机种子。

但是它的缺点很明显，如果在一秒内多次运行程序，生成的随机序列将完全相同。

更好用的是 std::random_device。它通过硬件熵源生成非确定性的随机数，可以看作是“真随机”。需要注意的是：

在许多 Linux 系统上，它确实利用 /dev/urandom。但在某些 Windows 编译器（如旧版 MinGW）下，它的实现可能是确定性的（每次运行结果一样）。
其调用比普通的伪随机数生成器慢得多，所以也只用它来当种子。

熵源：计算机利用热噪声、中断时序等不可预测的物理现象产生的随机性来源。

当然，不嫌麻烦可以用 std::chrono::steady_clock::now().time_since_epoch().count()。原理是获取系统启动后的高精度时间戳（通常是纳秒级），相比 time(0)，它更难被预测且精度极高。

序列

单个数

随机整数的生成

在给定的闭区间 [a, b] 内生成每一个数概率均等的整数。

传统的方法是使用 rand() % (b - a + 1) + a。
- 但需要注意的是 RAND_MAX 在某些系统（如 Windows）中仅为 32767，无法生成大数据。
- 而且如果 RAND_MAX + 1 不能被区间长度 L = b - a + 1 整除，那么区间前半部分的数字出现的概率会略高于后半部分。这个问题被称为模运算偏差。
现目前一般使用 <random> 头文件，然后通过 std::mt19937 或 std::mt19937_64（能生成 64 位整数）引擎配合 std::uniform_int_distribution 实现。
- 其优点很多，可以说严格符合数学上的均匀分布，同时执行周期极长（2^{19937}-1）。

具体实现请看伪代码：

// 1. 初始化真随机数种子源
std::random_device rd; 
// 2. 以种子初始化 mt19937 引擎
std::mt19937 gen(rd());
// 3. 定义 [a, b] 闭区间的均匀分布
int a = 1, b = 1000000;
----
std::uniform_int_distribution<int> dis(a, b);
// 4. 生成随机数
int random_val = dis(gen);
std::cout << "生成的随机数是: " << random_val << std::endl;
----1
或：
----
int random_val = dis(gen) % (b - a + 1) + a;
std::cout << "生成的随机数是: " << random_val << std::endl;
----2

Ps：<random> 头文件包含在万能头中。

随机浮点数的生成

在区间 [a, b) 内生成随机小数。

使用 std::uniform_real_distribution<double> dis(a, b)。它能自动处理浮点数的精度映射，确保在给定范围内均匀分布。它仍然需要使用 <random> 头文件。

伪代码：


// 定义 [a, b) 左闭右开区间的实数分布
double fa = 0.0, fb = 1.0;
std::uniform_real_distribution<double> fdis(fa, fb);

// 生成随机浮点数
double random_float = fdis(gen);

序列

随机排列

生成一个 1 \sim n 的随机排列，每个数恰好出现一次。

先使用 std::iota 填充序列（手动填充也行），再使用 std::shuffle 打乱。

注意：应避免使用已被废弃的 std::random_shuffle，而是配合mt19937 使用 std::shuffle。

伪代码：

std::vector<int> p(n);
std::iota(p.begin(), p.end(), 1); // 填充 1, 2, ..., n
std::shuffle(p.begin(), p.end(), gen);// 这里的 gen 是随机数。

std::iota：一个工具函数，用于用连续递增的值填充指定范围的元素。定义在 <numeric>（包含于万能头）头文件中。

当然，如果你不希望依赖 std::shuffle（~~因为笔者不会拼~~），可以手动实现 Fisher-Yates Shuffle（一种将有限集合生成随机排列的算法，由于其在线性时间内完成且不产生统计偏向，被广泛应用。）。

该算法的核心思想是从后往前遍历数组，将当前元素与前面任意一个随机位置的元素进行交换。这种方法能保证每一个排列出现的概率都是 \frac{1}{n!}。

单调数列

分为严格单调或非严格单调。

先生成一组随机数，然后使用 std::sort 进行排序。
也可以递增构造：a_i = a_{i-1} + \text{rand\_delta}，其中 \text{rand\_delta} \ge 0。

单峰数列

序列先严格递增再严格递减（形如山峰）。

构造步骤：

随机确定峰顶位置 k \in [1, n]。
生成 n 个随机数并排序。
将最大的数放在位置 k。
将剩余的数随机或交替填充到 k 的左侧和右侧，并分别排序。

Ps：多峰数列可由多个单峰数列组成。

区间 l，r

这里还是值得讲一下的，因为每种写法都有优缺点。

直接生成两个独立随机数 u, v \in [1, n]，取 l = \min(u, v), r = \max(u, v)。
- 生成的区间长度期望约为 n/3。
- 它在区间个体的选择上是不均匀的。例如，生成特定点区间 [i, i] 的概率是 1/n^2（需 u=v=i），而生成特定的 l < r 区间的概率是 2/n^2（u=l, v=r 或 u=r, v=l 均可）。这意味着它更倾向于生成长度大于 1 的区间。
先随机长度 len \in [0, n-1]，再随机起点 l \in [1, n-len]。
- 优点是它保证了长度 len 在 [0, n-1] 上是绝对均匀分布的。
- 缺点是会导致“长区间”个体被选中的概率远高于“短区间”。例如，全长度区间 [1, n] 只有一个，被选中的概率是 1/n；而长度为 1 的区间有 n 个，每个被选中的概率仅为 1/(n \times n)。
- 话说这应该不算缺点吧...

第二种生成策略就是很常用的了。

如果实在要追求完美（指所有可能的子区间 [l, r] 被选中的概率完全相等），解决方案也很简单：

在 [1, n] 范围内，合法的子区间总数为：Total = \frac{n(n+1)}{2}

先在 [1, \frac{n(n+1)}{2}] 范围内随机生成一个整数 k，然后通过数学映射将 k 唯一对应到一个区间 [l, r]。

针对特定算法的 Hack 数据的构造

需要注意的是，对于这个板块的所有算法，在固定数据的情况下，都无法完美卡掉做题者的代码。

所以 Hack 仅供参考。

针对快速排序

::::info[原理] 快速排序作为一种基于分治法的经典排序算法，其效率高度依赖于基准值的选择。

在理想情况下，基准值能将序列平分为两个等长的子序列，从而达到 O(n \log n) 的时间复杂度。

但显然这可能被卡。

注意到当快速排序采用固定位置（如第一个或最后一个元素）作为基准值时，其逻辑上的递归树将从平衡的二叉树退化为一条长链。

比如在升序或降序序列中，如果选取第一个元素作为基准值：

基准值在分区后依然留在最左侧，产生一个长度为 0 和一个长度为 n-1 的子序列。
为了排好一个元素，算法需要扫描剩余的所有元素。
总时间复杂度为 O(n^2)。

所以，现在的实现一般采用三数取中（Median-of-three）优化。也就是取序列首、中、尾三个数的中位数作为基准。但是这还是能卡。

M. D. McIlroy 提出的 Anti-Quicksort 是一种动态对手算法。它通过模拟排序过程，在算法进行比较时动态决定元素的大小关系，迫使“三数取中”每次都选到一个极差的基准值（如剩余元素中较小的一个）。 ::::

因为上述原因，在现代 C++ 的 std::sort 实现中，采用了内省排序策略了来防止被卡。

而且对于手写快排的随机选取基准值也是无法卡掉的。

~~所以还不膜拜期望真菌 %%%~~

针对哈希表

针对 std::unordered_map

::::info[原理]

因为在很多 C++ 实现（如 GCC）中，std::unordered_map 对整数的默认哈希函数是 Identity Map（恒等映射），即 hash(x) = x。

其内部使用拉链法（当多个键映射到同一个桶时，用链表将这些键连接起来的冲突解决方法。）处理冲突。

由于 `unordered_map 的桶大小遵循特定的质数序列（如 126271, 1073741824 等），攻击者可以构造大量相差该质数倍数的数值。 ::::

Hack：x_i = i \times P，其中 P 是哈希表内部使用的模数（通常是 107897 和 126271）。当然，这两个质数卡不掉，你可以造个质数表。

这会使所有 x_i 都会被映射到同一个桶中，导致哈希表退化为一条极其细长的单链表。

针对 pb_ds 中的 gp_hash_table

::::info[原理] gp_hash_table（探测法哈希表）通常比 unordered_map 快，因为它使用闭散列（开放寻址法）。

为了加速运算，它的桶大小通常是 2 的幂次，内部通过 (x ^ (x >> 16)) & (mask) 来定位。

对于这种哈希只需要构造在高位不同、但在低位经过位运算后相同的数值：

开放寻址法：当发生冲突时，通过某种探测序列在哈希表中寻找下一个空闲位置的解决方法。 ::::

Hack：构造序列 x_i = i \times 2^k（如 2^{16} 或 126271）。如果哈希函数没有进行充分的扰动，这些数在模 2^k 意义下全部冲突。

针对手动实现哈希

自然溢出

使用 unsigned long long 自动溢出而不取模（等价于对 2^{64} 取模）。

使用 Thue-Morse 序列。该序列可以构造出两段哈希值在 2^{64} 意义下完全相同的字符串。

具体地，

定义 S_0 = "a", T_0 = "b"。

S_{n} = S_{n-1} + T_{n-1}

T_{n} = T_{n-1} + S_{n-1}

随着 n 的增加，这两段字符串 S_n 和 T_n 的哈希值之差可以被 2^n 整除。当 n 达到 64 时，无论你的哈希底数是多少，只要它是奇数，S_{64} 和 T_{64} 的哈希值在 ULL 意义下就一定会产生碰撞。

Thue-Morse 序列：一个二进制序列，通过反复对当前序列取反并拼接在末尾生成，常用于数学和计算机科学中构造避开特定模式的序列。

单模数

如果使用固定的质数（如 10^9+7 或 10^9+9）作为模数。

利用生日悖论，大约只需要生成 \sqrt{M} 个随机数据，就有极高概率找到一对冲突点。

生日悖论：在不少于 23 人的群体中出现相同生日的概率超过 50%，60 人时概率可达 99%。

反 Hack 也很简单，添加上文中所说的扰动量，或者双模哈希，比如：

struct my_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }

  // 针对 std::pair<int, int> 作为主键类型的哈希函数
  size_t operator()(pair<uint64_t, uint64_t> x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x.first + FIXED_RANDOM) ^
           (splitmix64(x.second + FIXED_RANDOM) >> 1);
  }
};
// 使用方式：std::unordered_map<long long, int, my_hash> safe_map;

针对莫队

莫队算法的复杂度取决于区间端点 [L, R] 的移动。

针对普通莫队，若不使用奇偶排序优化，构造 L 在块内单调，但 R 在相邻块间剧烈跳动的数据。

更通用的 Hack：构造一系列询问，使得 L 在每个块的左端点和右端点交替，同时 R 在每一行询问中从 1 跨越到 N，最大化曼哈顿距离。

曼哈顿距离：在二维平面上，两点之间横纵坐标差的绝对值之和，莫队算法的复杂度本质上是询问点在二维平面上的曼哈顿距离之和。

针对 ODT

虽然其本身被划为暴力数据结构，但实在是没啥好说的。

出题者只需自己做下势能分析，每次取极限，也挺好卡的。

针对线段树

其本身的复杂度是完全达标的，所以这里教一下怎么恶心做题者。

::::info[线段树要开 4 倍空间的原因]{open}

很多萌新只知道要这么做，但不知道为什么。

线段树虽然不是完全二叉树，但它是一棵平衡二叉树。当我们使用堆式存储（即 p << 1 和 p << 1 | 1）时，数组下标取决于树的深度。

最坏情况下，当 n = 2^k + 1 时，线段树会为了容纳最后那一个点，被迫多长出一层。此时最大节点下标会达到 2^{\lceil \log_2 n \rceil + 1} - 1 = 2^{k+2} - 1 = 4 \times 2 ^ k - 1 = 4n - 5。

感性理解就行。 ::::

卡极限空间只要让 n=2^k + 1 就行。

当然如果作为做题者的你遇到空间限制极严（比如 64MB）的题目，可以祭出 zkw 线段树。它空间可以压到 2n。或者用动态开点，仅在访问时创建节点，将空间复杂度从 O(n) 转化为 O(m \log n)（~~看似变劣了~~）。

之后是常数。线段树最主要的操作是 pushdown 与 pushup。

我们构造大量的叶子节点查询，或者在区间两端频繁跳动的修改。强制线段树每次都走满 \log n 的深度。

字符串

窝趣，这部分忘讲了，后面再说。

图

这次修改给图开个头吧。-- 2026/2/14。

树

树只是图的一个分支，其本身在数据这块也没啥好讲的。

只能说以下内容确实都算树吧。

长链：每个点只连向 i+1，专门卡深度相关的算法。
菊花图：一个中心点连向所有其他点，卡那些对节点度数敏感的逻辑。
扫帚图：前半段是链，后半段是菊花。
完全二叉树：保持高度在 \log n，测试理想情况下的性能。笔者没了解到啥卡数据的作用。

同时真随机树的生成一般利用 Prufer 序列生成。先随机一个长度为 n-2 的序列，再通过线性时间转换成树，这能保证在所有可能的树形态中等概率抽取。

Prufer 序列：这里不做解释，请继续查询 Prüfer 序列。