题解：P13552 鱼类考古学

chenwenmo · 2025-08-11 21:39:45 · 题解

总结：位运算最优化问题考虑按位贪心。

P13552 鱼类考古学

因为 (a+b)\otimes c\le c\le (a\otimes b)+c，因此我们一定是先 \otimes 再 +。

因此问题转化为，将全集分成 k 个集合（不是题目中的 k），使得每个集合权值总和最大，一个集合的权值定义为所有元素按位与。

赛时卡这了，没想到按位贪心。

从高位往低位考虑，发现按位贪心是对的，即，这一位在满足更高位限制的前提下，尽量产生最多 1，一定是最优的。证明如下：

• 假设考虑的是第 i 位，当前位每个 1 贡献为 2^i，定义一个集合的价值为 x 表示该集合权值的第 i 位是 x，x\in\{0,1\}。

• 设有 a 个价值为 1 的集合（A 类集合），有 b 个价值为 0 且有 1 的集合（B 类集合），有 c 个价值为 0 但只有 0 的集合（C）类集合。

• 如果 b>0,c>0，可以把任意一个 B 类集合中的 1 构成新的 A 类集合，剩余的 0 和任意一个 C 类集合合并。由于这个过程只涉及两个集合之间的元素转移，那么减少的贡献一定 <2^{i}，而增加的贡献 =2^i，因此答案变大。

• 如果存在一个 A 类集合 S，|S|>1，且 c>1，那么可以把 S 拆分成两个 A 类集合，并把 C 类集合任意两个合并。显然拆分集合不会减少贡献，合并集合时减少的贡献也 <2^{i}，因此答案增大。

• 因此，根据这样不断调整，答案一定不会变小，而调整的结果等价于贪心地使这一位产生的 1 尽量多。

考虑如何实现，首先枚举位，然后维护 k 表示当前需要分成多少个集合。如果 k 大于 1 的数量，直接把每个 1 单独分成一组，然后考虑 0 如何分组，递归到子问题；否则，0 肯定会全部在一个组，那么直接把 0 全部缩成一个数，递归到子问题。

:::success[Code]

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using UI = unsigned int;
using ULL = unsigned long long;
using DB = double;
using LDB = long double;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
#define CP(x) complex<x>
#define fst first
#define snd second
#define popcnt(i) __builtin_popcount(i)

const int N = 1e6 + 5;

int n, k;
LL a[N];

void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    LL ans = 0;
    int m = n;
    for (int i = 29; i >= 0; i--) {
        int cnt = 0;
        for (int j = 1; j <= m; j++) {
            cnt += ((a[j] >> i) & 1);
        }
        if (k > cnt) {
            n = 0;
            for (int j = 1; j <= m; j++) {
                if ((a[j] >> i) & 1) {
                    ans += a[j];
                } else {
                    a[++n] = a[j];
                }
            }
            k -= cnt;
            m = n;
        } else {
            n = 0;
            LL sum = -1;
            for (int j = 1; j <= m; j++) {
                if ((a[j] >> i) & 1) {
                    a[++n] = a[j];
                } else {
                    if (sum == -1) sum = a[j];
                    else sum &= a[j];
                }
            }
            if (sum != -1) {
                a[++n] = sum;
            }
            m = n;
        }
    }
    for (int i = 1; i < k; i++) ans += a[i];
    LL sum = -1;
    for (int i = k; i <= m; i++) {
        if (sum == -1) sum = a[i];
        else sum &= a[i];
    }
    ans += sum;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

:::