hdu 4099 Revenge of Fibonacci(字典树+大数加法)
发布时间:2020-12-14 03:56:54 所属栏目:大数据 来源:网络整理
导读:题意:给你一个数字字符串,表示一个整数的前几位(40),求这个整数出现斐波那契数列中的最早的位置n 解析:赤裸裸的字典树,不过要用大数优化,坑爹的是插入时要严格控制小于100000,不能等于;就因为这个wa了好久 #includeiostream#includecstdio#include
题意:给你一个数字字符串,表示一个整数的前几位(<40),求这个整数出现斐波那契数列中的最早的位置n 解析:赤裸裸的字典树,不过要用大数优化,坑爹的是插入时要严格控制小于100000,不能等于;就因为这个wa了好久 #include<iostream> #include<cstdio> #include<string.h> #include<string> using namespace std; #define N 100001 int maxx=45; struct node { int minn; node *next[11]; node() { minn=N; memset(next,sizeof(next)); } }*root; int search(node *root,char *s) { node *p=root; for(int i=0;s[i];i++) { int x=s[i]-'0'; if(p->next[x]==NULL) return -1; p=p->next[x]; //cout<<x<<" "<<p->minn; } //cout<<endl; return p->minn; } void insert(node *root,int *s,int m,int len) { node *p=root; int i; for(i=len;i>=0&&i>=len-40;i--) { int x=s[i]; //cout<<x; if(p->next[x]==NULL) p->next[x]=new node; p=p->next[x]; p->minn=min(p->minn,m); // if(x<30) // cout<<p->minn<<"********"<<endl; } // cout<<" "<<p->minn<<endl; } void inint() { int a[70],b[70],c[70]; memset(a,sizeof(a)); memset(b,sizeof(b)); memset(c,sizeof(c)); int i,j,k,ma,mb,mc,w; a[0]=b[0]=c[0]=1; ma=mb=mc=0; insert(root,c,0); for(i=2;i<N-1;i++) { memcpy(a,b,sizeof(a)); memcpy(b,sizeof(b)); memset(c,sizeof(c)); ma=mb; mb=mc; if(ma>=60) { for(k=0;k<70;k++) { if(k<=ma) a[k]=a[k+2]; else a[k]=0; } for(k=0;k<70;k++) { if(k<=mb) b[k]=b[k+2]; else b[k]=0; } ma-=2; mb-=2; } mc=-1; for(j=0;j<=ma;j++) { c[j]+=a[j]+b[j]; } for(j;j<=mb;j++) c[j]+=b[j]; for(j=0;j<70;j++) { w=c[j]; c[j]=w%10; c[j+1]+=w/10; if(c[j]) mc=max(mc,j); } insert(root,i,mc); /* for(j=mc;j>=0;j--) cout<<c[j]; cout<<endl; */ } } int main() { root=new node; inint(); int i,t=1,T,f; char s[100]; scanf("%d",&T); while(T--) { scanf("%s",&s); f=search(root,s); printf("Case #%d: %dn",t++,f); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |