UVA - 12333 字典树+大数

?????????? 思路：用字典树将前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,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: %dn",kase++,find(s));
	}
	return 0;
}