CodeForces 838A Binary Blocks（前缀和）题解

题意：给你个n*m的矩阵，要求你找到一个k，k > 1，使得矩阵可以分为很多k * k的小正方形，然后进行操作把每个小正方形都变为0或1，问你怎样使操作数最小。

思路：随便暴力不可取，显然你每次遍历查找k * k正方形里1和0的数量会超时。这里新学了一招前缀和，其实和二位树状数组差不多。就是预处理前缀和，以达到花O(1)的时间算出(1,1)~(x,y)的和，这样我们就能直接暴力枚举每一种k的操作数，然后取最小即为答案。

参考：前缀和与差分

代码：

#include<stack>

#include<vector>

#include<queue>

#include<set>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#define ll long long

#define ull unsigned long long

using namespace std;

const int maxn = +;

const int seed = ;

const int MOD = ;

const int INF = 0x3f3f3f3f;

int sum[maxn][maxn];

char s[maxn];

int get(int x1,int y1,int x2,int y2){

    return sum[x2][y2] - sum[x2][y1 - ] - sum[x1 - ][y2] + sum[x1 - ][y1 - ];

}

int main(){

    int n,m,k,end;

    scanf("%d%d",&n,&m);

    end = max(n,m);

    memset(sum,,sizeof(sum));

    for(int i = ; i <= n; i++){

        scanf("%s",s + );

        for(int j = ; j <= m; j++){

            sum[i][j] = s[j] - '';

        }

    }

    for(int i = ;i < maxn;i++){  //前缀和

        for(int j = ;j < maxn;j++){

            sum[i][j] += sum[i][j - ] + sum[i - ][j] - sum[i - ][j - ];

        }

    }

    int ans = INF;

    for(int k = ; k <= end; k++){

        int cnt = ,endL,endR;

        if(n % k == ) endL = n;

        else endL = (n / k + ) * k;

        if(m % k == ) endR = m;

        else endR = (m / k + ) * k;

        for(int i = ; i <= endL; i += k){

            for(int j = ; j <= endR; j += k){

                int have = get(i,j,i + k - ,j + k - );

                cnt += min(have,k * k - have);

            }

        }

        ans = min(ans,cnt);

    }

    printf("%d\n",ans);

    return ;

}

巴特西

CodeForces 838A Binary Blocks（前缀和）题解

最新文章

热门文章