题意:给你一个n*n的0 1 矩阵,要求满足边上都是1的正方形矩阵的个数
分析:先DP求出每个点能到达的四个方向的最长距离,然后就是枚举每一条对角线进行统计,统计的时候必须用线段树什么的,然后比赛的时候一直都想不出怎样来统计,想了个错误的做法,看了题解才想明白,估计是太久没写线段树了(貌似暴力统计就过了,肿么能这样呢= =)
代码:
#include
#include
#include
#include
#define lson l,m,rt<
#define rson m+1,r,rt
using namespace std;
const int mm=1111;
struct data
{
int p,x;
}g[mm*2];
int a[mm][mm],s[mm][mm],t[mm][mm],r[mm][mm],c[mm][mm];
int sum[mm
void build(int n)
{
memset(sum,0,sizeof(int)*(n
}
void update(int x,int l,int r,int rt)
{
++sum[rt];
if(l==r)return;
int m=(l+r)>>1;
if(x<=m)update(x,lson);
else update(x,rson);
}
int query(int x,int l,int r,int rt)
{
if(l==r)return sum[rt];
int m=(l+r)>>1,ret=0;
if(x<=m)ret+=query(x,lson)+sum[rt<
else if(x>m)ret+=query(x,rson);
return ret;
}
bool cmp(data a,data b)
{
return a.p
}
int solve(int i0,int j0,int n)
{
int i,j,e=0,k,m=0,ret=0;
for(k=1,i=i0,j=j0;k
if(a[i][j])
{
g[m].p=k-t[i][j],g[m++].x=-k;
g[m].p=k,g[m++].x=k;
}
sort(g,g+m,cmp);
build(n);
for(k=1,i=i0,j=j0;k
{
if(a[i][j])update(k+s[i][j]-1,1,n,1);
while(e
{
if(g[e].p==k)
{
if(g[e].x
else ret+=query(g[e].x,1,n,1);
}
++e;
}
}
return ret;
}
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
int i,j,k,n,T,ans,cs=0;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=1;i
for(j=1;j
scanf("%d",&a[i][j]);
memset(r,0,sizeof(r));
memset(c,0,sizeof(c));
for(i=1;i
for(j=1;j
if(a[i][j])
{
r[i][j]=r[i-1][j]+1;
c[i][j]=c[i][j-1]+1;
t[i][j]=min(r[i][j],c[i][j]);
}
memset(r,0,sizeof(r));
memset(c,0,sizeof(c));
for(i=n;i>0;--i)
for(j=n;j>0;--j)
if(a[i][j])
{
r[i][j]=r[i+1][j]+1;
c[i][j]=c[i][j+1]+1;
s[i][j]=min(r[i][j],c[i][j]);
}
ans=0;
for(i=n;i>1;--i)
ans+=solve(i,1,n-i+1);
for(j=1;j<=n;++j)
ans+=solve(1,j,n-j+1);
printf("Case %d: %d\n",++cs,ans);
}
return 0;
}