题解：P13552 鱼类考古学

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

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

全部缩成一个数，递归到子问题。

Code

CPP

#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;
}

题解：P13552 鱼类考古学

文章操作

P13552 鱼类考古学

相关推荐

评论

题解：P13552 鱼类考古学