首页 > 代码库 > hdu4099 Revenge of Fibonacci

hdu4099 Revenge of Fibonacci

2024-08-14 19:45:08   219人阅读

   题意：给定fibonacci数列，输入前缀，求出下标。题目中fibonacci数量达到100000，而题目输入的前缀顶多为40位数字，这说明我们只需要精确计算fibinacci数前40位即可。查询时使用字典树。在计算时，为了保证前40位精确无误。在此我计算了前60位。以保证前面不在进位。

注意点：

       1）关于表示进位问题，需要控制计算的数位数在60以内，切记计算时不要错位（相同位要对齐）。

       2）坑点：题目给出的数插入字典树最好插入前40位即可，否则MLE.

       3）坑点：题目只要求计算下标不超过100000，计算到100000或者以上均会WA，因为输出值不是-1

下面是数组的AC代码：824ms

#define _CRT_SECURE_NO_DEPRECATE#include<iostream>#include<string>#include<map>#include<fstream>#include<ctime>#include<queue>#include<vector>#include<numeric>#include<string.h>#include<iomanip>#include<sstream>#include<algorithm>using namespace std;typedef pair<int,int> PII;typedef vector<int> BigInterger;const int maxn = 100000;const int maxsize = 10;const int maxnum =65;struct TrieNode{	TrieNode(int d = -1) :id(d){ memset(next, NULL, sizeof(next)); }	int id;	TrieNode*next[maxsize];};TrieNode*T = new TrieNode;void insert(char*str,const int&index){	int len = strlen(str);	TrieNode*p = T;	int t = 0;	for (int i = len-1; i>=0&&t<40;i--,t++){		int id =str[i]-‘0‘;		if (!p->next[id])p->next[id] = new TrieNode(index);		p = p->next[id];	}}int search(char*str){	TrieNode*p = T;	while (*str != ‘\0‘){		int id = *str++ - ‘0‘;		if (!p->next[id])return -1;		p = p->next[id];	}	return p->id;}void init(){	char f[3][maxnum];	f[1][0] =‘1‘; f[1][1] = ‘\0‘;	f[0][0] =‘1‘; f[0][1] = ‘\0‘;	insert("1", 0);	for (int i = 2; i<maxn; i++){		int g = 0,j=0,cnt = 0, x;		int r1 = (i - 1) % 3, r2 = (i - 2) % 3, r = i % 3;		int lena = strlen(f[r1]);		int lenb = strlen(f[r2]);		if (lena >= maxnum - 5){			memcpy(f[r1], f[r1]+1, lena - 1); f[r1][lena - 1] = ‘\0‘;			memcpy(f[r2], f[r2]+1, lenb - 1); f[r2][lenb - 1] = ‘\0‘;			lena--, lenb--;		}		while (g || j < lena||j<lenb){			x = g;			if (j < lena)x += f[r1][j]-‘0‘;			if (j < lenb)x += f[r2][j]-‘0‘;			f[r][cnt++] = x % 10+‘0‘;			g = x / 10;			j++;		}		f[r][cnt] = ‘\0‘;		insert(f[r], i);	}}int main(){	init();	int T,kase=1;	char str[50];	scanf("%d", &T);	while(T--){		scanf("%s", str);		printf("Case #%d: %d\n",kase++,search(str));	}	return 0;}

　采用向量AC的代码624ms(传值要用引用，否则多了不必要的复制)：

#define _CRT_SECURE_NO_DEPRECATE#include<iostream>#include<string>#include<map>#include<fstream>#include<ctime>#include<queue>#include<vector>#include<numeric>#include<string.h>#include<iomanip>#include<sstream>#include<algorithm>using namespace std;typedef pair<int,int> PII;typedef vector<int> BigInterger;const int maxn = 100000;const int maxsize = 10;const int maxnum =65;struct TrieNode{	TrieNode(int d = -1) :id(d){ memset(next, NULL, sizeof(next)); }	int id;	TrieNode*next[maxsize];};TrieNode*T = new TrieNode;void insert(const BigInterger&v,const int&index){	int len=v.size();	TrieNode*p = T;	int t = 0;	for (int i = len-1; i>=0&&t<40;i--,t++){		int id =v[i];		if (!p->next[id])p->next[id] = new TrieNode(index);		p = p->next[id];	}}int search(char*str){	TrieNode*p = T;	while (*str != ‘\0‘){		int id = *str++ - ‘0‘;		if (!p->next[id])return -1;		p = p->next[id];	}	return p->id;}//引用传值，避免赋值，效率更高void add(BigInterger &a, BigInterger &b, BigInterger&c){	int lena = a.size(), lenb = b.size();	int g=0, x,i=0;	c.clear();	if (lena > maxnum - 5 || lenb > maxnum - 5){ 		a.erase(a.begin()), b.erase(b.begin());		lena--, lenb--;	}	while (g || i < lena || i < lenb){		x = g;		if (i < lena)x += a[i];		if (i < lenb)x += b[i];		c.push_back(x % 10);		g = x / 10;		i++;	}}void init(){	BigInterger a[3];	a[0].push_back(1);	a[1].push_back(1);	insert(a[1], 0);	for (int i = 2; i<maxn; i++){		add(a[(i - 1) % 3], a[(i - 2) % 3], a[i % 3]);		insert(a[i % 3], i);	}}int main(){	init();	int T,kase=1;	char str[50];	scanf("%d", &T);	while(T--){		scanf("%s", str);		printf("Case #%d: %d\n",kase++,search(str));	}	return 0;}

　　

　

hdu4099 Revenge of Fibonacci


联系
我们