《寻找团伙》题解

阮行止 · 2022-03-13 23:16:59 · 题解

简化题意：给定一个整数集合，寻找子集使异或和最大。

本题 n\leq 21，可以暴力枚举子集。k\leq 60，可以采用 unsigned long long 来存储二进制位（不必开 bool 数组）。

细节：

• 读入每个人的能力时，应该用 p[i] |= (1ULL << (k - x)) 来标记 i 人士拥有 x 能力。需要注意这个 ULL，如果不加，编译器将其视为 int 型的 1，程序会 WA。

枚举子集有多种方式。我们下面的代码采用了递归枚举，但也可以使用二进制技巧枚举子集。

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
ull p[30];
int n, k;

void input() {
    cin >> n >> k;

    for(int i=0; i<n; i++) {
        int c, x;
        cin >> c;

        while(c--) {
            cin >> x;
            p[i] |= (1ULL << (k - x));   // 人士 i 拥有 x 能力，修改对应 bit
        }
    }
}

int choice[30];
ull ans;

void dfs(int pos) {
    if(pos == n) {
        ull res = 0;
        for(int i=0; i<n; i++)
            if(choice[i])
                res ^= p[i];

        ans = max(res, ans);
        return;
    }

    choice[pos] = 0;
    dfs(pos + 1);
    choice[pos] = 1;
    dfs(pos + 1);
}

void work() {
    dfs(0);
    cout << ans << endl;
}

int main() {
    input();
    work();

    return 0;
}

上述代码的复杂度为 \mathcal{O}(2^n \cdot k)，其中 2^n 为枚举子集的复杂度。

需要指出，本题可以采用线性基 + 贪心来做。线性基能以 \mathcal{O}(nk) 的复杂度完成任务，在此仅给出 Python 代码，有兴趣的同学可以去学习。

import numpy as np
from functools import reduce

n, k = map(int, input().split())
s = np.zeros([k, k], dtype=int)

for x in range(n):
    r = list(map(int, input().split()))[1:]
    p = np.array([1 if i+1 in r else 0 for i in range(k)])

    for pos in range(k):
        if p[pos] == 1:
            if s[pos, pos] == 1:
                p ^= s[pos]
            else:
                s[pos] = p
                break

res = np.zeros([k], dtype=int)
for pos in range(k):
    if res[pos] == 0 and s[pos, pos] == 1:  # 贪心
        res ^= s[pos]

print(reduce(lambda x,y: x*2+y, res))    # 二进制转整数输出