传送门
题面：
1800: [Ahoi2009]fly 飞行棋
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 2267 Solved: 1733
[Submit][Status][Discuss]
Description
给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。
Input
第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度
Output
所构成不重复矩形的个数
Sample Input
8
1
2
2
3
1
1
3
3
Sample Output
3
HINT
N<= 20
题目分析：
对于这个题目，我们首先需要回忆起一个初中所学过的定理：同弧所对的圆周角=圆心角的一半。
这就意味着，倘若两个不相交的弧，如果他们的长度相同，则一定有他们弧所对应的弦长相同。
由此我们可以想到一个最朴素的算法，我们枚举圆上的四个点，判断一下相对的两条边的弧长是否相同即可。两两间的弧长可以通过维护前缀和实现。此时的时间复杂度为O(n^4)。
但是这个题还是可以把复杂度继续压下来的。
考虑到题目中要我们求的是矩形，根据矩形在圆内的性质，不难发现，一个矩形是由两条相交的直径构成的。因此倘若我们知道了n个点可以构成的直径的个数，则最终的答案即为C(直径，2）。
而继续根据同弧所对的圆周角=圆心角的一半，我们知道，一段弧长为直径，当且仅当弧长为周长的一半。因此我们现在只需要枚举两个点，不断判断这两个点是否是直径即可。此时的时间复杂度为O(n^2)。
代码：
//O(n^4)
#include <bits/stdc++.h>
#define maxn 25
using namespace std;
int sum[maxn];
int a[maxn];
int main()
{
int n;
//freopen("in.txt","r",stdin);
scanf("%d",&n);
int tot=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
int res=0;
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((sum[b]-sum[a]==sum[d]-sum[c])&&(sum[n]-sum[d]+sum[a]==sum[c]-sum[b]))
res++;
}
cout<<res<<endl;
}//O(n^2)
#include <bits/stdc++.h>
#define maxn 25
using namespace std;
int sum[maxn];
int a[maxn];
int main()
{
// freopen("in.txt","r",stdin);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(sum[j]-sum[i]==sum[n]/2) cnt++;
}
}
cout<<cnt*(cnt-1)/2<<endl;
}