采样与随机化

前言

竞赛中”随机”出现在三个场景：

1. 调试：写一个随机数据生成器 + 暴力解，自动找出 WA 的测试用例。
2. 算法设计：某些问题确定性算法太慢，但随机化算法期望很快（如随机选 pivot 的快排、随机化判定素数的 Miller-Rabin）。
3. 概率分析：算法的正确性以概率保证（如哈希冲突概率 $O(1/M)$）。

这篇重点讲前两个——特别是随机测试调试，这是竞赛选手最重要的工程技能之一。

问题的本质

随机测试为什么有效？

假设你的程序有一个 bug，在大小为 $N$ 的输入上的触发概率是 $p$。生成 $K$ 组随机测试，触发 bug 的概率 $= 1-(1-p)^K$。即使 $p = 0.01$（1%），1000 组测试就能以 $99.995\%$ 的概率发现 bug。

追问：为什么很多选手不写随机测试？因为觉得”浪费时间”。实际上写一个随机测试生成器 + 暴力通常只需 5-10 分钟，但找到 WA 用例后修复 bug 可以节省 30 分钟甚至更多。

随机化算法设计

核心思想：让最坏情况变成期望情况。确定性快排最坏 $O(N^2)$，但随机选 pivot 后期望 $O(N \log N)$。类似地，字符串哈希的冲突检测用随机基底 $B$，使对手无法构造冲突数据。

理论 + 代码

随机测试模板

AtCoder Algorithm Lectures 推荐的三种方法，核心流程一致：

生成随机输入 → 分别用提交解法和暴力解法求解 → 比较输出 → 不一致则输出该用例

方法 1：三个独立文件（推荐）

generate.py  — 随机生成测试用例
naive.cpp    — 暴力解法（正确但慢）
main.cpp     — 提交用解法（快但可能有 bug）

Shell 脚本自动循环：

while true; do
    python3 generate.py > in.txt
    ./main < in.txt > out1.txt
    ./naive < in.txt > out2.txt
    if ! diff out1.txt out2.txt > /dev/null; then
        echo "Found mismatch!"
        cat in.txt
        echo "---main---"
        cat out1.txt
        echo "---naive---"
        cat out2.txt
        break
    fi
done

随机数据生成器示例（Python）：

import random

def generate():
    N = random.randint(1, 20)                    # ① 小规模确保暴力可跑
    A = [random.randint(1, 100) for _ in range(N)]
    print(N)
    print(*A)

generate()

暴力解示例：

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int A[109];
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);

    // ② 暴力：枚举所有可能的解
    int ans = 0;
    for (int i = 0; i < N; i++)
        for (int j = i+1; j < N; j++)
            ans = max(ans, abs(A[i] - A[j]));

    printf("%d\n", ans);
}

逐行解析：

• ① 随机生成小规模数据（暴力解法的复杂度限制）。关键是覆盖各种边界：$N=1$、全相同、递减、有负数等。
• ② 暴力解法的核心是逻辑简单，尽可能直接翻译题意。

方法 2：单文件 + 条件编译

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

// #define RANDOM_TEST                        // ① 取消注释启用随机测试

int solve(int N, int A[]) {
    // 提交用解法
    int ans = 0;
    // ... 你的算法 ...
    return ans;
}

int naive(int N, int A[]) {
    // 暴力解法
    int ans = 0;
    for (int i = 0; i < N; i++)
        for (int j = i+1; j < N; j++)
            ans = max(ans, abs(A[i] - A[j]));
    return ans;
}

int main() {
#ifdef RANDOM_TEST
    srand(time(0));
    int T = 100000;                            // ② 测试轮数
    while (T--) {
        int N = rand() % 20 + 1;               // ③ 随机 N
        int A[109];
        for (int i = 0; i < N; i++)
            A[i] = rand() % 200 - 100;         // ④ 随机 A[i]（含负数）
        int r1 = solve(N, A);
        int r2 = naive(N, A);
        if (r1 != r2) {
            printf("Mismatch! N=%d\n", N);
            for (int i = 0; i < N; i++) printf("%d ", A[i]);
            printf("\nsolve=%d naive=%d\n", r1, r2);
            return 0;
        }
    }
    printf("All passed!\n");
#else
    // 正式提交
    int N;
    scanf("%d", &N);
    int A[109];
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);
    printf("%d\n", solve(N, A));
#endif
}

逐行解析：

• ① 用 #define 切换随机测试和正式提交模式。
• ② 通常测试 10000-100000 轮。
• ③④ 生成小规模但多样的测试数据。

随机化算法示例：判定数组中是否有超过半数的元素

Boyer-Moore 投票法的随机化版本：随机选一个元素，验证它是否超过半数。$O(N)$ 时间，成功概率 $\ge 1/2$。做 $k$ 次则失败概率 $\le 2^{-k}$。

