题目
Luogu P2733 家的范围
分析
初看这题没有思路，参考了一下题解的思路，于是用了前缀和。
ans表示以（i,j）为右下角的矩形区域内边长为k的正方形是否存在，以此记录整个矩阵内边长为k的正方形的个数。
用d[i][j]预处理出以（i,j）为右下角，（0,0）为左上角的矩形区域内1的个数。仅当该点为原值1，并且从此点向左上延伸的边长为k的正方形中，1的个数与面积（k*k）相等时，ans++。
代码
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=300;
int a[maxn][maxn],d[maxn][maxn];//a用来存储原值，d处理前缀和；
int main()
{int n;char x;scanf("%d",&n);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>x;a[i][j]=x-'0';d[i][j]=d[i-1][j]+d[i][j-1]-d[i-1][j-1]+a[i][j];
// 处理二维前缀和；}for(int k=2;k<=n;k++)//枚举边长（最小是2）；{int ans=0,s;for(int i=k;i<=n;i++)//枚举横坐标（行）{for(int j=k;j<=n;j++)//枚举纵坐标（列）{s=d[i][j]-d[i-k][j]-d[i][j-k]+d[i-k][j-k];
// 画一个矩形，推算一下运算方式，其实与前缀和计算方式无异；if(s==k*k) ans++;} }if(ans!=0) printf("%d %d\n",k,ans);}return 0;
}