题解 P2733 【家的范围 Home on the Range】
z3475
2018-02-22 20:10:18
贡献一发蒟蒻的做法
#### 首先我们来推边长为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优化
还有这题读入有点坑...
```cpp
#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);
}
```