寻找团伙(Finding the Crew) 题解

思路分析

将每位人士的能力压成一个 unsigned long long 二进制掩码 mask[i]（第 $j$ 项能力对应 1ULL << (k - j)）。由于奇数人拥有保留、偶数人拥有抵消，选出一个子集后的团队总能力掩码恰好等于所选成员 mask[i] 的按位异或和，同时该掩码的无符号整数值恰好等于对应的权重之和！因为 $n \le 21$，直接 DFS 枚举每个人选或不选（时间复杂度 $O(2^n)$）维护异或和最大值即可（也可用 $60$ 位线性基在 $O(nk)$ 内求解）。注意 $k = 60$ 时需用 unsigned long long 的 1ULL。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

unsigned long long basisArr[64];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    for (int i = 0; i < n; ++i)
    {
        int c;
        cin >> c;
        unsigned long long mask = 0;
        for (int j = 0; j < c; ++j)
        {
            int x;
            cin >> x;
            mask |= (1ULL << (k - x));
        }
        for (int b = k - 1; b >= 0; --b)
        {
            if (!((mask >> b) & 1ULL)) continue;
            if (!basisArr[b])
            {
                basisArr[b] = mask;
                break;
            }
            mask ^= basisArr[b];
        }
    }
    unsigned long long ans = 0;
    for (int b = k - 1; b >= 0; --b)
    {
        if ((ans ^ basisArr[b]) > ans) ans ^= basisArr[b];
    }
    cout << ans << "\n";
    return 0;
}