随机化算法选讲

关于 rand()

它死了。

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

int main() {
    srand(time(NULL));
    for(int i=1; i<=10; ++i)
        printf("%d ",rand());
    return 0;
}

这是一份典型的使用 rand() 的代码，它有如下弊端：

1. 生成的随机数取值在 [0,RAND_MAX] 之中，C++ 文档 中仅要求 RAND_MAX 至少为 32767，在 Linux 下一般为 2147483647。
2. 由于使用了 time() 函数，在同一秒内其生成的随机数序列完全相同。

关于 mt19937

参考 Don't use rand(): a guide to random number generators in C++

mt19937 是 mersenne_twister_engine 的一个预定义特化，定义于 random 库中，其循环节长度达到 。

语法：

• mt19937(seed)：构造一个 mt19937 随机数生成器，seed 为种子，留空则为默认值。

• operator()：返回 unsigned int 类型的随机数。

• discard(n)：丢弃 n 个随机数。

• seed(value)：设置种子。

效率：在 -O2 编译开关下调用 次 operator() 用时为 秒。

mt19937_64 与其使用方法相同，返回 unsigned long long 类型。

一般用 random_device{}() 播种，但是更推荐 chrono::system_clock::now().time_since_epoch().count()，其返回自纪元来经过的时间长度，一般以纳秒为单位。

形如 rand()%(r-l+1)+l 的随机生成范围内的整数的方式其实并不均匀，可以用 uniform_int_distribution<int / long long>(l,r) 来生成均匀分布的随机数。

#include <cstdio>
#include <random>
#include <chrono>
using namespace std;

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
int main() {
    for(int i=1; i<=10; ++i)
        printf("%d ",uniform_int_distribution<int>(1,100)(rnd));
    return 0;
}

A possible Out

91 14 44 28 100 91 69 40 38 2

同时 uniform_real_distribution<double/long double>(l,r) 可用于生成一个在 区间均匀分布的实数。

参考 C++ 文档。

关于 shuffle()

shuffle 与其前身 random_shuffle 同样定义于 algorithm 库中，用于随机打乱一个容器中的元素。

后者在 C++17 标准中被弃用。

shuffle(first,last,rng) 将 [first,last) 范围内的元素随机打乱，rng 为一个随机数生成器。

线性时间复杂度。

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

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
int n=10,a[15];
int main() {
    for(int i=1; i<=n; ++i) a[i]=i;
    shuffle(a+1,a+n+1,rnd);
    for(int i=1; i<=n; ++i) printf("%d ",a[i]);
    return 0;
}

关于 chrono 库

传统方式是使用 ctime 库中的 clock() 函数，但是其效率及其低下，精度也不优于 chrono 库。

经测试，调用 次 chrono::steady_clock::now() 与 chrono::system_clock::now() 耗时均在 秒以内，而 clock() 在 -O2 编译开关下耗时超过 秒。

Usage: chrono::<timer>::now() 返回一个表示当前时间的 chrono::time_point 对象，可以用 auto 自动推断类型。

将两个 time_point 对象相减，作为 chrono::duration<Rep,Period> 的构造参数后调用 count() 方法，即可得到两个时间点的间的时长，类型为 Rep，Period 默认为秒。

#include <cstdio>
#include <chrono>

using namespace std;
int main() {
    const auto st = chrono::steady_clock::now();
    for(int i=1; i<=1e9; ++i);
    const auto et = chrono::steady_clock::now();
    printf("%.6lf",chrono::duration<double>(et-st).count());
    return 0;
}

参考 C++ 文档。

随机元素命中目标集合 (hit)

CF364D Ghd

定义一个集合的 为所有大小至少为一半的子集的 的最大值。
求给定集合 的 ，。

• 假设我们已经知道某个元素 在最优方案的集合中

• 提出 的因数，对每个因数求 中有多少个是它的倍数，如果 就更新答案。

• 随机取一个元素，钦定其在最优集合中，正确率 。

• 时间复杂度 。

CF1305F Kuroni and the Punishment

给定 个数。每次可以选择将一个数 或 。求至少多少次操作使得整个序列都是正数且全部元素的 。
。

• 显然

• 考虑这样一个集合 ：其中的元素在最优方案中至多被操作一次

• 随机选一个元素，将其 并分解作为备选答案，每次选中的概率 。

• 时间复杂度

随机增量法

P1742 最小圆覆盖

给出 个点，让你画一个最小的包含所有点的圆。

P1429 平面最近点对

给定平面上 个点，求两点之间最短距离。

P3222 [HNOI2012] 射箭

给定 条线段，求一条抛物线最多能与前几个线段有交点。

CF442E Gena and Second Distance

给定一个宽为 ，高为 的矩形以及矩形内的 个点。
一个点到这 个点的距离的非严格次小值被称为这个点的价值。
求矩形内的点的最大价值。

传统题

• CF1746F Kazaee

• CF1835C Twin Clusters

• P10010 [集训队互测 2023] Grievous Lady