思路:用字典树将前40个数字记录下来,模拟大数加法即可。
AC代码
#include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 10; struct Node{ int num; Node *next[maxn]; Node(){ num = -1; for(int i = 0; i < maxn; i++) { next[i] = NULL; } } }*root; void init() { root = new Node(); } void insert(int *a, int n, int num) { n = min(n, 40); Node *p = root, *q; for(int i = 0; i < n; ++i) { int x = a[i]; if(p->next[x] == NULL) { q = new Node(); q->num = num; p->next[x] = q; } p = p->next[x]; } } int find(char *a) { Node *p = root; int n = strlen(a); for(int i = 0; i < n; ++i) { int x = a[i] - '0'; if(p->next[x] == NULL) return -1; p = p->next[x]; } return p->num; } //高精度加法 const int Base = 100000000; int a[2][20000+5], val[100]; int f = 0, h = 1; stack<int>sta; void Deal() { memset(a, 0, sizeof(a)); a[0][0] = 1, a[1][0] = 1; val[0] = 1; int len[2] = {1,1}; insert(val, 1, 0); for(int i = 2; i < 100000; ++i) { int g = 0; for(int j = 0; j < len[f] || j < len[h] || g > 0; ++j) { int x = a[f][j] + a[h][j] + g; a[f][j] = x % Base; g = x / Base; len[f] = max(len[f], j+1); } int cur = 0; for(int j = len[f]-1; j >= 0; --j) { if(cur >= 40) break; int x = a[f][j]; if(j == len[f] - 1) { while(x) { sta.push(x % 10); x /= 10; } } else { int u = 0, t = x; while(t) { ++u; t /= 10; } while(x) { sta.push(x % 10); x /= 10; } for(int k = 0; k < 8 - u; ++k) { sta.push(0); } } while(!sta.empty()) { val[cur++] = sta.top(); sta.pop(); } } //insert insert(val, cur, i); f = 1 - f; h = 1 - h; } } int main() { init(); Deal(); int T, kase = 1; scanf("%d", &T); char s[50]; while(T--) { scanf("%s", s); printf("Case #%d: %d\n", kase++, find(s)); } return 0; }
如有不当之处欢迎指出!