题解：P11475 [COCI 2024/2025 #3] 红蓝牌 / Karte

一扶苏一 · 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;
}