「BZOJ1800」[Ahoi2009] fly 飞行棋

2014年5月8日3,2960

Description

给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。

Input

第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度

Output

所构成不重复矩形的个数

Sample Input

8
1
2
2
3
1
1
3
3

Sample Output

HINT

N<= 20

题解

20的数据范围直接使其变成水题

#include<iostream>
#include<cstdio>
using namespace std;
int n,ans,tot;
int a[21],dis[21];
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	    a[i]=read();
	for(int i=1;i<=n;i++)
	{
	    dis[i+1]=dis[i]+a[i];
	    tot+=a[i];
	}
	for(int a=1;a<=n;a++)
	for(int b=a+1;b<=n;b++)
	for(int c=b+1;c<=n;c++)
	for(int d=c+1;d<=n;d++)
	    if((dis[b]-dis[a]==dis[d]-dis[c])&&(tot-dis[d]+dis[a]==dis[c]-dis[b]))
	        ans++;
	printf("%d",ans);
	return 0;
}

#include<iostream>

#include<cstdio>

using namespace std;

int n,ans,tot;

int a[21],dis[21];

inline int read()

{

char ch=getchar();

int f=1,x=0;

while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}

return x*f;

}

int main()

{

n=read();

for(int i=1;i<=n;i++)

a[i]=read();

for(int i=1;i<=n;i++)

{

dis[i+1]=dis[i]+a[i];

tot+=a[i];

}

for(int a=1;a<=n;a++)

for(int b=a+1;b<=n;b++)

for(int c=b+1;c<=n;c++)

for(int d=c+1;d<=n;d++)

if((dis[b]-dis[a]==dis[d]-dis[c])&&(tot-dis[d]+dis[a]==dis[c]-dis[b]))

ans++;

printf("%d",ans);

return 0;

}

« 「CF427A」Police Recruits 「NOIP模拟赛」机器人 »

hzwer.com _ Home | http://hzwer.com

「BZOJ1800」[Ahoi2009] fly 飞行棋

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论