题意:
给你一个数,这个数是斐波那契数列中的一个数的前缀,找出这个前缀的最小下标. 且这个下标如果超过了10W还没有符合要求的话,就输出-1.且输入数不会超过40位,且没有前导0.
分析:
直接思路那就是把前10W个斐波那契数列都搞出来构建字典树,然后对每个输入串判断该字典即可. 这种想法不可行~,下标为10W的斐波那契数大概有几万位,不可能这样加的.
我们只存前60位.50-60位可能会有进位,但是概率来说进位影响不到前40位.
如果新出来的数是61位了,我们只需对它对它进行截取最后一位,同样,和它即将相加的另外一个数末尾一位也截一位.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 60*100000+1111;
void add(char *a,char *b,char *c)
{int len1 = strlen(a);int len2 = strlen(b);int i=len1-1,j=len2-1;int carry = 0;int k = 0;char tmp[111];while(i>=0||j>=0){int x,y,z;if(i<0)x=0;else x=a[i]-'0';if(j<0)y=0;else y=b[j]-'0';z=x+y+carry;tmp[k++]=z%10+'0';carry=z/10;i--;j--;}if(carry)tmp[k++]=carry+'0';for(int i=0;i<k;i++)c[i]=tmp[k-1-i];c[k]=0;
}struct node
{int ch[maxn][10];int v[maxn];int sz;void init(){sz=1;memset(ch[0],0,sizeof(ch[0]));memset(v,-1,sizeof v);}void insert(char *s,int vv){int u=0,n=strlen(s);for(int i=0;i<n && i<40;i++){int id=s[i]-'0';if(ch[u][id]==0){ch[u][id]=sz;memset(ch[sz],0,sizeof ch[sz]);v[sz]=-1;sz++;}u=ch[u][id];if(v[u]<0)v[u]=vv;}}int find(char *s){int n=strlen(s),u=0;for(int i=0;i<n;i++){int id=s[i]-'0';if(ch[u][id]==0)return -1;u=ch[u][id];}return v[u];}
}trie;char str[3][111];
int main()
{trie.init();///初始化前100000个F数str[0][0]='1';str[0][1]=0;trie.insert(str[0],0);str[1][0]='1';str[1][1]=0;for(int i=2;i<100000;i++){int len1=strlen(str[0]);int len2=strlen(str[1]);if(len2>60){str[0][len1-1]=0;str[1][len2-1]=0;}add(str[0],str[1],str[2]);trie.insert(str[2],i);strcpy(str[0],str[1]);strcpy(str[1],str[2]);}int t;cin>>t;for(int kase=1;kase<=t;kase++){scanf("%s",str[0]);int ans=trie.find(str[0]);printf("Case #%d: %d\n",kase,ans);}
}