838A - Binary Blocks【区间前缀和+思维】

题意：已知n*m的矩阵，由1,0构成，要求确定一个k，使得n*m的矩阵划分成一系列k*k的小矩阵，并且k*k矩阵内的所有值都要相同（要么都为1，要么都为0）。 （可以补行或列，补0）

思路：遍历k（1~2500） ， 对于每一个k，我们处理出当前k所需要改变的所有次数。 首先，我们预处理出(1,1)~(i,j)【任意一点】区域中’1’的个数dp[i][j]，那么对于当前k*k的区域，我们所要改变的就是 : dp[i][j]-dp[i-k][j]-dp[i][j-k] + dp[i-k][j-k]，对于每一个k，累加比较，求出最小的次数。

错误分析：瞎猜，以为2肯定是最小的，所以k恒等于2 ， 然后瞎搞搞就wa了5发。

数据分析：2 ≤ n, m ≤ 2 500 k<=max(n,m) <=2500

复杂度分析: O(k*n/k*m/k)=O(m*n/k) 还是很可观的复杂度

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char mp[5050][5050];
int n,m;
int dp[5050][5050];
ll a=0;
ll minn=LONG_LONG_MAX;

void init() // 预处理——关键
{
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=5050-1;i++)
        for(int j=1;j<=5050-1;j++)
           dp[i][j]= mp[i][j]=='1' ? dp[i][j-1]+1: dp[i][j-1];
    for(int i=1;i<=5050-1;i++)
        for(int j=1;j<=5050-1;j++)
            dp[i][j]+=dp[i-1][j];
}

ll solve()
{
    int t=max(n,m);
    for(int k=2;k<=t;k++)
    {
        a=0;
        for(int i=k;i<=n+k ;i+=k)
        {
            for(int j=k;j<=m+k ;j+=k)
            {
                int temp=dp[i][j]-dp[i-k][j]-dp[i][j-k]+dp[i-k][j-k];
                //printf("k=%d i=%d j=%d temp=%d\n",k,i,j,temp);
                a+=1LL*min(temp,k*k-temp);
            }
        }
        if(a<minn)  minn=a;
    }
    return minn;
}

int main(void)
{
    cin >> n>> m;
    for(int i=1;i<=n;i++)
        scanf("%s",mp[i]+1);
    init();
    /*for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) printf("dp[%d][%d]=%d\n",i,j,dp[i][j]);*/
    ll ans=solve();
    cout << ans << endl;
}