hdu 4099 Revenge of Fibonacci (字典樹)

題目大意：

問前綴為給出的 串的斐波那契數列的最小下標，斐波那契最多給出前40個。

思路：
我們保存斐波那契的前50 個。

然後在高精度加的時候損失的精度也不會影響結果。

然後插入的時候只插入前40個 多了就不插

#include 
#include 
#include 
#include 

using namespace std;

struct foo
{
    int save[51];
    void init()
    {
        memset(save,0,sizeof save);
    }
    int get()
    {
        int pos=50;
        while(save[pos]==0)pos--;

        return pos;
    }
}s[3];

foo add(foo a,foo b)
{
    foo res;
    res.init();
    for(int i=0;i<50;i++)
    {
        res.save[i]=a.save[i]+b.save[i]+res.save[i];
        if(res.save[i]>=10)
        {
            res.save[i]%=10;
            res.save[i+1]++;
        }
    }
    return res;
}
struct node
{
    struct node *br[10];
    int num;
};

node *root;

void Trie_init()
{
    root=new node;
    root->num=0;
    for(int i=0;i<10;i++)root->br[i]=NULL;
}
void Trie_insert(foo str,int pos,int mak)
{
    node *s=root;
    int i,ct;
    for(i=pos,ct=0;i>=0 && ct<41;i--,ct++)//ct<=41 MLT 出翔  就卡的這麼好  你敢信？
    {
        int id=str.save[i];
        if(s->br[id]==NULL)
        {
            node *t=new node;
            for(int j=0;j<10;j++)t->br[j]=NULL;
            t->num=mak;
            s->br[id]=t;
            s=s->br[id];
        }
        else {
            s=s->br[id];
        }
    }
}

int Trie_find(char str[])
{
    int len=strlen(str);

    node *s;
    s=root;
    int res;

    for(int i=0;ibr[id]==NULL)return -1;
        else
        {
            s=s->br[id];
            res=s->num;
            //printf("%d ",res);
        }
    }
    return res;
}

void Trie_del(node *p)
{
    for(int i=0;i<10;i++)
    {
        if(p->br[i]!=NULL)
          Trie_del(p->br[i]);
    }
    free(p);
}

void move(foo &t)
{
    int pos=t.get();
    for(int i=1;i<=pos;i++)
    {
        t.save[i-1]=t.save[i];
    }
    t.save[pos]=0;
}

int main()
{
    Trie_init();

    s[0].init();
    s[1].init();

    s[0].save[0]=1;
    s[1].save[0]=1;

    Trie_insert(s[0],0,1);
    //cout<<"---"<