CF1523D Love-Hate 题解

传送门

题目大意：给定 \(m\) 和 \(n\) 个集合，而且这 \(n\) 个集合的元素都是 \(1\) ~ \(m\) 中的数且没有重复，而且大小都不超过 \(15\)。求一个最大的集合，使得这个集合是至少 \(\left\lceil\frac{n}{2}\right\rceil\) 个集合的子集。

先想一个问题：题目是让求集合是任意 \(\left\lceil\frac{n}{2}\right\rceil\) 个集合的子集，那如果我们已经知道它是其中一个给定集合的子集，该怎么求？

这个其实很好算，先让所有集合只保留这个集合有的元素，然后另 \(f_i\) 表示状态为 \(i\) 的这个集合是多少个集合的子集，然后就可以 \(\mathcal{O}(n+p\times 2^p)\) 来求了。

那么回到原题，我们怎么知道这个集合是哪个集合？

假设我们随机选一个，那么最终答案集合不是该子集的可能性仅为 \(\frac{1}{2}\)。

如果我们随机选 \(k\) 个，那么都不是答案的可能就是 \(\frac{1}{2^k}\)。

当 \(k=50\) 时，基本上已经完全不可能了，此时时间复杂度为 \(\mathcal{O}(k\times(n+p\times 2^p))\)。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 200005;

LL a[N];
char s[100];
int f[1 << 15];
int main() {
    int n, m;
    scanf("%d%d%*d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        for (int j = 0; j < m; j++) {
            if (s[j] == '1') a[i] ^= 1LL << j;
        }
    }
    mt19937 g(time(0));
    uniform_int_distribution<int> u1(0, n - 1);
    LL ans = 0;
    int T = 50;
    while (T--) {
        vector<int> b;
        LL ak = a[u1(g)];
        for (int i = 0; i < m; i++) {
            if (ak >> i & 1) b.push_back(i);
        }
        memset(f, 0, sizeof f);
        for (int i = 0; i < n; i++) {
            int t = 0;
            for (int j = 0; j < b.size(); j++) {
                if (a[i] >> b[j] & 1) {
                    t ^= 1 << j;
                }
            }
            f[t]++;
        }

        for (int i = 0; i < b.size(); i++) {
            for (int j = 0; j < 1 << b.size(); j++) {
                if ((j >> i & 1) == 0) f[j] += f[j ^ 1 << i];
            }
        }
        int now = 0;
        for (int i = 0; i < 1 << b.size(); i++) {
            if (f[i] * 2 >= n && __builtin_popcount(i) > __builtin_popcount(now)) now = i;
        }
        if (__builtin_popcount(now) > __builtin_popcountll(ans)) {
            ans = 0;
            for (int i = 0; i < b.size(); i++) {
                if (now >> i & 1) ans ^= 1LL << b[i];
            }
        }
    }
    for (int i = 0; i < m; i++) {
        printf("%d", ans >> i & 1);
    }
    putchar('\n');
    return 0;
}