題目

有 n 個人，每人都喜歡特定的加密貨幣，尋找最大的貨幣集合使得有 $$\lceil\frac{n}{2}\rceil$$ 個人喜歡集合裡所有貨幣。

解法

隨機選一個人，答案集合為他的子遮罩機率是 $$\frac{1}{2}$$，選個 50 次一定能選到目標。

選中的人喜歡最多 15 種幣，將所有人喜好壓縮成只考慮這些幣

1
2
3


11001 -> 111 (選中)
10101 -> 101
00110 -> 000

直接枚舉集合判斷它是幾個人的子遮罩，複雜度 $$O(50n(p+2^p))$$，一定超時。

優化

設 dp[mask] 表示 mask 是幾個人的子遮罩。

1

dp[mask ^ 1 << k] += dp[mask] if mask & 1 << k

如果 dp[mask] * 2 >= n 就更新答案，複雜度 $$O(50p(n+2^p))$$。

對了，rand() 最大值只到 32767，必須改用 random 裡的生成器。

 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


string s[200000];
int dp[32768], index[15], n, m, p, target, result = 0;

void handle(int base) {
    p = 0;
    for(int j = 0; j < m; j++) {
        if(s[base][j] == '1') {
            index[p++] = j;
        }
    }
    fill_n(dp, 1 << p, 0);
    for(int i = 0, num; i < n; i++) {
        num = 0;
        for(int j = 0; j < p; j++) {
            num <<= 1;
            num |= s[i][index[j]] == '1';
        }
        dp[num]++;
    }
    for (int j = 0; j < p; j++) {
        for (int mask = 0; mask < 1 << p; mask++) {
            if (mask & (1 << j)) {
                dp[mask ^ (1 << j)] += dp[mask];
            }
        }
    }
    for(int mask = 1; mask < 1 << p; mask++) {
        if(dp[mask] << 1 >= n && __builtin_popcount(result) < __builtin_popcount(mask)) {
            result = mask;
            target = base;
        }
    }
}

void solve() {
    cin >> n >> m >> p;
    for(int i = 0; i < n; i++) {
        cin >> s[i];
    }
    mt19937 rng(time(0));
    uniform_int_distribution<int> gen(0, n - 1);
    for(int i = 0; i < 50; i++) {
        handle(gen(rng));
    }
    // 重建答案
    for(int j = m - 1; j >= 0; j--) {
        if(s[target][j] == '1') {
            if(!(result & 1)) {
                s[target][j] = '0';
            }
            result >>= 1;
        }
    }
    cout << s[target];
}