【Codeforces 1107D】Compression

题意

【题解】

先把所给的压缩形式的字符串转成二进制
然后对获得的01数组做一个前缀和(a[i][j]=以(i,j)为右下角,(1,1)为左上角的矩形内的数字的和)
这样就能O(1)复杂度获得一个长度为x的正方形的区间和了。
这样。我们直接暴力从1..n枚举n的因子x
显然每个因子x要进行(n/x)^2次判断。
有个性质
∑(n/x)^2=n^2*∑(1/(x^2))=n^2*(π^2/6)
所以实际上时间复杂度约等于O(n^2)

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 5200;

int n;

int a[N+10][N+10];

char s[N+10][N+10];

int main(){

    /*

      4

      3

      3

      3

      3

    */

    scanf("%d",&n);

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

        scanf("%s",s[i]);

        for (int j = 0;j < n/4;j++){

            int key = s[i][j]-'0';

            if (s[i][j]>='A' && s[i][j]<='F'){

                key = s[i][j]-'A'+10;

            }

            for (int k = 0;k < 4;k++){

                a[i][j*4+4-k] = key%2;

                key/=2;

            }

        }

    }

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

        for (int j = 1;j <= n;j++)

            a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j];

    int ans = -1;

    for (int x = 1;x <= n;x++)

        if (n%x==0){

            bool flag = true;

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

                for (int j = x;j <= n;j+=x){

                    int x0 = i-x+1,y0 = j-x+1;

                    int x1 = i,y1 = j;

                    int num = a[x1][y1]-a[x0-1][y1]-a[x1][y0-1]+a[x0-1][y0-1];

                    if (num!=0 && num!=x*x){

                        flag = false;

                        break;

                    }

                }

                if (!flag) break;

            }

            if (flag){

                ans = x;

            }

        }

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

    return 0;

}

巴特西

【Codeforces 1107D】Compression

最新文章

热门文章