题目：Revenge of Fibonacci
题意：输入一串斐波拉契数的前缀，求包含这个前缀的最小斐波拉契数的编号。
思路：
1、先生成100000个斐波拉契数，用字符串实现高精度的加法。因数据要求前缀长度最大为40，所以可以少存几位，因为精度问题，所以存50位。
2、读入前缀，查找最小的。
这里顺序查找的复杂度很高，会超时，然后我就懵逼了。
网上找题解，学习一种叫字典树的东西，大致就是处理公共前缀、快速查找之类的。
（百度百科：字典树）
我的字典树用数组实现，下次再尝试写下指针吧（从来没尝试过指针这玩意）。
注意：数据规模是小于（smaller than）100000，不是小于等于！
代码：
#include<cstdio>
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;struct NODE{int x;int son[10];NODE(int one){x=one;for(int i=0;i<=9;i++){son[i]=(1<<30);}}
};vector<NODE> vec;
string f[100005];void make(int i,string& str){string a=f[i-2],b=f[i-1];if(a.size()<b.size()){a="0"+a;}bool Add=false;int Size=a.size()-1;for(int j=min(Size,50);j>=0;j--){int x=a[j]-'0'+b[j]-'0'+Add;if(x>=10) x%=10,Add=true;else Add=false;str=(char)(x+'0')+str;}if(Add==true) str="1"+str;
}void add(int id,string& str){int now=0;for(int i=0;i<str.size();i++){int x=str[i]-'0';if(vec[now].son[x]==(1<<30)){vec[now].son[x]=vec.size();vec.push_back(NODE(id));}now=vec[now].son[x];}
}int find(string str){int now=0;for(int i=0;i<str.size();i++){int x=str[i]-'0';if(vec[now].son[x]==(1<<30)){return -1;}now=vec[now].son[x];}return vec[now].x;
}int main() {vec.push_back(NODE(0));f[0]=f[1]="1";add(1,f[1]);for(int i=2;i<100000;i++){make(i,f[i]);add(i,f[i]);}int m,T=0;scanf("%d",&m);while(++T&&T<=m){string x;cin>>x;int y=find(x);if(x=="1") y=0;printf("Case #%d: %d\n",T,y);}return 0;
}