梳理了一下字典序：

hdu1251裸 字典树

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 struct trie{ 6     int cnt; 7     trie *next[26]; 8 }; 9 trie *root=new trie;10 void insert(char s[]){11     trie *p=root,*newnode;12     for(int i=0;s[i]!='\0';i++){13         if(p->next[s[i]-'a']!=NULL){14             p=p->next[s[i]-'a'];15             p->cnt++;16         }else{17             newnode=new trie;18             for(int j=0;j!=26;j++)19                 newnode->next[j]=NULL;20             newnode->cnt=1;21             p->next[s[i]-'a']=newnode;22             p=newnode;23         }24     }25 }26 int find(char s[]){27     trie *p=root;28     for(int i=0;s[i]!='\0';i++){29         if(p->next[s[i]-'a']!=NULL)30             p=p->next[s[i]-'a'];31         else32             return 0;33     }34     return p->cnt;35 }36 int main(){37     char s[20];38     for(int i=0;i!=26;i++)39         root->next[i]=NULL;40     root->cnt=0;41     while(gets(s)){42         if(!strcmp(s,"")) break;43         insert(s);44     }45     while(scanf("%s",s)!=EOF){46         printf("%d\n",find(s));47     }48     return 0;49 }50 /*51 Sample Input52 banana53 band54 bee55 absolute56 acm57 58 ba59 b60 band61 abc62 Sample Output63 264 365 166 067 */
        
       
      

hdu1247 字典树变形，题意：输入n个字符串，如果存在字符串a,b,c，满足c=a+b，输出c

将所有字符串建树或者map存储，然后遍历一遍，将每个字符串拆成两部分，分别查找看是否存在，存在输出该字符串~

map代码：280ms+

1 #include
      
        2 #include
       
         3 #include
        
       
      

字典树的代码，一开始写的很挫，map还280ms，字典树却250ms，后来参考了一下别人的，31ms~

1 //字典树做法就是用字典树来代替map判断字符串是否在词典中存在。 2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 struct Trie{ 7        void init(){ 8             memset(child,0,sizeof(child)); 9             end=false;10        }11        Trie *child[26];12        bool end;//用来判断这个点是不是一个单词的最后一个点13 }trie[50005];14 int cnt;15 char str[50005][21];16 void insert(const char *source){17      Trie *current=&trie[0]; //根节点18      for(int i=0;source[i];i++){19          if(current->child[source[i]-'a'])20               current=current->child[source[i]-'a'];21          else{22               current->child[source[i]-'a']=&trie[++cnt];23               trie[cnt].init();24               current=current->child[source[i]-'a'];25          }26      }27      current->end=true;28 }29 int find(const char *source){30     Trie *current=&trie[0];31     for(int i=0;source[i];i++){32         if(current->child[source[i]-'a'])33              current=current->child[source[i]-'a'];34         else35              return 0;36     }37     if(current->end)38         return 1;39     else40         return 0;41 }42 int main(){43     int str_cnt=0;44     cnt=0;45     trie[0].init();46     while(scanf("%s",str[str_cnt])==1){47          insert(str[str_cnt]);48          str_cnt++;49     }50     int f;51     char ch;52     for(int i=0;i
        
       
      

hdu4099 暴力计算0~10 0000 的Fibonacci前60位（插入字典树只需插入前40位），建树，没输入一个字符串查询~

