题目链接：Codeforces 1185F

有 $n$ 个人想要买两个比萨。众所周知，比萨共有 $9$ 种成分，用 $1$ 到 $9$ 的整数表示。每个人都有若干喜欢的成分（至多有 $9$ 种）；商店里一共有 $m$ 个比萨，每个比萨都有若干成分组成和一个价格 $c_i$。

你需要选择 $2$ 个比萨，使这些人中满足的人数最多。如果一个人是满足的当且仅当对于任何一个他喜欢的成分，至少出现在其中一个比萨中。如果有多种方案，输出价格最小的方案。

数据范围：$1 \le n \le 10 ^ 5$，$2 \le m \le 10 ^ 5$，$1 \le c_i \le 10 ^ 9$。

Solution

暴力枚举两个比萨的成分集合 $i, j$，那么可以满足所有成分集合为 $k$ 且 $k \subseteq i \cup j$ 的人。

分析一下这样暴力枚举的复杂度。设全集的二进制位数为 $f$，枚举 $i \cup j$ 的位数为 $b$。对于确定的 $i \cup j$，一共有 $3 ^ b$ 对 $(i, j)$ 满足条件（考虑某一位上的 $1$ 有 $3$ 种情况），得到：

$$ T(f) = \sum_{b = 0} ^ f \binom{f}{b} 3 ^ b \cdot 2 ^ b = 7 ^ f $$

此处的 $f = 9$，则复杂度为 $\mathcal O(7 ^ 9)$。

时间复杂度：$\mathcal O(n + m + 7 ^ f)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 1 << 9;
const int INF = 0x7f7f7f7f;

int n, m, cnt[N], fir[N], sec[N], idf[N], ids[N];

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int k, msk = 0;
        scanf("%d", &k);
        for (int j = 1; j <= k; j++) {
            int x;
            scanf("%d", &x);
            msk |= 1 << (x - 1);
        }
        cnt[msk]++;
    }
    std::fill(fir, fir + N, INF);
    std::fill(sec, sec + N, INF);
    for (int i = 1; i <= m; i++) {
        int c, k, msk = 0;
        scanf("%d%d", &c, &k);
        for (int j = 1; j <= k; j++) {
            int x;
            scanf("%d", &x);
            msk |= 1 << (x - 1);
        }
        if (c < fir[msk]) {
            sec[msk] = fir[msk], ids[msk] = idf[msk];
            fir[msk] = c, idf[msk] = i;
        } else if (c < sec[msk]) {
            sec[msk] = c, ids[msk] = i;
        }
    }
    int ans1, ans2;
    auto ans = std::make_pair(-1, 0);
    for (int i = 1; i < N; i++) {
        for (int j = 1; j < N; j++) {
            int c1, c2, id1, id2;
            if (i == j) {
                c1 = fir[i], c2 = sec[i], id1 = idf[i], id2 = ids[i];
            } else {
                c1 = fir[i], c2 = fir[j], id1 = idf[i], id2 = idf[j];
            }
            if (id1 == 0 || id2 == 0) continue;
            int cst = c1 + c2, now = 0;
            for (int S = i | j, T = S; T >= 1; T = (T - 1) & S) now += cnt[T];
            if (std::make_pair(now, -cst) > ans) {
                ans = std::make_pair(now, -cst), ans1 = id1, ans2 = id2;
            }
        }
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}
最后修改：2019 年 06 月 25 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