题解：P13552 鱼类考古学

int4399 · 2025-12-19 20:23:11 · 题解

题意：有 n 个数，要进行 n-k 次按位与和 k-1 次加法，求最后结果的最大值。

对于这种有多种操作的问题，看能不能推出最优解长啥样。我们发现如果两个数进行加法，那么它之后就不会再按位与了，因为 (a+b)\operatorname{and} c\le c\le c+(a\operatorname{and} b)，这两个用的符号都一样，所以最优解肯定是：先按位与再加。

问题转化：将 n 个数划分为 k 个集合，该划分的权值为所有组的按位与之和，求最大权值。

我们再挖掘最优解的性质，发现这个东西可以按位贪心，因为如果一个集合第 k 位均为 1，你把一个该位不为 1 的数换过来，一定减少 2^k，至多增加 2^k-1，这个可以通过极端思想考虑出来，也就是先考虑高位不劣。

于是问题再次转化：将 n 个 0/1 划分为 k 个集合，该划分的权值为所有组的按位与之和，求最大权值。

继续分析，把 0 和 1 放到一组一定不优，因为调整 1 到别的集合可能答案会更大。答案上界是 k，当 1 的个数小于等于 k 时直接每个 1 单开一组一定最优。