Revolving Digits(hdu4333)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Revolving Digits(hdu4333),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4375字,纯文字阅读大概需要7分钟。
内容图文
![Revolving Digits(hdu4333)](/upload/InfoBanner/zyjiaocheng/1129/bb528dbd05ad4fe79a82b7b2b8dae79f.jpg)
Revolving Digits
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 24215 Accepted Submission(s): 5268
For each test cases, there is only one line that is the original integer N. we will ensure that N is an positive integer without leading zeros and N is less than 10^100000.
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<stdlib.h> 6 #include<math.h> 7 #include<cstdio> 8 #include<queue> 9 #include<stack> 10 #include<map> 11char tt[2*100005]; 12int extend[2*100005]; 13int nex[100005]; 14char d[100005]; 15char cc[100005]; 16int pp[100005]; 17void next1(int k); 18void EXkmp(int k,int r); 19usingnamespace std; 20int main(void) 21{ 22int i,j,k,p,q; 23 scanf("%d",&k); 24for(int s =1; s<=k; s++) 25 { 26 memset(nex,0,sizeof(nex)); 27 memset(extend,0,sizeof(extend)); 28 scanf("%s",d); 29int l=strlen(d); 30for(i=1; i<=2*l; i++) 31 { 32if(i<=l) 33 tt[i]=d[i-1]; 34else 35 tt[i]=d[i-l-1]; 36 } 37for(i=0; i<l; i++) 38 cc[i+1]=d[i]; 39 j=0; 40 pp[0]=0; 41 pp[1]=0; 42for(i=2; i<=l; i++) 43 { 44while(j>0&&cc[j+1]!=cc[i]) 45 { 46 j=pp[j]; 47 } 48if(cc[j+1]==cc[i]) 49 { 50 j++; 51 } 52 pp[i]=j; 53 } 54int temp=l/(l-pp[l]); 55if(temp==0) 56 { 57 temp=1; 58 } 59 next1(l); 60 EXkmp(2*l,l); 61int a[4]; 62 memset(a,0,sizeof(a)); 63for(i=1; i<=l+1; i++) 64 { 65if(extend[i]==l)//当匹配数等于l时就相等 66 { 67 a[1]++; 68 } 69else 70 { 71if(tt[i+extend[i]]-‘0‘>cc[extend[i]+1]-‘0‘)//不等于l时比较开始不相等的那位 72 { 73 a[0]++; 74 } 75else a[2]++; 76 } 77 } 78 printf("Case %d: ",s); 79 printf("%d %d %d\n",a[2]/temp,(a[1]-1)/temp,a[0]/temp); 80 81 } 82 83} 84void next1(int k) 85{ 86int i,j,p; 87 j=1; 88int r=j; 89 nex[1]=0; 90while(cc[j+1]==cc[j]&&j+1<=k) 91 { 92 j++; 93 } 94 nex[2]=j-r; 95int id=2; 96for(i=3; i<=k; i++) 97 { 98 p=id+nex[id]-1; 99int L=nex[i-id+1]; 100int c=i+L-1; 101if(c>=p) 102 { 103int j=p-i+1; 104if(j<0)j=0; 105while(cc[j+1]==cc[j+i]&&j+i<=k) 106 { 107 j++; 108 } 109 nex[i]=j; 110 id=i; 111 } 112else nex[i]=L; 113 } 114} 115116void EXkmp(int k,int r) 117{ 118int i,j; 119 j=0; 120while(cc[j+1]==tt[j+1]&&j+1<=r) 121 { 122 j++; 123 } 124 extend[1]=j; 125int id=1; 126int p; 127for(i=2; i<=k; i++) 128 { 129 p=id+extend[id]-1; 130int L=nex[i-id+1]; 131int c=i+L-1; 132if(c>=p) 133 { 134 j=p-i+1; 135 j=max(j,0); 136while(cc[j+1]==tt[j+i]&&j+i<=k&&j<=r) 137 { 138 j++; 139 } 140 extend[i]=j; 141 id=i; 142 } 143else extend[i]=L; 144 } 145 }
原文:http://www.cnblogs.com/zzuli2sjy/p/5186473.html
内容总结
以上是互联网集市为您收集整理的Revolving Digits(hdu4333)全部内容,希望文章能够帮你解决Revolving Digits(hdu4333)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。