1800: [Ahoi2009]fly 飞行棋

1800: [Ahoi2009]fly 飞行棋

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1831  Solved: 1440
[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

#include <bits/stdc++.h>

#define MAXN 25

using namespace std;

int n;
int a[MAXN];//a[i]表示第i个点到第i-1个点的弧长
int res;
int tol;

inline void init(){
    res=0;
    tol=0;
}

int main(){
    // freopen("in.txt","r",stdin);
    init();
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        tol+=a[i];
    }
    for(int i=0;i<n;i++){//枚举那个点作为顶点
        int pos=0;//这条边的长度
        for(int j=i+1;j<i+n-1;j++){//枚举那个点作为终点
            pos+=a[j%n];
            if(tol-pos*2<=0)//这个边长到极限了
                break;
            else if((tol-pos*2)%2!=0)//不能均分肯定比不能组成矩形
                continue;
            bool flag=false;
            int cnt=(tol-pos*2)/2;
            int s=0;
            int r=(j+1)%n;

            while(true){
                s+=a[r%n];
                if(s==cnt){
                    flag=true;
                    break;
                }else if(s>cnt){
                    break;
                }
                r++;
            }
            if(flag==false){
                continue;
            }else{
                s=0;
                flag=false;
            }
            int l=i;
            while(true){
                if(l<0){
                    l=n-1;
                }
                s+=a[l];
                if(s==cnt){
                    flag=true;
                    break;
                }else if(s>cnt){
                    break;
                }
                l--;
            }
            if(flag==false)
                continue;
            else{
                res++;
            }
        }
    }
    printf("%d
",res/4);
    return 0;
}