欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

SSL P1861 无限序列

程序员文章站 2024-03-19 08:24:34
...

目录:

题目:

无限序列题目

题意:

给出一个原序列:1。求在若干次变化后,a~b中有多少个1。

分析:

刚开始,看到给出的序列变化就觉得有些头大,因为好像是无规律可循的。但我们不妨换个思维,不看这整个序列的变化不以其的形态来记录,而是以1的个数和总长度来记录。顿时感觉山重水复疑无路,柳暗花明又一村了——因为这两者的变化是按照斐波那契数列这下就非常好办了,因为题目给我们的范围是2的63次方,所以我们就只需要求出前92个斐波那契数,而这又刚好在unsigned long long的范围内。
而对于求a~b之间的1的个数,我们可以用整体-部分,即用1~b的1的个数,减去1~a-1的1的个数,那么就是正解啦。
但是a、b不一定是个斐波那契数,所以我们可以不断的用与其最接近的斐波那契数去计算,算完后再减去这个斐波那契数,以此类推,直到ta等于0。

AC后感想:

其实这道题目还是挺简单的虽然我们也没有对,关键在于我们要找到怎么去巧算。

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
inline unsigned long long read()//一定要用unsigned long long 
{
    unsigned long long a=0,f=1;char s=getchar();
    while(s<'0'||s>'9') {if(s=='-') f=-1;s=getchar();}
    while(s>='0'&&s<='9') {a=a*10+s-'0';s=getchar();}
    return a*f;
}
using namespace std;
unsigned long long max(unsigned long long x,unsigned long long y)
{
    return x>y? x:y;
}
unsigned long long c[101],g[101];
int main()
{
/*  freopen("infinit.in","r",stdin);
    freopen("infinit.out","w",stdout);*/
    unsigned long long n,a[50001],b[50001],maxb;
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),b[i]=read();
    c[1]=1;g[1]=1;//斐波那契初始化 
    c[2]=2;g[2]=1;
    int s=2;
    while(s<92)//只需要计算到第92个 
    {
        s++;
        c[s]=c[s-1]+c[s-2];
        g[s]=g[s-1]+g[s-2]; 
    }
    for(int i=1;i<=n;i++)
    {
        unsigned long long ans1=0,ans2=0;
        while(b[i])//求1~b[i]中1的个数 
        {
            int j=1;
            while(c[j]<=b[i]) j++;
            j--;
            ans1+=g[j];
            b[i]-=c[j];
        }
        a[i]--;
        while(a[i])//求1~a[i]-1中1的个数 
        {
            int j=1;
            while(c[j]<=a[i]) j++;
            j--;
            ans2+=g[j];
            a[i]-=c[j];
        }
        cout<<ans1-ans2<<endl;//总体减部分,求出正解 
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}