浅谈随机化

• 2026-01-15 写出初稿。
  
• 2026-02-17 修改一些错误。
  

前言 - 我们为什么要学习随机化

随机化是一种极好的思想，当我们想不出正解的时候，我们就可以使用随机化。
并且，我们有的时候可以使用随机化过掉许多极难的题。
我们将会在这篇文章里，讲解随机化，由浅入深，一步步来。
从绿题到黑题，随机化所向披靡。
正文

Before we start - 了解我们要使用的工具

其实，随机化要使用的东西很少。
你看这下面的代码：

1. srand(k); // 其中 k 是任意一个正整数

复制代码

就是我们的初始化操作。
也可以使用

1. srand(time(0));

复制代码

这两个写法都可以：第一种方便调试，第二种随机性强。两种都可以使用。我们这里使用第一种。
当我们想要调用一个随机数的时候，直接调用 rand() 就可以了。
而当我们想要打乱一个数组 a，其下标从 \(1\) 到 \(n\)，我们可以使用这段代码：

1. random_shuffle(a + 1, a + n + 1);

复制代码

简单的随机化

P2210 [USACO13OPEN] Haywire B
先读一下题再回来看。
这道题正解是状压 DP，但是我们可以用随机化 AC。
用一个数组 \(a\) 来表示奶牛的位置，每次随机打乱 \(a\) 数组并计算当前的值，答案为最小值。
[code]#include using namespace std;const int N = 12 + 5;const int M = 5;const int INF = 0x3f3f3f;const double down = 0.996;int n, a[N], fri[N][M];signed main() {        cin >> n;        for (int i = 1; i  fri[1] >> fri[2] >> fri[3];        }                int temp = 2000000;        int ans = INF;        while (temp--) {                random_shuffle(a + 1, a + n + 1);                                int tot = 0;                for (int i = 1; i  b.y;                tx += b.x;                ty += b.y;        }        tx /= m;        ty /= m;        bst = max(bst, energy(tx, ty));        SA();        for (int i = 1; i  0.9) break;                if(!vis[{tx, ty}] && rand() % 4 != 0) {                        SA();                        vis[{tx, ty}] = true;                }                        }                        cout