hdu4099 Revenge of Fibonacci 字典树

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

思想很容易想到

就是预处理出前10w个的fib数，然后建树查询

建树时只用前40位即可，所以在计算时只用截取前60位

但是我在截取时总是出错

后来看了别人的代码改了一下就对了

不过还是不知道为什么那样是对的

更改地方在代码：

  1 #include<iostream>
  2 #include<cstdlib>
  3 #include<cstdio>
  4 #include<cstring>
  5 #define maxn 110
  6 using namespace std;
  7 char  s[60];
  8 char c[100];
  9 char s1[maxn],s2[maxn],s3[maxn];
 10 void add(char *s1,char *s2, char *s3)//大数加
 11 {
 12     int len1=strlen(s1)-1;
 13     int len2=strlen(s2)-1;
 14     int up=0;
 15     int x=0,y=0;
 16     int k=0;
 17     int z=0;
 18     while(len1>=0 || len2>=0)
 19     {
 20         if(len1<0) x=0;
 21         else x=s1[len1]-'0';
 22         if(len2<0) y=0;
 23         else y=s2[len2]-'0';
 24 
 25         z=x+y+up;
 26 
 27         c[k++]=z%10+'0';
 28         up=z/10;
 29         len1--;
 30         len2--;
 31     } 
 32 
 33     if(up>0) c[k++]=up+'0';
 34     for(int i=0;i<k;i++)
 35     s3[i]=c[k-1-i];
 36     s3[k]='';
 37 }
 38 class node
 39 {
 40    public:
 41      int ID;
 42      node *next[10];
 43      
 44 };
 45 node *root=new node;
 46 void insert_node(char *s, int num)
 47 {
 48    node *p=root;
 49 
 50   for(int i=0;s[i]&&i<41;i++)
 51   {
 52      if(p->next[s[i]-'0']==NULL)
 53      {
 54        node *temp=new node;
 55        for(int j=0;j<10;j++)
 56             temp->next[j]=NULL;
 57             temp->ID=-1;
 58        p->next[s[i]-'0']=temp;
 59 
 60      }
 61     p=p->next[s[i]-'0'];
 62 
 63     if(p->ID<0) p->ID=num;
 64   }
 65 }
 66 void init()
 67 {
 68    node *q=root;
 69    for(int i=0;i<10;i++)
 70       q->next[i]=NULL;
 71       q->ID=-1;
 72    
 73    s1[0]='1';s1[1]='';
 74    s2[0]='1';s2[1]='';
 75 
 76    insert_node(s1,0);
 77    insert_node(s2,1);
 78 
 79 
 80   for(int i=2;i<100000;i++)
 81   {
 82      int len1=strlen(s1);
 83      int len2=strlen(s2);
 84      if(len2>60) // 防止进位出错，但是不知道为什么这样就可以防止了。。。。。
 85      {
 86         s2[len2-1]='';
 87         s1[len1-1]='';
 88      }
 89 
 90      //我自己曾经的方法
 91      /*
 92         if(len2>60) s2[len2-1]='';
 93         if(len1>60) s1[len1-1]='';
 94  
 95      */
 96 
 97      add(s1,s2,s3);
 98      insert_node(s3,i);
 99 
100      strcpy(s1,s2);
101      strcpy(s2,s3);
102 
103   }
104 }
105 int find(char *s)
106 {
107   node* q=root;
108   int num;
109   int len=strlen(s);
110   for(int i=0;i<len;i++)
111   {
112       int d=s[i]-'0';
113 
114       if(q->next[d]==NULL) return -1;
115      else
116      {
117        q=q->next[d];
118        num=q->ID;
119     }
120   }
121    return num;
122 }
123 void del_node(node *p)
124 {
125       for(int i=0;i<10;i++)
126       {
127            if(p->next[i]!=NULL)
128                    del_node(p->next[i]);
129 
130       }
131       free(p);
132 
133 }
134 int main()
135 {
136    int t;
137    init();
138 
139    scanf("%d",&t);
140    int iCase=0;
141    while(t--)
142    {
143       
144       scanf("%s",s);
145      printf("Case #%d: %d
",++iCase,find(s)); 
146    }
147    del_node(root);
148    return 0;
149 }