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;i
      
       br[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<<"---"<