自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 23:07:41，当前版本为作者最后更新于2024-12-28 00:09:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解析

规模很小，考虑枚举选择了哪些蓝牌。

假设选择了集合 $lhs$ 里的蓝牌，我们可以知道选择每张红牌贡献的好对数。具体来说，如果第 $i$ 张红牌能和集合 $\mathrm{matched}_i$ 里的蓝牌产生好对，那么第 $i$ 张牌贡献的好对数就是 $rhs(i) = |lhs \bigcap \mathrm{matched}_i|$。因为牌的数量很少，所以 $lhs$ 和 $\mathrm{matched}_i$ 都可以压位成 int，集合求交可以对两个整形做按位与，求集合大小可以通过 std::popcount 来实现。

注意这里 $lhs$ 是蓝牌选牌集合，$rhs(i)$ 是第 $i$ 张牌的贡献，两者含义不是对称的。

接下来考虑枚举选了几张红牌。显然尽可能选择贡献较大的红牌是优的，所以把 $rhs$ 数组从大到小排序，贪心地选前几项并尝试更新答案即可。

时间复杂度 $O(2^m \times n \times t(w))$，其中 $t(w)$ 表示一次 popcount 的时间。

代码

#include <bits/stdc++.h>

int main() {
  int n, m, x, y;
  std::cin >> n >> m >> x >> y;
  std::vector<int> matched(n);
  for (auto &i : matched) {
    std::string s;
    std::cin >> s;
    for (int j = 0; j < m; ++j) if (s[j] == '1') i ^= 1 << j;
  }
  int ans = 0;
  for (int lhs = 0, upc = 1 << m; lhs < upc; ++lhs) {
    std::vector<int> rhs(n);
    for (int i = 0; i < n; ++i) {
      rhs[i] = std::popcount(static_cast<unsigned>(matched[i] & lhs));
    }
    std::sort(rhs.begin(), rhs.end(), std::greater<int>());
    int matchedCnt = 0;
    int lhsCnt = std::popcount(static_cast<unsigned>(lhs));
    for (int j = 0; j < n; ++j) {
      matchedCnt += rhs[j];
      ans = std::max(ans, matchedCnt - y * lhsCnt - x * (j + 1));
    }
  }
  std::cout << ans << std::endl;
}