UVa 12333 - Revenge of Fibonacci(字典树+高精度压位)

输入一个斐波那契数的前缀,求开头与所给前缀相同的最小斐波那契数的编号。

容易超时的一道题,计算前十万个斐波那契数要用高精度算法,还要注意只保留前50位就够了,不然会超时。

然后就是查询,原本保存在string数组中,单次查找复杂度为O(n*s.length())。发现查找会超时,后来使用了字典树,单次查找仅为O(s.lengt
h()),效率提高很多,就过了。

建树使用了指针,调用之前一定要判断不为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<vector>
#include<string>
using namespace std;
vector<int>a[3];
struct Node{
int num;
bool have_value;
Node* p[10];
Node(int num=0):num(num),have_value(false){}
};
Node* root;
Node* newnode(){
Node* temp;
temp=new Node();
for(int i=0;i<10;temp->p[i++]=NULL);
return temp;
}
string Sum(int x){//求前十万个斐波那契数。
string s0;
a[x%3]=a[(x-1)%3];
if(a[(x-1)%3].size()!=a[(x-2)%3].size())
for(int i=1;i<(int)a[(x-1)%3].size();i++)
a[x%3][i]+=a[(x-2)%3][i-1];
else for(int i=0;i<(int)a[(x-1)%3].size();i++)
a[x%3][i]+=a[(x-2)%3][i];
for(int i=(int)a[x%3].size()-1;i>0;i--){
a[x%3][i-1]+=a[x%3][i]/10;
a[x%3][i]%=10;
}
while(a[x%3][0]>9){
a[x%3].insert(a[x%3].begin(),a[x%3][0]/10);
a[x%3][1]%=10;
}
for(int i=0;i<a[x%3].size();s0+=a[x%3][i++]+'0');
while(a[x%3].size()>50&&a[(x-1)%3].size()>50){
a[x%3].erase(a[x%3].end()-1);
a[(x-1)%3].erase(a[(x-1)%3].end()-1);
}
return s0;
}
void build(Node* u,string s,int k){//建树。
for(int i=0;i<s.length();i++){
int t=s[i]-'0';
if(u->p[t]==NULL) u->p[t]=newnode();
if(!u->p[t]->have_value){
u->p[t]->have_value=true;
u->p[t]->num=k;
}
u=u->p[t];
}
return;
}
int search(string s,Node* b){//字典树查找。
for(int i=0;i<s.length();i++){
if(b->p[s[i]-'0']==NULL) return -1;
b=b->p[s[i]-'0'];
}
if(!b->have_value) return -1;//指针未赋值,返回-1。
return b->num;
}
int main(){
a[0].push_back(1);
a[1].push_back(1);
root=newnode();
root->p[1]=newnode();
root->p[1]->have_value=true;
for(int i=2;i<100000;i++)
build(root,Sum(i),i);
int n,t=0;
cin>>n;
while(n--){
string s0;
cin>>s0;
cout<<"Case #"<<++t<<": "<<search(s0,root)<<endl;
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。