Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 376 Solved: 256
Description
大三角形的所有短边可以看成由(n+1)*n/2个单位三角形的边界组成。如下图的灰色三角形所示。其中第1排有1个灰色三角形，第2排有2个灰色三角形，……，第n排有n个灰色三角形。所以输入格式是这样规定的：输入第一行为正整数n，其中1<=n<=1000，表示大三角形每边的长度。接下来的n行，第i+1行有i组数，从左到右每组数描述一个三角形，每组数都有3个数，这3个数非0即1，表示对应的短边是否被删除，0表示已被删除，1表示未被删除，依次按照三角形的左、右、下边的顺序来描述。所以第i+1行有3i个数，每个数是0或1 
仅包含一个整数T，表示有多少个三角形的边界都没有被删除。
Sample Input5
1 1 1
1 1 0 1 1 0
1 1 1 1 1 1 1 0 1
1 0 1 1 1 1 0 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1 1 1 0 1 1
19
/**************************************************************
Problem: 1201
User: ictsing
Language: C++
Result: Accepted
Time:2716 ms
Memory:13136 kb
****************************************************************/
//1201: [HNOI2005]数三角形
/*
就是叫你数三角形，
枚举三角形的底边，
然后前缀和检查一下
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int mt=1000+5;
struct line
{
int d[mt],n;
void add(int x,int v)
{
d[x]+=v;
}
void gets()
{
for(int i=2;i<=n;i++)
d[i]+=d[i-1];
}
bool check(int l,int r)
{
return d[r]-d[l-1]==r-l+1;
}
}d1[mt],d2[mt];
int c[mt][mt];
bool check1(int i,int l,int r)
{
int len=r-l+1;
return d1[l].check(i-l+1-len+1,i-l+1)&&d2[i-r+1].check(r-len+1,r);
}
bool check2(int i,int l,int r)
{
int len=r-l+1;
return d2[i-l+2].check(l,l+len-1)&&d1[r+1].check(i-r+1,i-r+1+len-1);
}
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
int main()
{
int n=read();
int ans=0;
for(int i=1;i<=n;i++)
d1[i].n=d2[i].n=n-i+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
{
int x=read(),y=read(),z=read();
if(x) d1[j].add(i-j+1,1);
if(y) d2[i-j+1].add(j,1);
c[i][j]=z;
}
for(int i=1;i<=n;i++)
d1[i].gets(),d2[i].gets();
for(int i=1;i<=n;i++)
{
int l=1,r=0;
for(int j=1;j<=i;j++)
{
int z=c[i][j];
if(z) r++;
else l=j+1,r=j;
for(int k=l;k<=r;k++)
{
ans+=check1(i,k,r);
if(r-k+1<=n-i)
ans+=check2(i,k,r);
}
}
}
printf("%d\n",ans);
return 0;
}
评论