題目鏈接：hdu 4099 Revenge of Fibonacci
題目大意：給定1個前綴，找到最小的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("
");
}
}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
", 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];
}
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
