http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&cid=832

Problem Description

In the world line 1.048596%

在反覆上演的梦境中，两年前的梓川咲太坐在通往沙滩的阶梯，心不在焉地看着七里滨的海。

这也一定是梦，接下来的进展他早已知晓。翔子小姐就要来了。

“咲太小弟今天的心情也处于低潮呢。”，翔子踩着轻快脚步现身，坐在咲太身旁。

“翔子小姐今天也有点烦人呢。”

“即使每天来到海边也没有治愈荒废的心吗？我来告诉你摆脱无聊的方法。我从一个朋友那边听来的。”出乎意料的，翔子小姐站了起来。

“难道是数质数吗？别开玩...”，梓川咲太的话没说完，就被翔子小姐拉到海边，然后一起捡贝壳。

捧满贝壳的梓川咲太，又被拉着用脚在沙滩上踩出圆环的形状。

然后翔子小姐又把贝壳随意的放在圆环上。

做完这一切后，翔子小姐又拉着咲太小弟站到了防波堤上面。

“那么咲太小弟，你知道这些贝壳里面能形成多少个不重复的矩形吗？”

“两个矩形不相同当且仅当选取的四个贝壳的位置不同哦。”

咲太小弟不过是普通的初中生，也许这个问题只有翔子小姐才知道如何解答。

“不要觉得自己不会哦，这无关能力的事情。”翔子小姐温柔的说。

“我的朋友这样说过，许多失败了的未来，无法挽回的过去，但是肯定在这之后，会有连接到......”

......

咲太任凭情感漩涡驱使而想要转身，但是做不到。

梦醒了。

 

 

Input

多组输入输出

对于每组样例，第一行一个正整数n（n<=300），代表圆环上有多少个贝壳。

接下来n行分别为这n个贝壳所分割的各个圆弧的长度s(1<=s<=15)。

输入保证：

1：每组样例给出的圆弧的长度按顺时针的顺序给出。

2：所有样例输入的n的和不超过500

 

 

Output

对于每组样例，输出一个整数，代表能形成不同矩形的个数

 

 

Sample Input


 

8 1 2 2 3 1 1 3 3

 

 

Sample Output


 

3

Hint

样例的图如下


 

C++版本一

数一下直径就行了

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG

using namespace std;
typedef long long ll;
const int N=10000;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m;
int a[N],b[N];
bool BS(int x){
    int l=0;
    int r=n;
    int mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(b[mid]==x)   return 1;
        else if(b[mid]<x)   l=mid+1;
        else r=mid-1;
    }
    return 0;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    while(~scanf("%d",&n)){
        int sum=0;
        a[0]=0;
        b[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum+=a[i];
            b[i]=sum;
        }
        int ans=0;
        if(sum%2){
            cout << ans << endl;
            continue;
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
                if(BS((b[i]+sum/2)%sum))
                    cnt++;
        }
        ans=cnt*(cnt-1)/2-cnt/2;
        cout << ans/4 << endl;
    }
  //  cout << "Hello world!" << endl;
    return 0;
}

 

C++版本二

https://www.cnblogs.com/MingSD/p/10050324.html

如果是矩形的话，那么一定是在直径上，然后找到一个直径，然后就枚举可能存在的矩形，如果存在矩形，则弧长相等。

#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL mod =  (int)1e9+7;
const int N = 305;
int a[N];
int n;
int L = 0;
inline int cal(int x, int y){
    if(x > n) x -= n;
    if(y > n) y -= n;
    if(x > y) swap(x, y);
    return min(a[y]-a[x], a[x]+L-a[y]);
}
int main(){
    while(~scanf("%d", &n)){
        for(int i = 2; i <= n; ++i){
            scanf("%d", &a[i]);
            a[i] += a[i-1];
        }
        scanf("%d", &L);
        L += a[n];
        int ans = 0;
        if(L&1) {
            printf("0\n");
            continue;
        }
        for(int i = 1; i <= n; ++i){
            for(int j = i+1; j <= n; ++j){
                if(cal(i,j) != L/2) continue;
                for(int k = i+1; k < j; ++k){
                    for(int z = j+1; z < i+n; ++z){
                        int t1 = cal(i,k), t2 = cal(j,z);
                        if(t1 == t2) ans++;
                        else if(t1 < t2) break;
                    }
                }
            }
        }
        cout << ans/2 << endl;
    }
    return 0;
}