CF1660E-Matrix and Shifts
题目大意
给你一个 \(n\cdot n\) 的 \(0,1\) 矩阵，你可以先无限次将矩阵循环左移，右移，上移，下移。然后你可以进行若干次操作，将一位上的 \(0,1\) 倒置。问你最少进行多少次倒置操作，使得整个矩阵变成一个单位矩阵。
题解
首先无论怎么循环移动，可能属于一条主对角线上的数字都是固定的。所以我们只需要统计一共 \(n\) 条可能作为主对角线上的 \(1\) 的数量。取最多一个。那么答案就是，将这条对角线补齐 \(1\) 和将其他 \(1\) 变成 \(0\) 的总操作次数。
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define umap unordered_map
#define pq(x) priority_queue<x>
#define ppq(x) priority_queue<x,vector<x>,greater<x>>
#define endl '\n'
using namespace std;
using i128 = __int128;
const int mod =1e9+7;
template <typename T>void read(T&x){x=0;int f = 1;char c=getchar();for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);x*=f;
}
template <typename T>void print(T x) {if (x < 0) { putchar('-'); x = -x; }if (x > 9) print(x / 10);putchar(x % 10 + '0');
}
#define int long long
const int N=5e5+5;
const int M=2e6+5;
inline void solve()
{int n;cin>>n;vector<string> s(n);for(int i=0;i<n;i++){cin>>s[i];}vector<int> sum(n+1);for(int i=0;i<n;i++){for(int j=0;j<n;j++){sum[(j-i+n)%n]+=s[j][i]-'0';}}int ans=0,maxn=0;for(int i=0;i<n;i++){maxn=max(maxn,sum[i]);ans+=sum[i];}cout<<ans-maxn+(n-maxn)<<endl;
}signed main()
{ios;int T=1;cin>>T;for(;T--;) solve();return 0;
}