CF1660E Matrix and Shifts 题解

XL4453 · 2022-04-06 07:04:14 · 题解

\text{Difficulty : 1600}

解题思路：

算是一个比较经典的 \text{trick}。

第一步操作是棋盘的一个平移。可以将整个棋盘复制三份构成一个 2n\times 2n 的大棋盘，大棋盘中的每一个 n\times n 的子棋盘相应地对应不同方式的平移。

第二步操作需要的次数只需要统计在对角线上的 1 的个数，记为 cnt，和总共 1 的个数，记为 sum，就能直接求出了，式子是：sum+n-2cnt。

然后问题就转化为每一个子棋盘上的对角线上有多少 1，这个问题可以直接用前缀和求解，S_{i,j} 表示从位置 (i,j) 尽可能地向左上方按主对角线方向拓展路径上存在的 1 的个数。那么每一次确定子矩形之后，只需要用右下角的 S 减去左上角左上的 S 就能确定当前子棋盘主对角线上的 1 的个数了。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int T,n,a[4005][4005],cnt,sum[4005][4005],ans;
int SUM(int x,int y){
    if(x>2*n||y>2*n)return 0;
    if(x<0||y<0)return 0;
    return sum[x][y];
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        cnt=0;
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            scanf("%1d",&a[i][j]);
            cnt+=a[i][j];
        }
        for(int i=0;i<2*n;i++)
        for(int j=0;j<2*n;j++)
        a[i][j]=a[i%n][j%n];
        for(int i=0;i<2*n;i++)
        for(int j=0;j<2*n;j++)
        sum[i][j]=SUM(i-1,j-1)+a[i][j];
        ans=2147483647;
        for(int i=0;i<n+1;i++)
        for(int j=0;j<n+1;j++)
        ans=min(ans,n+cnt-2*(SUM(i+n-1,j+n-1)-SUM(i-1,j-1)));
        printf("%d\n",ans);
    }
    return 0;
}