首页 > 代码库 > BZOJ1800 [Ahoi2009]fly 飞行棋

BZOJ1800 [Ahoi2009]fly 飞行棋

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

 

 

 

本文作者:ljh2000  

作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

 

 

Description

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

Input

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

Output

所构成不重复矩形的个数

Sample Input

8
1
2
2
3
1
1
3
3


Sample Output

3

HINT

N<= 20
技术分享

 
 
正解:组合数学
解题报告:
  显然矩形的对角线一定是直径,找出所有直径,假设有x条,答案就是$C^{2}_{x}$。
 
 
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN = 45;
int n,a[MAXN],tot,sum,ans;
inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
    if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}

inline void work(){
	n=getint(); for(int i=1;i<=n;i++) a[i]=getint(),sum+=a[i];
	if(sum&1){ printf("0"); return ; } sum>>=1;
	for(int i=1,j=1;i<n;i++) {	tot+=a[i];	while(tot>sum) tot-=a[j++]; if(tot==sum) ans++; }
	printf("%d",ans*(ans-1)/2);
}

int main()
{
    work();
    return 0;
}

  

BZOJ1800 [Ahoi2009]fly 飞行棋