#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

int A[100009];

bool check(int x, int N) {
    int cnt = 0;
    for (int i = 0; i < N; i++)
        if (A[i] == x) cnt++;
    return cnt > N / 2;                             // ① 验证 x 是否超过半数
}

int main() {
    srand(time(0));
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);

    int trials = 50;                                 // ② 做 50 次
    int ans = -1;
    for (int t = 0; t < trials; t++) {
        int idx = rand() % N;                        // ③ 随机选一个
        if (check(A[idx], N)) {
            ans = A[idx];
            break;
        }
    }
    printf("%d\n", ans);
}

逐行解析：

• ① 验证阶段：$O(N)$ 检查 $x$ 出现次数。
• ② 每次成功概率 $\ge 1/2$，50 次后失败概率 $\le 2^{-50}$。
• ③ 随机选取一个候选。

例题

例题 1：随机测试实战——调试排序算法

场景：你写了一个排序算法但不确定是否正确。用随机测试验证。

数据范围：小规模 $N \le 20$ 确保暴力可跑

分析：生成随机数组，用自己的排序和 std::sort 分别排序，比较结果。

代码：

# generate.py
import random

def generate():
    N = random.randint(1, 20)
    A = [random.randint(-100, 100) for _ in range(N)]
    print(N)
    print(*A)

generate()

// naive.cpp（直接用 std::sort 作为"正确答案"）
#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int A[109];
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);
    sort(A, A + N);
    for (int i = 0; i < N; i++) {
        if (i) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
}

验证：运行 10000 轮，如果有不一致立即报告。Shell 脚本见上方模板。

---

例题 2：随机化求众数

场景：$N$ 个数中，如果某个数出现超过 $N/2$ 次，找出它。保证存在。

数据范围：$1 \le N \le 10^6$

分析：随机选一个数，$O(N)$ 验证。期望 $O(N)$ 总时间。

代码：

#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

int A[1000009];

int main() {
    srand(time(0));
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);

    while (true) {
        int x = A[rand() % N];                       // ① 随机选
        int cnt = 0;
        for (int i = 0; i < N; i++)
            if (A[i] == x) cnt++;
        if (cnt > N / 2) {                            // ② 验证成功
            printf("%d\n", x);
            return 0;
        }
    }
}

逐行解析：

• ① 随机选一个候选。因为众数占比 $> 50\%$，每次选中众数的概率 $> 1/2$。
• ② $O(N)$ 验证。

---

例题 3：随机化哈希——避免被卡

场景：字符串哈希中，固定基底 $B$ 和模数 $M$ 可能被对手构造冲突。使用随机基数避免。

分析：在程序开始时随机选择 $B \in [256, 10^9]$。对手无法预知 $B$，所以无法构造冲突。

代码：

#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

int main() {
    srand(time(0));
    long long B = 256 + rand() % 999999744LL;         // ① 随机基数
    const long long MOD = 1000000007;

    char S[100009];
    scanf("%s", S);
    int N = 0;
    while (S[N]) N++;

    long long h = 0;
    for (int i = 0; i < N; i++)
        h = (h * B + S[i]) % MOD;                     // ② 用随机基数算哈希

    printf("%lld\n", h);
}

逐行解析：

• ① 每次 run 选用不同的 $B$，对手无法预先构造冲突。
• ② 标准哈希计算。

---

例题 4：随机化快速选择——第 K 大

场景：数组中找第 $K$ 大的元素。期望 $O(N)$。

数据范围：$1 \le N \le 10^7$

分析：随机选 pivot 做划分。期望深度 $O(\log N)$，每层 $O(N)$，总 $O(N)$。

代码：

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;

int A[10000009];

// ① 随机化快速选择
int quick_select(int lo, int hi, int k) {
    if (hi - lo == 1) return A[lo];
    int pivot = A[lo + rand() % (hi - lo)];           // ② 随机选 pivot
    int i = lo, j = hi - 1;
    while (i <= j) {
        while (A[i] < pivot) i++;
        while (A[j] > pivot) j--;
        if (i <= j) { swap(A[i], A[j]); i++; j--; }
    }
    if (k < i - lo) return quick_select(lo, i, k);    // ③ 在左半
    else return quick_select(i, hi, k - (i - lo));     // ④ 在右半
}

int main() {
    srand(time(0));
    int N, K;
    scanf("%d%d", &N, &K);
    for (int i = 0; i < N; i++) scanf("%d", &A[i]);
    printf("%d\n", quick_select(0, N, K - 1));
}

逐行解析：

• ② 随机选 pivot 而非固定选第一个元素，避免最坏 $O(N^2)$。
• ③④ 根据 pivot 位置决定递归方向，期望每次至少去掉一半元素。

参考文献

理论讲义 — AtCoder Algorithm Lectures

• ランダムテストによるデバッグ（難易度 1）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化