hdu 4099 Revenge of Fibonacci 字典树+大数 - c++编程基础

将斐波那契的前100000个，每个的前40位都插入到字典树里（其他位数删掉），然后直接查询字典树就行。

此题坑点在于

1、字典树的深度不能太大，事实上，超过40在hdu就会MLE……

2、若大数加法时，保存的位数过少，就会导致低位误差，累积起来就可能导致前40位产生错误，解决办法是提高精度。

#include  
#include  
#include  
#include  
using namespace std;  
  
struct Trie  
{  
    struct Trie *son[10];  
    int id;  
}*root;  
void insert(char s[],int ID)  
{  
    int i,j;  
    struct Trie *c,*newnode;  
    c=root;  
    for(i=0;s[i];i++)  
    {  
        if(c->son[s[i]-'0'])  
        {  
            c=c->son[s[i]-'0'];  
        }  
        else  
        {  
            c->son[s[i]-'0']=new Trie;  
            for(j=0;j<10;j++)    c->son[s[i]-'0']->son[j]=0;  
            c=c->son[s[i]-'0'];  
            c->id=ID;  
        }  
    }  
}  
int find(char *s)  
{  
    int i;  
    int len;  
    struct Trie *c;  
    len=strlen(s);  
    if(len==0)    return 0;  
    c=root;  
    for(i=0;ison[s[i]-'0']!=0)  
        {  
            c=c->son[s[i]-'0'];  
        }  
        else  
            return -1;  
    }  
    return c->id;  
}  
void init()  
{  
    root=new Trie;  
    for(int i=0;i<10;i++)    root->




son[i]=0;  
}  
char a[60]="1",b[60]="1",c[60];  
int main()  
{  
    char str[50];  
    int cas;  
    int ca=1;  
    init();  
    insert("1",0);  
    int la=1;  
    int lb=1;  
    for(int i=2;i<100000;i++)  
    {  
        int len=max(la,lb);  
        int x=0;  
        int top=0;  
        for(int j=0;j=la) a[j]='0';  
            int s=x+a[j]+b[j]-2*'0';  
            x=s/10;  
            c[top++]=s%10+'0';  
        }  
        if(x) c[top++]=x+'0';  
        c[top]='\0';  
        if(top>50)              //计算数列的精度必须大一些  
        {  
            for(int j=0;j<49;j++) a[j]=b[j+1];a[la=49]='\0';  
            for(int j=0;j<50;j++) b[j]=c[j+1];  
            b[lb=50]='\0';  
        }  
        else  
        {  
            la=lb;  
            strcpy(a,b);  
            strcpy(b,c);  
            lb=top;  
        }  
        int j,c;  
        for(j=lb-1,c=0;j>=0&&c<40;c++,j--) str[c]=b[j];str[c]='\0';//字典树的深度绝对不能太大，超过40就要MLE！  
        insert(str,i);  
    }  
  //  cout<<"ok"<>cas;  
    while(cas--)  
    {  
        scanf("%s",str);  
        printf("Case #%d: %d\n",ca++,find(str));  
    }  
    return 0;  
}