构造题的应用

在 n 较小时，确定一个随机数的seed mt19937 rng(SOME_SEED);，如果在本地成功跑出来结果，就直接把这个seed交上去，这样就可以deterministic保证答案是对的。

color coding

一个很有趣的概念，意思是对于一个很难解决的问题，可以考虑先将问题中的一些变量染色，对于不同颜色分别解决。或者是染色后，根据某些与颜色有关的性质进行操作。

例题见例2和例3。

破坏input的性质

如果input是一些较小的正整数，并且它们之间可能有一定规律，将input map到一个较大的范围可以破坏掉input的一些限制。从而获得一些有用的特性。

例题

例1 CF364D. Ghd

题意

给定一个长度为 n 的数组 a1,a2,…,an，定义其ghd为：

最大的一个数 g，使得 ai 中有至少一半的数 divisible by g。

求一个数组的 ghd。

其中，n≤106,ai∈[1,1012]。

题解

好题。考虑随机化：

显然，我们随机选一个 ai，并且求出它的所有因数，那么有 50% 的概率使得ghd在 ai 的因数中。

但众所周知一个数的因数数量是 O(n13) 级别的（证明见这里），ai≤1012，很明显这有点太大了。

我们需要快速解决以下问题：

给定一个数 x，求 x 的每一个因数能够被多少个 ai 整除。

有一个 O(d2) 的基于 dp 的方法（d 是 x 的因数数量）。

先将 x 的所有因数求出来，然后sort一下，我们维护一个 cnt[] 数组，其中 cnt[i] 代表 x 的第 i 个因数能够被多少个 ai 整除。

然后将 x 与每一个 ai 取 gcd，得到 gi，那么 gi 就是满足 既是 x 的因数，又是 ai 的因数 的最大因数。

那么我们先找到 gi 对应 x 的第几个因数，先让对应的 cnt[j]++。

然后从小到大 dp，对于小的因数，如果某个更大的因数能够整除它，那么就将大的 cnt 加到小的上去。

这样 cnt[] 有了就可以更新答案了。

这样随机个10次左右即可（我代码中随机3秒停止）。

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#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 个正整数 a1,a2,…,an 和两个正整数 L1,L2。

从中选出四个数，ai,aj,al,ak 使得：

  1. ai+aj≤L1
  2. al+ak≤L2
  3. i,j,l,k 互不相同

并且求出 ai+aj+al+ak 可能的最大值，如果无解输出 −1。

其中，n≤2000,ai,L1,L2∈[1,10000]。

题解

显然 ai,aj 和 al,ak 是两个独立的问题。

对于其中一个问题，显然可以用二分来做。但现在有两个问题。

所以不妨将原数组随机分成两等份，然后分别对两份数组进行操作。

假设最优答案为 ai′,aj′,al′,ak′，那么 ai′,aj′ 在第一份数组，且 al′,ak′ 在第二份的数组的概率为 18。

重复很多次即可。

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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 个龙珠，每个龙珠会拥有一个颜色 di，并且这个龙珠会存在于节点 ci 中。

我们从节点 1 出发，经过一个节点时会获得这个节点里的所有龙珠。

求最短路径的长度，使得我们收集了至少 7 个不同颜色的龙珠。如果无解输出 −1。

其中，n,k≤1000,m≤10000,wi∈[0,10000],ci,di∈[1,n]。

题解

我们只需要收集 7 个不同的颜色，但原图中的颜色有 n 种，怎么办？

考虑 color coding 的思想：

我们不妨假设只有 7 种颜色，然后对于原图中的每一种颜色，将它们随机 map 到七种颜色中的一种，然后就只有 7 种颜色了。

只有 7 种颜色后，明显可以直接维护大小为 27 的mask，然后跑dijkstra。

什么情况下答案会出错呢？

假设答案需要颜色 di1,di2…di7，那么如果有任意两个颜色被map到同一种，就说明答案错误了。

因此，答案正确的情况有 A77=7! 种。

答案正确的概率为 7!77=0.006。

这个题目时限为 16 秒，大概可以跑 109。这个dijkstra相当于在 M=104∗27=1.28∗106 的情况下跑 O(Mlog⁡M)（实际上吃不了这么满）。

实际上大概可以跑 800−1000 次。失败概率约为 5 % 左右，运气好还是可以跑过去的。

• 另外如果我们提升随机颜色的数量，运行次数只会大幅度缩小，而成功概率不会提升很多，所以 7 种颜色就是最好的。

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#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 的正整数数组 a1,a2,…,an。

有 q 个询问，每次询问 [L,R] 之间是否存在恰好一个出现次数为奇数的数字，如果存在，输出它，否则输出 0。