代码写的很挫很挫很挫很挫~~用java大数打好数据，调试了好几个小时~~还好1A了~~

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5 #define M 100000  6 char f[M+5][70]={
    "1","1",};  7 //add函数，大数模板，计算斐波那契数  8 void add(char *a,char *b,char *c){  9     int i; 10     int c1[105]; 11     memset(c1,0,sizeof(c1)); 12     int l1=strlen(a); 13     int l2=strlen(b); 14     int top=0; 15     for(i=1;i<=l1&&i<=l2;i++) 16         c1[top++]=a[l1-i]+b[l2-i]-'0'*2; 17     while(i<=l1){ 18         c1[top++]=a[l1-i]-'0'; 19         i++; 20     } 21     while(i<=l2){ 22         c1[top++]=b[l2-i]-'0'; 23         i++; 24     } 25     int t=0; 26     for(i=0;i
         
          =0;i--){ 33         if(c1[i]!=0||flag){ 34             flag=1; 35             c[begin++]=c1[i]+'0'; 36         } 37     } 38     c[begin]='\0'; 39     return ; 40 } 41 struct trie{ 42     int cnt;//标记位置 43     trie *next[10]; 44 }; 45 //建树 46 trie *root=new trie; 47 void insert(char *ch,int index){ 48     trie *p=root,*newnode; 49     int len=strlen(ch); 50     for(int i=0;i
          
           next[ch[i]-'0']==NULL){ 52             newnode=new trie; 53             for(int j=0;j!=10;j++){ 54                 newnode->next[j]=NULL; 55             } 56             p->next[ch[i]-'0']=newnode; 57             p=newnode; 58             p->cnt=index; 59         }else{ 60             p=p->next[ch[i]-'0']; 61             if(p->cnt==-1){ 62                 p->cnt=index; 63             } 64         } 65     } 66     return ; 67 } 68 //查找函数 69 int find(char *ch){ 70     trie *p=root; 71     for(int i=0;ch[i]!='\0';i++){ 72         if(p->next[ch[i]-'0']!=NULL) 73             p=p->next[ch[i]-'0']; 74         else 75             return -1; 76     } 77     return p->cnt; 78 } 79 int main(){ 80     char ch[50]; 81     for(int i=0;i!=10;i++){ 82         root->next[i]=NULL; 83     } 84     root->cnt=-1; 85  86     ch[0]='1'; 87     ch[1]='\0'; 88     insert(ch,0); 89  90     for(int i=2;i
           
            60){ //如果大于60位，就减少一位103 f[i][60]='\0';104 int f1_len=strlen(f[i-1]);105 f[i-1][f1_len-(f_len-60)]='\0';106 }107 }108 int T=0,t;109 scanf("%d",&t);110 while(t--){111 scanf("%s",ch);112 printf("Case #%d: %d\n",++T,find(ch));113 }114 return 0;115 }
           
          
         
        
       
      

以上这个搓搓的代码在自己学校OJ上就MLE了，下面这个可以AC~

二分法。大概思路：先将一个数组串数组in将输入的所有测试数据存起来，sort一下，然后开始计算Fibonacci数列，

每计算一次，就用二分查找看in数组里有没有对应项，然后将i存入到in数组对应的结构体中，都计算结束之后，再sort回来原来的序列，

输出答案。代码还没有写，这是别人的，稍后补上：

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 #define  mm  69  //保存的fib数列的位数（长度） 或59 或79 都ok  7 struct IN  // 存输入的数据  8 {  9     char ss[44]; 10     int ans,id; 11 }in[50008]; 12 struct AA   // 存 fib 数列 13 { 14     int x[mm],len; 15 }one[100005]; 16 char ss[50],ST[50]; 17  18  19 int bySS(IN x,IN y)  // 按ss值的大小排序（这里是从小到大） 20 { 21     return strcmp(x.ss,y.ss) < 0; 22 } 23 int byID(IN x,IN y) // 按id值的大小排序（这里是从小到大） 24 { 25     return x.id < y.id; 26 } 27  28 int main() 29 { 30 //    freopen("indata.txt","r",stdin); 31  //   freopen("out.txt","w",stdout); 32     int i,j,k,test,len; 33     int le,ri,mid,fg; 34     scanf("%d",&test); 35     for(getchar(),i=0;i < test;i++) 36     { 37         gets(in[i].ss); 38         in[i].ans = -1; 39         in[i].id = i; 40     } 41     sort(in,in+test,bySS); 42     memset(one,0,sizeof(one)); 43     one[0].x[1] = one[1].x[1] = one[0].len = one[1].len = 1; 44     for(i=0;i < test;i++)   //如果字符串是"1"，则其ans直接就是0 45         if(strcmp(in[i].ss,"1") == 0 && in[i].ans == -1) 46             in[i].ans = 0; 47     for(i=2;i < 100000;i++) //循环，同时处理要求的数据 48     { 49         for(j=1;j <= mm-9;j++) // fib 的计算 50             one[i].x[j] = one[i-1].x[j] + one[i-2].x[j]; 51         for(j=1;j <= mm-9;j++) // 进位处理 52             if(one[i].x[j] > 9) 53                 one[i].x[j+1]++, one[i].x[j]%=10; 54         for(j=mm-4;;j--) 55             if(one[i].x[j]) 56                 break; //找到第一个非0位 57         one[i].len = j;  //保存长度 58         for(len=0;len<=40 && j >= 1;j--,len++) 59             ss[len] = one[i].x[j]+'0'; //保存最多前40位 60         ss[len] = '\0'; 61         memset(ST,'\0',sizeof(ST)); 62         for(k=0;k < len;k++) //从一位到最多40位，依次去找，并且处理要求的数据 63         { 64             ST[k] = ss[k]; 65             fg=le=0, ri=test-1; 66             while(le <= ri) //二分查找 67             { 68                 mid = (le+ri)/2; 69                 if(strcmp(ST,in[mid].ss) == 0) 70                 { 71                     fg=1; 72                     break; 73                 } 74                 else if(strcmp(in[mid].ss,ST) < 0) 75                     le = mid+1; 76                 else 77                     ri = mid-1; 78             } 79             if(fg)  // 查找成功，并对应处理。 80             { 81                 for(j=mid;j >= 0;j--) 82                     if(strcmp(in[j].ss,in[mid].ss) == 0 && in[j].ans == -1) 83                         in[j].ans = i; 84                     else 85                         break; 86                 for(j=mid+1;j < test;j++) 87                     if(strcmp(in[j].ss,in[mid].ss) == 0 && in[j].ans == -1) 88                         in[j].ans = i; 89                     else 90                         break; 91             } 92         } 93     //        printf("i=%d ss=%s\n",i,ss); 94         if(one[i].len == mm-8)//表示多出了一位，则需要把整个字符串向后移动一位。 95         { 96             for(j=1;j <= mm-9;j++) //向后移动一位 97                 one[i].x[j] = one[i].x[j+1]; 98             one[i].x[mm-8] = 0; //最前面的那位要置0 99             for(j=1;j < one[i-1].len;j++) //同理处理之。100                 one[i-1].x[j] = one[i-1].x[j+1];101             one[i-1].x[one[i-1].len] = 0;102             one[i-1].len--;  //长度减一103             one[i].len--;104         }105     }106     sort(in,in+test,byID); //按id值排序，107     for(i=0;i < test;i++) //输出结果。108         printf("Case #%d: %d\n",i+1,in[i].ans);109     return 0;110 }