一开始想的是java大数然后字典树插入前40个。
但是这样会爆内存，数太大了。
但其实超过40之后保存前50位就可以了，这样精度也能保证。
这题题目内存很紧，优化了好几次常数终于过了。
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 1e6 + 5; const int M = 4e4+5; const LL Mod = 1e9+7; #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } } using namespace FASTIO; int tree[N * 5][10],tim[N * 10],k = 0; char a[55],b[55],c[55],s[55]; void Insert(char s[],int id){ int len = strlen(s),p = 0; for(int i = 0;i < len;++i){ int c = s[i] - '0'; if(tree[p][c] == 0) { tree[p][c] = ++k; tim[tree[p][c]] = id; } p = tree[p][c]; } } int query(char s[]){ int len = strlen(s),p = 0; for(int i = 0;i < len;++i){ int c = s[i] - '0'; if(tree[p][c] == 0) return -1; p = tree[p][c]; } return tim[p]; } void Add(int up) { int la = strlen(a) - 1,lb = strlen(b) - 1,res[105],l = 0,t = 0; while(la >= 0){ res[l] = (a[la] - 48) + (b[lb] - 48) + t; t = 0; if(res[l] >= 10)res[l] -= 10,t = 1; la--,lb--,l++; } while(lb >= 0){ res[l] = b[lb] - 48 + t; t = 0; if(res[l] >= 10) res[l] -= 10,t = 1; lb--,l++; } if(t) res[l++] = 1; int i = 0,k = 0; if(l > up) k = l - up; l--; while(l >= 0 && i < up) c[i++] = res[l--] + 48; c[i] = ' '; //计算完c的值。即a + b lb = strlen(b); int lc = strlen(c); for(int j = 0;j < lb - k;j++) a[j] = b[j];//轮换，a = b a[lb-k] = ' '; for(int j = 0;j < lc;j++) b[j] = c[j];//b = c; b[lc] = ' '; } void init() { a[0] = '1',a[1] = ' '; b[0] = '1',b[1] = ' '; Insert(a,0);Insert(b,1); for(int i = 2;i < 100000;++i){ Add(50); Insert(c,i); } } int main() { init(); int ca;ca = read(); int tot = 0; while(ca--) { scanf("%s",s); int ans = query(s); printf("Case #%d: %d ",++tot,ans); } system("pause"); return 0; }