「BZOJ1800」[AHOI2009]fly 飞行棋

Description

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

Input

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

Output

所构成不重复矩形的个数

Sample Input

1
2
3
4
5
6
7
8
9
8
1
2
2
3
1
1
3
3

Sample Output

1
3

HINT

n20n\leq 20

Solution

两个点的连线为直径,当他们直接的弧长为圆周长的一半。
假设有nn个直径,答案就是Cn2C_n^2
然而我太菜只能暴力枚举直径,最后答案除以22.刷水题找安慰。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 70;
int n;
ll a[N], sum;

int main() {
n = read();
for(int i = 1; i <= n; ++i) {
cin>>a[i];
sum += a[i];
}
for(int i = 1; i <= n; ++i) a[i + n] = a[i];
ll ans = 0;
for(int i = 1; i <= n; ++i) {
ll tmp = 0;
int j = i;
while(j < n && tmp * 2 < sum) tmp+=a[j],++j;
if(tmp * 2 != sum) continue;
ll s1 = 0;
for(int x = i; x < j-1; ++x) {
s1 += a[x];
ll s2 = 0;
int y = j;
while(y < n + i - 1 && s2 < s1) s2 += a[y], ++y;
ans += s2 == s1;
}
}
writeln(ans/2);
return 0;
}