題意：
? ? ? 給你一個(gè)串（最長(zhǎng)40位）問你這個(gè)串是斐波那契F(n) ?n <= 99999中的那個(gè)數(shù)的前綴，如果存在多個(gè)輸出最小的n否則輸出-1.

思路：
? ? ? 給的串最長(zhǎng)40位，那么就直接把所有的斐波那契全求出來（每個(gè)要前40位，求

的時(shí)候多求幾位，省著精度出問題，不能全求出來，存不下）求出來后把他們建在一顆字典樹里面，建樹的時(shí)候注意開一個(gè)變量記住當(dāng)前位置的這個(gè)字母最早出現(xiàn)的是第幾個(gè)斐波那契數(shù)，然后對(duì)于每組詢問，直接查找就行了。

#include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct Tree {Tree *next[10];int v; }Tree;Tree root;void Buid_Tree(char *str ,int vv) {int len = strlen(str);Tree *p = &root ,*q;for(int i = 0 ;i < len ;i ++){int id = str[i] - '0';if(p -> next[id] == NULL){q = (Tree *) malloc(sizeof(root));q -> v = vv;for(int j = 0 ;j < 10 ;j ++)q -> next[j] = NULL;p -> next[id] = q;p = p -> next[id];}else p = p -> next[id];} }int Find(char *str) {int len = strlen(str);Tree *p = &root;for(int i = 0 ;i < len ;i ++){int id = str[i] - '0';if(p -> next[id] == NULL) return -1;p = p -> next[id];}return p -> v; }void Buid() {int a[80] ,b[80] ,c[80];char str[60];for(int i = 0 ;i < 10 ;i ++)root.next[i] = NULL;str[0] = '1' ,str[1] = '\0';Buid_Tree(str ,0);memset(a ,0 ,sizeof(a));memset(b ,0 ,sizeof(b));memset(c ,0 ,sizeof(c));a[1] = b[1] = 1;for(int i = 2 ;i < 100000 ;i ++){for(int j = 1 ;j <= 60 ;j ++)c[j] = a[j] + b[j];for(int j = 1 ;j <= 60 ;j ++)c[j+1] += c[j] / 10 ,c[j] %= 10;int max = 0;for(int j = 60 ;j >= 1 ;j --)if(c[j]){max = j; break;}int k = 0;for(int j = max ;j >= 1 ;j --){str[k++] = c[j] + '0';if(k == 40) break;}str[k] = '\0';Buid_Tree(str ,i);if(max > 55){for(int j = 6 ;j <= 60 ;j ++)b[j - 5] = b[j] ,c[j - 5] = c[j];for(int j = 56 ;j <= 60 ;j ++)b[j] = c[j] = 0;}for(int j = 1 ;j <= 60 ;j ++){a[j] = b[j];b[j] = c[j];c[j] = 0;}} }int main () {int t ,cas = 1;char str[50];Buid();scanf("%d" ,&t);while(t--){scanf("%s" ,str);printf("Case #%d: %d\n" ,cas ++ ,Find(str));}return 0; } ?

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的hdu 4099 字典树 + 斐波那契的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。