首页 > 代码库 > UVa12333 Revenge of Fibonacci
UVa12333 Revenge of Fibonacci
高精度 trie
暴力预处理出前100000个fibonacci数，将每个数的前40位数字串插入到trie中，记录每个结点最早可以由哪个数字串到达。
然后依次回答询问即可。
存fibonacci数的数组当然要滚动起来。
时限是10秒。本机试着卡了常数后跑了18秒（这个高精度写法好像本来就很慢），干脆交一波，UVA上7s AC
↑for循环i+=4 和直接一个register跑出来一样快，果然WC2017那道题只能在特定机子上做吗233
↑本机CPU是Intel I5-4590
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<queue> 6 #include<cstdlib> 7 #include<time.h> 8 using namespace std; 9 const int mxn=200010;10 struct Num{11 int x[24501];12 int len;13 friend Num operator + (Num a,Num b){14 a.len=max(a.len,b.len);15 // printf("len:%d\n",a.len);16 int ed=a.len/4*4;17 for(int i=1;i<=ed;i+=4){18 a.x[i]+=b.x[i];19 a.x[i+1]+=b.x[i+1];20 a.x[i+2]+=b.x[i+2];21 a.x[i+3]+=b.x[i+3];22 }23 for(int i=ed+1;i<=a.len;i++)24 a.x[i]+=b.x[i];25 26 // for(register int i=1;i<=a.len;i++) a.x[i]+=b.x[i];27 28 for(int i=1;i<=a.len;i++){29 if(a.x[i]>=10){30 a.x[i+1]+=a.x[i]/10;31 a.x[i]%=10;32 }33 }34 if(a.x[a.len+1]) ++a.len;35 return a;36 }37 }a[2];38 struct Trie{39 int t[4850007][10];40 int end[4850007];41 int cnt,rt;42 void init(){43 memset(end,0x3f,sizeof end);44 cnt=rt=1;45 }46 void insert(int id,Num a){47 int ed=a.len;48 int st=max(1,a.len-40+1);//取高位40位 49 int now=rt;50 for(int i=ed;i>=st;i--){51 if(!t[now][a.x[i]])t[now][a.x[i]]=++cnt;52 now=t[now][a.x[i]];53 end[now]=min(end[now],id);54 }55 }56 int query(char *s){57 int now=rt,len=strlen(s),tmp;58 for(int i=0;i<len;i++){59 tmp=s[i]-‘0‘;60 if(!t[now][tmp])return -1;61 now=t[now][tmp];62 if(end[now]>100000)return -1;63 }64 return end[now];65 }66 }tr;67 void init(){68 a[0].len=1;a[0].x[1]=1;69 a[1].len=1;a[1].x[1]=1;70 tr.insert(0,a[0]);71 tr.insert(1,a[1]);72 for(int i=2;i<100000;i++){73 // printf("init:%d \n",i);74 int tmp=i&1;75 a[tmp]=a[tmp]+a[tmp^1];76 // for(int j=1;j<=a[tmp].len;j++)printf("%d ",a[tmp].x[j]);77 // printf("%d cnt:%d\n",i,tr.cnt);78 tr.insert(i,a[tmp]);79 }80 return;81 }82 char s[mxn];83 int n;84 int main(){85 int i,j;86 // clock_t a=clock();87 // printf("%d\n",a);88 tr.init();89 init();90 // clock_t b=clock();91 // printf("%d\n",b);92 // printf("fin: %d \n",b-a);93 scanf("%d",&n);94 for(i=1;i<=n;i++){95 scanf("%s",s);96 printf("Case #%d: %d\n",i,tr.query(s));97 }98 return 0;99 }
UVa12333 Revenge of Fibonacci
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。