bzoj 1800: [Ahoi2009]fly 飞行棋
Contents
1800: [Ahoi2009]fly 飞行棋
Description
给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。
Input
第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度
Output
所构成不重复矩形的个数
Sample Input
8
1
2
2
3
1
1
3
3
1
2
2
3
1
1
3
3
Sample Output
3
HINT
N<= 20
Source
#include<cstdio>
#define F(i,l,r) for(int i=l;i<=r;i++)
int n,w[22],ans;
int main()
{
scanf("%d",&n);
w[0]=0;
F(i,1,n){
scanf("%d",&w[i]);
w[i]+=w[i-1];
}
if(w[n]&1){printf("0");return 0;}
F(i,1,n) F(j,i+1,n) if(w[j]-w[i]==w[n]>>1) ans++;
printf("%d\n",ans*(ans-1)>>1);
return 0;
}
发表评论