z3475 的博客

题解 P2733 【家的范围 Home on the Range】

贡献一发蒟蒻的做法

首先我们来推边长为2的正方形的做法

我们让a[i][j]+=a[i+1][j]+a[i][j+1]+a[i+1][j+1]

那么显然a[i][j]==4时就是一个边长为2的正方形

那么我们再来一下a[i][j]+=a[i+1][j]+a[i][j+1]+a[i+1][j+1]

显然a[i][j]==16时就是一个边长为3的正方形

合理推断

进行w次a[i][j]+=a[i+1][j]+a[i][j+1]+a[i+1][j+1]的运算之后a[i][j]==4^w的话(i,j)就是边长为w+1的正方形的左上角的点的坐标

严谨性请自行证明

时间复杂度为O(n^3)

但是我们又想到a[i][j]最大值肯定是4^n

而n最大为250

肯定会炸int/long long

分析一下

我们在推边长为w的正方形的时候必须要a[i][j],a[i+1][j],a[i][j+1],a[i+1][j+1]都必须是4^(w-1)才成立

我们大可在a[i][j]计算完毕时进行判断,是4就赋值为1,不是4就是零

严谨性请自行证明

这样子的话a[i][j]就只有0,1俩种可能

对,对,对a数组可以上bitset优化

还有这题读入有点坑...

#include <bits/stdc++.h>

using namespace std;

int gc(){
    while (1){
        char o=getchar();
        if (o=='1') return 1;
        if (o=='0') return 0;
    }
}

int main(){
    register int n;
    scanf("%d\n",&n);
    bitset<256> a[n+2];
    for(register int i=1;i<=n;i++)
        for(register int j=1;j<=n;j++)
            a[i][j]=gc();
    register int q=2;
    do{
        register int w=0;
        for(register int i=1;i<=n;i++)
            for(register int j=1;j<=n;j++){
                a[i][j]=a[i][j]&a[i][j+1]&a[i+1][j]&a[i+1][j+1];
                w+=a[i][j];
            }
        if (w==0) return 0;
        printf("%d %d\n",q++,w);
    }while(1);
}

2018-02-22 20:10:18 in 题解