HDU1316(求区间斐波那契数的个数)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1316

题意：给两个数a和b，其中它们可能很大，最大到10^100，然后求区间[a,b]内有多少个fib数。

分析：这个题呢，看数据肯定是要当字符串处理的，那么对于本题我的思路就是先把fib数长度小于等于100的预处理出来。

然后呢，就与a和b比较，分别找出刚好大于等于a的fib数的下标和刚好小于等于b的fib数下标，假设分别是record1和

record2，那么record2-record1+1就是答案了。

估计了一下，由于在1000以内的fib数的长度就超过了100，所以预处理到1000个fib数就行了。

#include <iostream>#include <string.h>#include <stdio.h>using namespace std;const int N=1005;int fib[N][105];int f[N][105];int h[N];void Solve(){    memset(fib,0,sizeof(fib));    h[0]=0;h[1]=0;    fib[0][0]=1;fib[1][0]=1;    for(int i=2;i<N;i++)    {        for(int j=0;j<105;j++)        {            fib[i][j]+=fib[i-1][j]+fib[i-2][j];            if(fib[i][j]>=10)            {                fib[i][j]-=10;                fib[i][j+1]++;            }        }        for(int j=104;j>=0;j--)        {            if(fib[i][j])            {                h[i]=j;                break;            }        }    }}bool compare1(char *str,int len,int a[],int n){    if(n<len) return true;    if(n>len) return false;    for(int i=0;i<n;i++)    {        if(str[i]-'0'>a[i]) return true;        if(str[i]-'0'<a[i]) return false;    }    return true;}bool compare2(char *str,int len,int a[],int n){    if(n>len) return true;    if(n<len) return false;    for(int i=0;i<n;i++)    {        if(str[i]-'0'<a[i]) return true;        if(str[i]-'0'>a[i]) return false;    }    return true;}char a[105],b[105];int main(){    Solve();    for(int i=0;i<N;i++)        for(int j=h[i];j>=0;j--)            f[i][h[i]-j]=fib[i][j];    int record1,record2;    while(cin>>a>>b)    {        int len1=strlen(a);        int len2=strlen(b);        if(len1==1&&len2==1&&a[0]=='0'&&b[0]=='0') break;        for(int i=1;i<N;i++)        {            if(compare2(a,len1,f[i],h[i]+1))            {                record1=i;                break;            }        }        for(int i=N-1;i>=1;i--)        {            if(compare1(b,len2,f[i],h[i]+1))            {                record2=i;                break;            }        }        cout<<record2-record1+1<<endl;    }    return 0;}

Re: ACdreamers昨天 18:25

回复u011757662n非常感谢！