首页 > 代码库 > BZOJ 1800

BZOJ 1800

2024-09-22 09:14:48   215人阅读

1800: [Ahoi2009]fly 飞行棋

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1622  Solved: 1293
[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
技术分享

 

 

这个题需要有初中数学的基础，因为圆的内接矩形，他的对角线是直径，所以，就要找出直径的条数，然后将直径两两组合，每两条不同的直径可以组成一个矩形，这里用到组合数，

答案就是C(2,直径条数)

如何求直径条数呢

就是将若干条连续弧相加，使等于圆周长一半就是直径，弧的端点就是直径的端点

我们有一种比较慢的方法求直径条数，复杂度n^2

for(int i=1;i<n;++i)    for(int j=1;j<n;++j)        if(s[j]-s[i-1]==number)           //number是圆周长的一半，s是前缀和
　　　　　　 ans++;

其实这种方法也不是太慢，也就比快的方法慢几MS，可能是数据小吧……

 

有一种比较快的方法

和一道题思路基本一致

洛谷 P1115 最大子段和

这是代码

技术分享
#include<iostream>using namespace std;int main(){    int n;    cin>>n;    int sum=0,maxl=0;    for(int i=1;i<=n;++i)    {        int number;        cin>>number;        sum+=number;        maxl=max(sum,maxl);        if(sum<0)sum=0;    }    cout<<maxl;    return 0;}
最大子段和

我们就稍微改一改就能将上面那个比较慢的方法变成线性啦

int total=0;    int ans=0;    for(int i=1,j=1;i<n;++i)    {        total+=s[i];        while(total>number)            total-=s[j++];        if(total==number)            ans++;    }

只是一定要注意两个地方容易出错

1、循环到n-1

2、while(total>number)

     total-=s[j++];如果不用while的话，结果可以想象……不是会变慢的问题，是答案有可能不对的问题……


完整代码如下
#include<iostream>#include<cstdio>#include<cstdlib>using namespace std;int s[1000],f[10000];int n,number=0;void quit(){    printf("0");    exit(0);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;++i)    {        scanf("%d",&s[i]);        number+=s[i];        f[i]=f[i-1]+s[i];    }    if(number&1)quit();    number>>=1;    int total=0;    int ans=0;    for(int i=1,j=1;i<n;++i)    {        total+=s[i];        while(total>number)            total-=s[j++];        if(total==number)            ans++;    }    if(ans<2)quit();    printf("%d",ans*(ans-1)>>1);    return 0;}
 
这个题也是比较水的……相对于BZOJ的其他题……
 
BZOJ 1800






























        

            
                
                  
                
                

                    联系

                    我们