UVA-12333 Fibonacci的复仇 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

算法竞赛入门经典书中给出了大数类的算法，直接照抄即可。

我的做题过程：

1. 照着书上抄了大数类，下面的判断就使用循环查找。结果超时。

2. 大数类从int改成了long long，base成了10^16。结果还是超时。

3. 不直接存储大数类本身，只存储前40个数字的string的vector。结果超时。

3. 优化细节：iostream改成stdio.h，生成Fibonacci数列时采用长度为3的数组循环，减少大数类的赋值，所有循环中的变量都提前定义好，size()等函数都提前计算好保存。结果还是超时。

4. 在计算好Fibonacci数列后，直接结束函数，发现从Time limit exceeded变为了Wrong answer，看来计算数列的过程可能不是超时的原因，查找的时候才是。查找时候的复杂度最高是100000*50000。

5. 尝试对存储前40个数字的string的vector进行字典序排序，打算用二分查找找出字典序最符合的。结果发现这和题目要求不符，题目要求的不是字典序最靠前的，而是符合前n个数字时序号最靠前的，因此排序的方法行不通。

6. 发现字典树可以解决这个查找的问题。从根节点到当前节点路径形成的数字序列就是查找的序列，当前节点对应的值就是这个序列最早出现的序号。从超时变为Wrong answer。

7. 改了一点小问题，比如从数字转字符串时：1. 严格只要前40个；2. 注意非大数类中非第一个数子转换成字符串时，需要补前导0。结果AC。

AC代码

#include
#include
#include
#include
#include

using namespace std;

struct BigInt {
	static const long long BASE = 1000000000000000000;
	static const int WIDTH = 18;
	static const int LEN = 4;
	
	vector s;
	BigInt(long long num = 0) {
		*this = num;
	}
	BigInt operator= (long long num) {
		s.clear();
		do {
			s.push_back(num % BASE);
			num /= BASE;
		} while(num > 0);
		return *this;
	}
	BigInt operator+ (const BigInt &b) {
		BigInt c;
		c.s.clear();
		long long g = 0, x;
		int ssize = s.size(), bssize = b.s.size();
		for(int i = 0; ; i++) {
			if(g == 0 && i >= ssize && i >= bssize) break;
			x = g;
			if(i < ssize) x += s[i];
			if(i < bssize) x += b.s[i];
			c.s.push_back(x % BASE);
			g = x / BASE;
		}
		return c;
	}
	string outN() {
		string str, st;
		int i = s.size() - 1, j = LEN;
		while(i >= 0 && j > 0) {
			st = to_string(s[i]);
			while(i != s.size() - 1 && st.length() < WIDTH) {
				st = "0" + st;
			}
			str += st;
			--i;
			--j;
		}
		return str.substr(0, 40); 
	}
};

struct Node {
	int id;
	int num;
	Node* childs[10] = {NULL};
};

vector v;

Node* createTree() {
	int i, j, n, num;
	Node * tree = new Node;
	tree->id = -1;
	tree->num = -1;
	for(i = 0; i < v.size(); ++i) {
		n = v[i].size();
		Node *p = tree;
		for(j = 0; j < n; ++j) {
			num = v[i][j] - '0';
			if(!p->childs[num]) {
				p->childs[num] = new Node;
				p->childs[num]->id = i;
				p->childs[num]->num = num;
			}
			p = p->childs[num];
		}
	}
	return tree;
}

int main() {
	char s[45];
	int i, j, T, n, num, res;
	BigInt bv[3];
	bv[0] = 1;
	bv[1] = 1;
	v.push_back("1");
	v.push_back("1");
	for(i = 2; i < 100000; ++i) {
		bv[i % 3] = bv[(i-1) % 3] + bv[(i-2) % 3];
		v.push_back(bv[i % 3].outN());
	}
	scanf("%d", &T);
	
	Node * tree = createTree();
	
	for(i = 0; i < T; ++i) {
		scanf("%s", s);
		n = strlen(s);
		Node * p = tree;
		for(j = 0; j < n; ++j) {
			num = s[j] - '0';
			if(!p->childs[num]) {
				break;
			}
			p = p->childs[num];
		}
		if(j == n) {
			res = p->id; 
		} else {
			res = -1;
		}
		printf("Case #%d: %dn", i+1, res);
	} 
	return 0;
}