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;
}