随机化
Contents
构造题的应用
在 $n$ 较小时，确定一个随机数的seed mt19937 rng(SOME_SEED);，如果在本地成功跑出来结果，就直接把这个seed交上去，这样就可以deterministic保证答案是对的。
color coding
一个很有趣的概念，意思是对于一个很难解决的问题，可以考虑先将问题中的一些变量染色，对于不同颜色分别解决。或者是染色后，根据某些与颜色有关的性质进行操作。
例题见例2和例3。
破坏input的性质
如果input是一些较小的正整数，并且它们之间可能有一定规律，将input map到一个较大的范围可以破坏掉input的一些限制。从而获得一些有用的特性。
例题
例1 CF364D. Ghd
题意
给定一个长度为 $n$ 的数组 $a_1,a_2,…,a_n$，定义其ghd为：
最大的一个数 $g$，使得 $a_i$ 中有至少一半的数 divisible by $g$。
求一个数组的 ghd。
其中，$n \leq 10^6, a_i \in [1,10^{12}]$。
题解
好题。考虑随机化：
显然，我们随机选一个 $a_i$，并且求出它的所有因数，那么有 50% 的概率使得ghd在 $a_i$ 的因数中。
但众所周知一个数的因数数量是 $O(n^{\frac{1}{3}})$ 级别的（证明见这里），$a_i \leq 10^{12}$，很明显这有点太大了。
我们需要快速解决以下问题：
给定一个数 $x$，求 $x$ 的每一个因数能够被多少个 $a_i$ 整除。
有一个 $O(d^2)$ 的基于 dp 的方法（$d$ 是 $x$ 的因数数量）。
先将 $x$ 的所有因数求出来，然后sort一下，我们维护一个 cnt[] 数组，其中 cnt[i] 代表 $x$ 的第 $i$ 个因数能够被多少个 $a_i$ 整除。
然后将 $x$ 与每一个 $a_i$ 取 gcd，得到 $g_i$，那么 $g_i$ 就是满足 既是 $x$ 的因数，又是 $a_i$ 的因数 的最大因数。
那么我们先找到 $g_i$ 对应 $x$ 的第几个因数，先让对应的 cnt[j]++。
然后从小到大 dp，对于小的因数，如果某个更大的因数能够整除它，那么就将大的 cnt 加到小的上去。
这样 cnt[] 有了就可以更新答案了。
这样随机个10次左右即可（我代码中随机3秒停止）。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
ll gcd(ll a, ll b) {
if (!b) return a;
return gcd(b, a%b);
}
ll ans = 0;
int n;
ll a[maxn];
vector<ll> factorize(ll x) {
vector<ll> vec;
for (int i = 1; i <= sqrt(x); i++) {
if (x % i == 0) {
vec.push_back(i);
if (x / i != i)
vec.push_back(x/i);
}
}
sort(vec.begin(), vec.end());
return vec;
}
void solve() {
ll x = a[randint(1,n)];
vector<ll> fac = factorize(x);
vector<int> cnt(fac.size(), 0);
for (int i = 1; i <= n; i++) {
ll g = gcd(x, a[i]);
int p = lower_bound(fac.begin(), fac.end(), g) - fac.begin();
cnt[p]++;
}
// 从小到大 dp
for (int i = 0; i < cnt.size(); i++) {
for (int j = i+1; j < cnt.size(); j++) {
if (fac[j] % fac[i] == 0) cnt[i] += cnt[j];
}
}
for (int i = cnt.size()-1; i >= 0; i--) {
if (cnt[i] * 2 >= n) {
ans = max(ans, fac[i]);
return;
}
}
}
int main() {
fastio;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
while ((double)clock() / CLOCKS_PER_SEC <= 3) {
solve();
}
cout << ans << endl;
}
例2 Vacuum Tubes
题意
给定 $n$ 个正整数 $a_1,a_2,…,a_n$ 和两个正整数 $L_1, L_2$。
从中选出四个数，$a_i, a_j, a_l, a_k$ 使得：
- $a_i+a_j \leq L_1$
- $a_l+a_k \leq L_2$
- $i,j,l,k$ 互不相同
并且求出 $a_i+ a_j+ a_l+ a_k$ 可能的最大值，如果无解输出 $-1$。
其中，$n \leq 2000, a_i, L_1,L_2 \in [1,10000]$。
题解
显然 $a_i,a_j$ 和 $a_l,a_k$ 是两个独立的问题。
对于其中一个问题，显然可以用二分来做。但现在有两个问题。
所以不妨将原数组随机分成两等份，然后分别对两份数组进行操作。
假设最优答案为 $a_i’,a_j’,a_l’,a_k'$，那么 $a_i’, a_j'$ 在第一份数组，且 $a_l’,a_k'$ 在第二份的数组的概率为 $\frac{1}{8}$。
重复很多次即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+55;
const int maxm = 4e4+55;
int l1, l2, n, a[maxn];
int solve(int l, int r, int L) {
sort(a+l, a+r+1);
int res = -1;
for (int i = l; i <= r; i++) {
int p = upper_bound(a+l, a+r+1, L - a[i]) - a;
p = max(p, l);
p = min(p, i-1);
while (p-1 >= l && a[p] + a[i] > L) p--;
if (p < i && p >= l && a[i] + a[p] <= L) res = max(res, a[i] + a[p]);
}
return res;
}
int main() {
cin >> l1 >> l2 >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int ans = 0;
while ((double)clock() / CLOCKS_PER_SEC * 1000 <= 2000) {
shuffle(a+1, a+n+1, rng);
int r1 = solve(1, n/2, l1);
int r2 = solve(n/2+1, n, l2);
if (r1 > 0 && r2 > 0)
ans = max(ans, r1 + r2);
}
if (!ans) cout << "Impossible\n";
else cout << ans << "\n";
}
例3 Dragon Ball II
题意
给定一个 $n$ 个点，$m$ 条边的无向图。边有边权。
现在有 $k$ 个龙珠，每个龙珠会拥有一个颜色 $d_i$，并且这个龙珠会存在于节点 $c_i$ 中。
我们从节点 $1$ 出发，经过一个节点时会获得这个节点里的所有龙珠。
求最短路径的长度，使得我们收集了至少 $7$ 个不同颜色的龙珠。如果无解输出 $-1$。
其中，$n,k \leq 1000, m \leq 10000, w_i \in [0,10000], c_i, d_i \in [1,n]$。
题解
我们只需要收集 $7$ 个不同的颜色，但原图中的颜色有 $n$ 种，怎么办？
考虑 color coding 的思想：
我们不妨假设只有 $7$ 种颜色，然后对于原图中的每一种颜色，将它们随机 map 到七种颜色中的一种，然后就只有 $7$ 种颜色了。
只有 $7$ 种颜色后，明显可以直接维护大小为 $2^7$ 的mask，然后跑dijkstra。
什么情况下答案会出错呢？
假设答案需要颜色 $d_{i_1}, d_{i_2} … d_{i_7}$，那么如果有任意两个颜色被map到同一种，就说明答案错误了。
因此，答案正确的情况有 $A_7^7 = 7!$ 种。
答案正确的概率为 $\frac{7!}{7^7} = 0.006$。
这个题目时限为 $16$ 秒，大概可以跑 $10^9$。这个dijkstra相当于在 $M = 10^4 * 2^7 = 1.28 * 10^6$ 的情况下跑 $O(M\log M)$（实际上吃不了这么满）。
实际上大概可以跑 $800-1000$ 次。失败概率约为 $5$ % 左右，运气好还是可以跑过去的。
• 另外如果我们提升随机颜色的数量，运行次数只会大幅度缩小，而成功概率不会提升很多，所以 $7$ 种颜色就是最好的。
代码
#include <bits/stdc++.h>
using namespace std;
const int M = 7;
struct Edge {
int v, w;
};
vector<Edge> adj[maxn];
int n, m, k;
vector<int> ball[maxn], cur[maxn];
ll ans = 1e18;
ll dis[maxn][(1<<M) + 5];
bool vis[maxn][(1<<M) + 5];
struct Node {
int u;
ll d;
int mask = 0;
bool operator<(const Node& other) const {
return d > other.d;
}
};
void solve() {
map<int, int> mp;
for (int i = 1; i <= n; i++) {
cur[i].clear();
for (int x : ball[i]) {
if (!mp.count(x)) {
mp[x] = randint(0, M-1);
}
cur[i].push_back(mp[x]);
}
}
memset(vis, 0, sizeof(vis));
memset(dis, 63, sizeof(dis));
int smask = 0;
for (int x : cur[1]) smask |= (1<<x);
dis[1][smask] = 0;
priority_queue<Node> pq;
pq.push({1, 0, smask});
while (pq.size()) {
auto [u, d, mask] = pq.top();
pq.pop();
if (vis[u][mask]) continue;
vis[u][mask] = 1;
for (auto [v, w] : adj[u]) {
int nmask = mask;
for (int x : cur[v]) {
nmask |= (1<<x);
}
if (dis[v][nmask] > dis[u][mask] + w) {
dis[v][nmask] = dis[u][mask] + w;
pq.push({v, dis[v][nmask], nmask});
}
}
}
for (int i = 1; i <= n; i++) {
for (int mask = (1<<7) - 1; mask < (1<<M); mask++) {
if (__builtin_popcount(mask) >= 7) {
ans = min(ans, dis[i][mask]);
}
}
}
}
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 1; i <= k; i++) {
int c, d; cin >> c >> d;
ball[c].push_back(d);
}
while ((double)clock() / CLOCKS_PER_SEC < 14.5) {
solve();
}
cout << (ans > 1e16 ? -1 : ans) << endl;
}
例4 Spooky Scary Skeletons
题意
给定一个长度为 $n$ 的正整数数组 $a_1,a_2,…,a_n$。
有 $q$ 个询问，每次询问 $[L,R]$ 之间是否存在恰好一个出现次数为奇数的数字，如果存在，输出它，否则输出 $0$。
其中，$n \leq 3 \times 10^6, q \leq 10^6, a_i \in [1,10^5]$。
题解
我们知道一个区间 $[L,R]$ 内，如果恰好有一个出现次数为奇数的数字，那么这个区间的XOR和就是这个数字。
但，有一些例外，比如有多个出现次数为奇数的数字时，XOR和不能说明任何问题。
例如对于 $[1,2,3]$，有 1 ^ 2 ^ 3 = 0，更关键的是 $0$ 甚至都没出现过。
所以我们考虑将每个数字随机 map 到一个很大的范围，如 $[1,2^{63}]$。
这样，询问 $[L,R]$ 时，我们计算这个 XOR 和，假设为 $x$。那么 $x$ 就很有可能是我们的答案。
当然，也有可能 $x$ 压根就没出现在 $[L,R]$ 这个范围内，所以我们预处理一下每一个数出现的位置，然后二分一下验证 $x$ 是否在 $[L,R]$ 范围内即可。
什么情况下会失败？
假设有 $n$ 个出现次数为奇数的数字，而我们得到的XOR和 $x$ 恰好是这 $n$ 个数字中的一个，就会错误的判断 $x$ 为答案。
不过这样的概率只有 $\frac{n}{2^{63}} = 3 \times 10^{-13}$。
$10^6$ 次询问均正确的概率为 $(1-3 \times 10^{-13})^{10^6} = 0.999999…$
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e6+55;
const int maxm = 1e5+55;
int n, k, q;
ll a[maxn], sum[maxn];
unordered_map<int, ll> mp;
unordered_map<ll, int> rev_mp;
vector<int> pos[maxm];
int main() {
fastio;
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pos[a[i]].push_back(i);
if (!mp.count(a[i])) {
ll r = randll(1, (1LL<<63));
mp[a[i]] = r;
rev_mp[r] = a[i];
}
a[i] = mp[a[i]];
}
for (int i = 1; i <= n; i++) sum[i] = sum[i-1] ^ a[i];
while (q--) {
int l, r; cin >> l >> r;
ll x = sum[r] ^ sum[l-1];
if (!x) cout << 0 << "\n";
else {
// 答案很可能是 x，查询 x 是否在 [L,R] 中出现过？
x = rev_mp[x]; // 先 map 回原来的样子
auto itr = lower_bound(pos[x].begin(), pos[x].end(), l);
if (itr != pos[x].end() && *itr >= l && *itr <= r) {
cout << x << "\n";
} else cout << 0 << "\n";
}
}
}
例5 Zero Sum
题意
给定一个 $n \times (2k+1)$ 的矩阵。column的编号是从 $-k$ 到 $k$。
求一串数字 $x_1,x_2,…,x_n$，其中：
- $x_i \in [-k, k]$。
- $x_1+x_2+…x_n = 0$。
- $a_{1,x_1} + a_{2,x_2} + … + a_{n,x_n}$ 尽可能小。
其中，$n \leq 35000, 1 \leq k \leq 3$，矩阵元素在 $[-10^9, 10^9]$。
题解
注意到 $k$ 很小。
我们想象一下，答案是一条从第一行从上到下走到最后一行的一条路径。
这条路径一定是左拐右拐，最后才能保证 $x_1+x_2+…x_n = 0$。
那么一个很简单的思路是 dp[i][j] 代表走到第 $i$ 行，当前的 column 的编号和为 $j$ 的最小值。
但是 $j$ 的绝对值可能会很大，因为这条路径有可能是先拐到最右，再拐回最左。
于是我们想到利用随机化打乱input。将所有的row随机shuffle以后，答案不大可能出现上述的情况。
所以我们可以在shuffle之后，认为 dp[i][j] 里的 j 的绝对值不会很大。然后再跑 dp 就可以了。
• 需要滚动数组否则 MLE。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 35000+5;
const int M = 1500;
ll a[maxn][9];
ll pre[maxn], dp[maxn];
int n, k;
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 2*k+1; j++) cin >> a[i][j];
}
vector<int> perm;
for (int i = 1; i <= n; i++) perm.push_back(i);
shuffle(perm.begin(), perm.end(), rng);
for (int j = 1; j <= 2*M+1; j++) dp[j] = pre[j] = 1e18;
pre[M+1] = 0;
for (int i = 0; i < n; i++) {
int p = perm[i];
for (int j = 1; j <= 2*M+1; j++) {
for (int d = -k; d <= k; d++) {
if (j + d >= 1 && j + d <= 2*M+1) {
dp[j+d] = min(dp[j+d], pre[j] + a[p][d+k+1]);
}
}
}
memcpy(pre, dp, sizeof(dp));
for (int j = 1; j <= 2*M+1; j++) dp[j] = 1e18;
}
cout << pre[M+1] << endl;
}
例6 KTH Challenge 2014 - Pizza Problems
题意
我们有一个pizza，上面需要有一些种类的配料。
有 $n$ 个人，每个人有 $[1,30]$ 个愿望，每个愿望可以是希望某一种配料存在，也可以是希望某一种配料不存在。
保证一定存在一种pizza使得每个人至少有 $\frac{2}{3}$ 的愿望被满足，而我们只需要找出一种pizza使得每个人有严格大于 $\frac{1}{3}$ 的愿望被满足即可。
其中，$n\leq 10000$，总配料种类不超过 $250$ 种。
题解
我们从没有配料的pizza开始，我们设当前pizza与理想pizza的共同点有 $k$ 个。
我们每一步随机选择一个尚未被满足的人，随机的满足他的一个愿望。注意由于理想的pizza一定保证 $\frac{2}{3}$ 的愿望被满足，而这个人尚未被满足说明他被满足的愿望比例 $<\frac{1}{3}$。这意味着这次修改至少有 $\frac{1}{2}$ 使得我们离理想的pizza的共同点 +1，有 $\leq \frac{1}{2}$ 的概率使得共同点 -1。
接下来要解决：大概需要随机走多少步才能使得当前pizza与理想pizza的共同点数量达到一个值？（这个值最高为 $250$），我们不关心这个值具体是多少，因为我们只要走到满足题目条件停止即可，而我们知道每走一步，共同点+1的概率都是 $\geq \frac{1}{2}$ 的。
这是一个随机游走（random walk）问题：
从 $x=0$ 出发，每次随机向左/向右走一步，问第一次走到 $x=\pm n$ 的期望步数？
结论：期望步数为 $O(n^2)$，证明见 这个知乎回答。
• 注意这个题不太一样，不能走到负数位置，而且要走到的是 $x=n$。我们可以理解成可以走到负数，但是走到负数时就进行一次反射，把 $x$ 轴翻了过来，所以本质上还是走到 $x=\pm n$ 的期望步数，而本题中，期望步数为 $O(250^2)$。
最后一些注意点：
- 由于有 $n=10000$ 个人，每个人至多 $30$ 个愿望，而总共 $250$ 种配料，这意味着每一种配料至多与 $10000*30/250 = 1200$ 个人有关，所以每次满足愿望以后不需要修改所有人，只要记录和这个配料有关的人即可。
- 必须是随机满足愿望，无论这个愿望是希望某个配料存在，或者是不存在。不能将存在/不存在分开随机，否则会陷入死循环。在代码中利用了
void fulfill(int i) { int r = randint(0,1); if (r == 0) { if (!fulfillgood(i)) fulfillbad(i); } else { if (!fulfillbad(i)) fulfillgood(i); } }来实现。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 15000+5;
int n;
vector<int> g[maxn], b[maxn];
map<string, int> mp;
string revmp[maxn];
int cnt[maxn], all[maxn];
bool cur[maxn];
vector<int> yes[maxn], no[maxn];
void upd(int x, int f) {
if (f == 1) {
cur[x] = 1;
for (int i : yes[x]) cnt[i]++;
for (int i : no[x]) cnt[i]--;
} else {
cur[x] = 0;
for (int i : no[x]) cnt[i]++;
for (int i : yes[x]) cnt[i]--;
}
}
bool fulfillgood(int i) {
shuffle(g[i].begin(), g[i].end(), rng);
for (int x : g[i]) {
if (!cur[x]) {
upd(x, 1);
return 1;
}
}
return 0;
}
bool fulfillbad(int i) {
shuffle(b[i].begin(), b[i].end(), rng);
for (int x : b[i]) {
if (cur[x]) {
upd(x, -1);
return 1;
}
}
return 0;
}
void fulfill(int i) {
int r = randint(0,1);
if (r == 0) {
if (!fulfillgood(i)) fulfillbad(i);
} else {
if (!fulfillbad(i)) fulfillgood(i);
}
}
int main() {
fastio;
cin >> n;
int id = 0;
for (int i = 1; i <= n; i++) {
int m; cin >> m;
while (m--) {
string s; cin >> s;
int f = ((s[0] == '+') ? 1 : 0);
s.erase(s.begin());
int x;
if (!mp.count(s)) mp[s] = ++id, revmp[id] = s;
x = mp[s];
if (f) g[i].push_back(x), yes[x].push_back(i);
else b[i].push_back(x), no[x].push_back(i);
}
all[i] = g[i].size() + b[i].size();
cnt[i] = b[i].size();
}
while (1) {
for (int i = 1; i <= n; i++) {
if (cnt[i] * 3 <= all[i]) {
fulfill(i);
goto nxt;
}
}
for (int j = 1; j <= 250; j++) {
if (cur[j]) cout << revmp[j] << "\n";
}
return 0;
nxt:;
}
}