hdu 4099 Revenge of Fibonacci(字典树)

本文主要是介绍hdu 4099 Revenge of Fibonacci(字典树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：hdu 4099 Revenge of Fibonacci

题目大意：给定一个前缀，找到最小的n，保证f(n)包含前缀。f为斐波那契数列，要求n小于100000。

解题思路：大数加法，对100000以内的斐波那契数预处理出前缀，这里处理的时候只需要对前50位进行加法处理即

可，否则复杂度过高，因为查询的长度不会超过40。然后建立字典树，查询则在字典树上进行搜索。

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 1e6 + 5;
const int sigma_size = 10;struct Bign {int c, s[maxn];Bign() {}void operator = (int a) {c = 0;memset(s, 0, sizeof(s));while (a) {s[c++] = a % 10;a /= 10;}}void put() {for (int i = 1; i <= 40 && i <= c; i++)printf("%d", s[c-i]);printf("\n");}
}num[3];void add(const Bign& a, const Bign& b, Bign& ans) {int tmp = 0;ans.c = max(a.c, b.c);for (int i = max(min(a.c, b.c) - 50, 0); i < a.c || i < b.c; i++) {if (i < a.c) tmp += a.s[i];if (i < b.c) tmp += b.s[i];ans.s[i] = tmp % 10;tmp /= 10;}while (tmp) {ans.s[ans.c++] = tmp % 10;tmp /= 10;}
}struct Tire {int sz, g[maxn * 10][sigma_size];int val[maxn * 10];void init();int find(char* s);void insert(const Bign& a, int x);
}T;void init () {num[0] = 1;num[1] = 1;T.init();T.insert(num[0], 1);T.insert(num[1], 2);int t = 2;for (int i = 2; i < 100000; i++) {add(num[(t+1)%3], num[(t+2)%3], num[t]);T.insert(num[t], i + 1);t = (t + 1) % 3;}
}int main () {init();int cas;char s[60];;scanf("%d", &cas);for (int kcas = 1; kcas <= cas; kcas++) {scanf("%s", s);printf("Case #%d: %d\n", kcas, T.find(s) - 1);}return 0;
}void Tire::init() {sz = 1;val[0] = 0;memset(g[0], 0, sizeof(g[0]));
}int Tire::find(char* s) {int n = strlen(s), u = 0;for (int i = 0; i < n; i++) {int v = s[i] - '0';if (g[u][v] == 0)return 0;u = g[u][v];}return val[u];
}void Tire::insert(const Bign& a, int x) {int u = 0;for (int i = 1; i <= 40 && i <= a.c; i++) {int v = a.s[a.c - i];if (g[u][v] == 0) {val[sz] = x;memset(g[sz], 0, sizeof(g[sz]));g[u][v] = sz++;}u = g[u][v];}
}