UVa 12333 - Revenge of Fibonacci（字典树＋高精度压位）

发表于 分类于 ， Disqus：

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

容易超时的一道题，计算前十万个斐波那契数要用高精度算法，还要注意只保留前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博客，格式可能有所偏差。 **

相关文章