首先能够构成正方形的两个对顶点肯定在同一条对角线上，可以想到依次处理每条对角线上的点。
对于每个点，预处理出它能到的四个方向的连续1最多有多少个，记为p_up,p_down,p_left,p_right，显然，决定某一个点向右下能延伸的多少只取决于p_down和p_right中的较小值，决定某一个点向左上能延伸到多少只取决于p_up和p_left的较小值。
对于每个点，记录它能到达的最右的x轴的绝对坐标，并记录它自身的y坐标。
统计一个点和它左上的点(在对角线上)能组成多少个正方形时，只要判断有多少个点向右能和它相交即可。比如统计5，只要记录1~4中有多少点向右能和红线交叉，显然5可以和1，3，4组成边上全部为1的正方形。
HDU给的题解没太看懂，我是用一个堆维护每个点能到的最右的x轴坐标，当堆顶元素向右不能到达该点的x坐标时，就可以将这个点删除，因为这个点已经没有用了，比如统计5时，就可以将2这个点删除，它已经不能和5以及以后的点组成正方形，然后再统计红线范围内有多少点即可，这里用树状数组线段树什么的都可以。
另外这题如果不一条条对角线分别统计会MLE。。。可能是以为我用了堆的缘故吧。。
1 #include <string.h> 2 #include <stdio.h> 3 #include <queue> 4 #define MAXN 1005 5 using namespace std; 6 typedef pair<int,int> pii; 7 typedef __int64 LL; 8 int cas,n,mz[MAXN][MAXN],d[MAXN][MAXN][4]; 9 int c[MAXN]; 10 int lowbit(int x){return x&-x;} 11 void update(int k,int d){ 12 while(k<n+1)c[k]+=d,k+=lowbit(k); 13 } 14 int getans(int k){ 15 int ret=0; 16 while(k)ret+=c[k],k-=lowbit(k); 17 return ret; 18 } 19 int main(){ 20 //freopen("test.in","r",stdin); 21 scanf("%d",&cas); 22 for(int ca=1;ca<=cas;ca++){ 23 scanf("%d",&n); 24 memset(mz,0,sizeof mz); 25 for(int i=1;i<=n;i++) 26 for(int j=1;j<=n;j++) 27 scanf("%d",&mz[i][j]); 28 //计算最长能延伸到4个方向的距离 29 //0:left-> 1:right<- 2:top 3:bottom 30 for(int i=1;i<=n;i++) 31 for(int j=1;j<=n;j++) 32 d[i][j][0]=mz[i][j]?d[i][j-1][0]+1:0, 33 d[i][j][2]=mz[i][j]?d[i-1][j][2]+1:0; 34 for(int i=n;i>=1;i--) 35 for(int j=n;j>=1;j--) 36 d[i][j][1]=mz[i][j]?d[i][j+1][1]+1:0, 37 d[i][j][3]=mz[i][j]?d[i+1][j][3]+1:0; 38 LL ans=0; 39 //枚举对角线,能构成正方形的点的对顶点必然在一条对角线上 40 for(int dt=-n+1;dt<=n-1;dt++){ 41 //用堆维护该对角线上向左和向右都能延伸到当前点的集合 42 //并用树状数组统计某个区间内能到达该点的点的数量 43 priority_queue<pii,vector<pii>,greater<pii> > q; 44 memset(c,0,sizeof c); 45 for(int i=1-dt>0?1-dt:1;i<=n&&i+dt<=n;i++){ 46 int j=i+dt; 47 if(mz[i][j]==0)continue; 48 if(d[i][j][3]<d[i][j][1])d[i][j][1]=d[i][j][3]; 49 if(d[i][j][2]<d[i][j][0])d[i][j][0]=d[i][j][2]; 50 q.push(pii(j-1+d[i][j][1],i)); 51 update(i,1); 52 while(!q.empty()&&q.top().first<j){ 53 update(q.top().second,-1); 54 q.pop(); 55 } 56 ans+=getans(i)-getans(i-d[i][j][0]); 57 } 58 } 59 printf("Case %d: %I64d\n",ca,ans); 60 61 62 } 63 return 0; 64 }