其中，n≤3×106,q≤106,ai∈[1,105]。

题解

我们知道一个区间 [L,R] 内，如果恰好有一个出现次数为奇数的数字，那么这个区间的XOR和就是这个数字。

但，有一些例外，比如有多个出现次数为奇数的数字时，XOR和不能说明任何问题。

例如对于 [1,2,3]，有 1 ^ 2 ^ 3 = 0，更关键的是 0 甚至都没出现过。

所以我们考虑将每个数字随机 map 到一个很大的范围，如 [1,263]。

这样，询问 [L,R] 时，我们计算这个 XOR 和，假设为 x。那么 x 就很有可能是我们的答案。

当然，也有可能 x 压根就没出现在 [L,R] 这个范围内，所以我们预处理一下每一个数出现的位置，然后二分一下验证 x 是否在 [L,R] 范围内即可。

什么情况下会失败？

假设有 n 个出现次数为奇数的数字，而我们得到的XOR和 x 恰好是这 n 个数字中的一个，就会错误的判断 x 为答案。

不过这样的概率只有 n263=3×10−13。

106 次询问均正确的概率为 (1−3×10−13)106=0.999999…

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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×(2k+1) 的矩阵。column的编号是从 −k 到 k。

求一串数字 x1,x2,…,xn，其中：

  1. xi∈[−k,k]。
  2. x1+x2+…xn=0。
  3. a1,x1+a2,x2+…+an,xn 尽可能小。

其中，n≤35000,1≤k≤3，矩阵元素在 [−109,109]。

题解

注意到 k 很小。

我们想象一下，答案是一条从第一行从上到下走到最后一行的一条路径。

这条路径一定是左拐右拐，最后才能保证 x1+x2+…xn=0。

那么一个很简单的思路是 dp[i][j] 代表走到第 i 行，当前的 column 的编号和为 j 的最小值。

但是 j 的绝对值可能会很大，因为这条路径有可能是先拐到最右，再拐回最左。

于是我们想到利用随机化打乱input。将所有的row随机shuffle以后，答案不大可能出现上述的情况。

所以我们可以在shuffle之后，认为 dp[i][j] 里的 j 的绝对值不会很大。然后再跑 dp 就可以了。

• 需要滚动数组否则 MLE。

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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使得每个人至少有 23 的愿望被满足，而我们只需要找出一种pizza使得每个人有严格大于 13 的愿望被满足即可。

其中，n≤10000，总配料种类不超过 250 种。

题解

我们从没有配料的pizza开始，我们设当前pizza与理想pizza的共同点有 k 个。

我们每一步随机选择一个尚未被满足的人，随机的满足他的一个愿望。注意由于理想的pizza一定保证 23 的愿望被满足，而这个人尚未被满足说明他被满足的愿望比例 <13。这意味着这次修改至少有 12 使得我们离理想的pizza的共同点 +1，有 ≤12 的概率使得共同点 -1。

接下来要解决：大概需要随机走多少步才能使得当前pizza与理想pizza的共同点数量达到一个值？（这个值最高为 250），我们不关心这个值具体是多少，因为我们只要走到满足题目条件停止即可，而我们知道每走一步，共同点+1的概率都是 ≥12 的。

这是一个随机游走（random walk）问题：

从 x=0 出发，每次随机向左/向右走一步，问第一次走到 x=±n 的期望步数？

结论：期望步数为 O(n2)，证明见 这个知乎回答。

• 注意这个题不太一样，不能走到负数位置，而且要走到的是 x=n。我们可以理解成可以走到负数，但是走到负数时就进行一次反射，把 x 轴翻了过来，所以本质上还是走到 x=±n 的期望步数，而本题中，期望步数为 O(2502)。

最后一些注意点：

  1. 由于有 n=10000 个人，每个人至多 30 个愿望，而总共 250 种配料，这意味着每一种配料至多与 10000∗30/250=1200 个人有关，所以每次满足愿望以后不需要修改所有人，只要记录和这个配料有关的人即可。
  2. 必须是随机满足愿望，无论这个愿望是希望某个配料存在，或者是不存在。不能将存在/不存在分开随机，否则会陷入死循环。在代码中利用了
    copy
    1
    2
    3
    4
    5
    6
    7
    8
     void fulfill(int i) {
         int r = randint(0,1);
         if (r == 0) {
             if (!fulfillgood(i)) fulfillbad(i);
         } else {
             if (!fulfillbad(i)) fulfillgood(i);
         }
     }

    来实现。

代码
copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#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:;
    }
}

参考PDF

NAC2023 - Randomized