名为青春的悖论β

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

题解:用a[i]数组存第i个点与第一个点之间的距离,b[i]存储长度为i的点有没有贝壳(有则为1,没有为0),然后遍历半圆上(不包括第一个点正对的那个点)的点,如果满足:

1.b[a[i]+sum/2] 即加上半周长的长度也有贝壳

2.b[(a[j]+sum/2)%sum] 两个半圆上有相互对应的点

即可以说明可以构成一个矩形

PS:注意判断圆的周长是不是奇数啊!!! 这里WA了好几次。还有答案别忘了除以二啊!

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ling long
#define INF 0×3f3f3f3f  //0×7ffffff
#define EPS 1e-6
#define maxn 2000+10
#define PI acos(-1.0)
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,res,t,x,sum;
    int a[maxn],b[maxn];
    while(cin>>n)
    {
        a[0]=0;res=0;
        memset(b,0,sizeof(b));
        b[0]=1;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a[i]+=a[i-1];
            b[a[i]]=1;
        }
        sum=a[n];  //圆的周长
        if(sum%2) {cout<<'0'<<endl;continue;} //此处为坑,不判断奇数会WA
        for(int i=0;a[i]<sum/2;i++)
        {
            if(b[a[i]+sum/2])
            {
                for(int j=i+1;a[j]<a[i]+sum/2;j++)
                {
                    if(b[(a[j]+sum/2)%sum])
                        res++;
                }
            }
            else continue;
        }
        cout<<res/2<<endl;
    }
    return 0;
}

 

发表评论,支持MarkDown语法