专栏文章

题解：CF1977D XORificator

__Missile_
CF1977D题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miopul1v
此快照首次捕获于
2025/12/02 23:11
3 个月前
此快照最后确认于
2025/12/02 23:11
3 个月前
查看原文

题意

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

思路

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

代码

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

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...