924
HDU 4099 字典樹+高精度
題意：給出某項斐波那契數的前幾位，讓輸出最小的一項前綴為這個串的項數。
先高精度算出前100000項斐波那契的前50位。並把前40位存進字典樹預處理一下。字典樹節點值存為第幾項。然後輸入字符串直接查找。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 50
int fib[3][N+1];
class trie
{
public:
trie* next[10];
int value;
trie()
{
for(int i=0; i<10; i++)
next[i]=0;
value=-1;
}
} root,*a;
void insert(trie* p,int* s,int n,int len)
{
p=&root;
int k=len;
while(k>=0&&len-k<=40)
{
if(!p->next[s[k]])
p->next[s[k]]=new trie;
p=p->next[s[k]];
if(p->value==-1)
p->value=n;
k--;
}
}
int find(trie* p,char* s)
{
p=&root;
int k=0,ans;
while(s[k]!='\0')
{
if(!p->next[s[k]-'0'])
return -1;
p=p->next[s[k]-'0'];
k++;
}
return p->value;
}
void init()
{
memset(fib,0,sizeof(fib));
char str[45];
fib[0][0]=1;
fib[1][0]=1;
insert(a,fib[0],0,0);
int i,j;
for(i=2; i<100000; i++)
{
int c=0;
for(j=0; j<=N; j++)
{
fib[2][j]=(c+fib[1][j]+fib[0][j])%10;
c=(c+fib[1][j]+fib[0][j])/10;
}
if(j==N+1&&c>0)
{
for(int t=0; t<N; t++)
{
fib[0][t]=fib[1][t+1];
fib[1][t]=fib[2][t+1];
}
fib[0][N]=0;
fib[1][N]=c;
}
else
{
for(int t=0; t<=N; t++)
{
fib[0][t]=fib[1][t];
fib[1][t]=fib[2][t];
}
}
int t;
for(t=N; t>=0; t--)
if(fib[1][t]) break;
insert(a,fib[1],i,t);
}
}
int main()
{
init();
char temp[45];
int t,ca=0;
scanf("%d",&t);
while(t--)
scanf("%s",temp),
printf("Case #%d: %d\n",++ca,find(a,temp));
return 0;
}
最後更新：2017-04-03 16:48:34