题解：CF1977D XORificator

_Missile_ · 2025-07-26 19:50:01 · 题解

题意

给定一个 n 行 m 列且只包含 0 和 1 的矩阵，考虑将其中几行中的 0、1 数字全部翻转。如果某一列恰好包含一个 1，则得分加 1。求可能的最大得分。

思路

对于矩阵中的每一个数字，可以考虑如果它是当前列唯一一个 1 需要翻转哪些行，这样就共有 O(n \cdot m) 种状态。

具体地，我们可以枚举每一列，先枚举一遍每一个数字，记录出将这一列全变成 0 要翻转哪些行，然后再考虑每一个数字作为唯一一个 1 要翻转哪些行。而这相当于就是先将所有数字变为 0 ，再翻转一下当前行。不过这样每次记录一个长度为 n 的翻转序列会超时，因此我们考虑字符串哈希。对于每一种翻转序列，如果它是最优的，出现次数就一定是最多的，因此我们的答案就是最多的出现次数。而具体的反转序列，我们只需要记录一下它是由矩阵中的哪一个单元格计算出来的，最后输出时判断一下要让记录的单元格成为那一列唯一一个 1 是否需要翻转当前行即可。AC记录

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3e5 + 5;
const int mod = 25364761;

ll n, m, p[N];
mt19937_64 gen(time(0));

struct tp{
  ll x, y, cnt;
};

map<ll, tp> mp;

void solve(){
  cin >> n >> m;
  vector<vector<char>> a(n + 1, vector<char> (m + 1, ' '));
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= m; j++){
      cin >> a[i][j];
    }
  }
  p[0] = 0;
  for(int i = 1; i <= n; i++){
    p[i] = gen();
  }
  mp.clear();
  ll ans = 0, po = 0;
  for(int i = 1; i <= m; i++){
    ll op = 0;
    for(int j = 1; j <= n; j++){
      if(a[j][i] == '1'){
        op ^= p[j];
      }
    }
    for(int j = 1; j <= n; j++){
      op ^= p[j - 1];
      op ^= p[j];
      mp[op] = {j, i, mp[op].cnt + 1};
      if(mp[op].cnt > ans){
        ans = mp[op].cnt;
        po = op;
      }
    }
  }
  cout << ans << '\n';
  tp it = mp[po];
  for(int i = 1; i <= n; i++){
    cout << ((i == it.x && a[i][it.y] == '0') || (i != it.x && a[i][it.y] == '1') ? 1 : 0);
  }
  cout << '\n';
}

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