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

z3475

2018-02-22 20:10:18

Solution

贡献一发蒟蒻的做法 #### 首先我们来推边长为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); } ```