HDU - 4333 :Revolving Digits (扩展KMP经典题,问旋转后有多少个不同的数字小于它本身,等于它本身,大于它本身。)
InputThe first line of the input contains an integer T (1<=T<=50) which means the number of test cases.
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.OutputFor each test case, please output a line which is "Case X: L E G", X means the number of the test case. And L means the number of integers is less than N that we can get by revolving digits. E means the number of integers is equal to N. G means the number of integers is greater than N.Sample Input
1
341
Sample Output
Case 1: 1 1 1
题意:给定一个数字,问旋转后有多少个不同的数字小于它本身,等于它本身,大于它本身。
思路:比较两个数的大小时,我们可以跳过前面相等的数字,直接比较第一个不相等的数字,那么就可以用exKMP,得到expand的位置,然后比较第一个不相等的位置。因为是求不同的数字的贡献,我们还要注意循环节。
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int Next[maxn],ans1,ans2,ans3; char c[maxn];
void exKMP(){
int i,len=strlen(c+);
Next[]=len;
for(int i=;i<=len;i++) c[i+len]=c[i];
for(i=;i+<len+len&&c[i+]==c[i+];i++);
Next[]=i; int a=;
for(int k=;k<=len+len;k++){
int p=a+Next[a]-, L=Next[k-a+];
if(L>=p-k+){
int j=(p-k+)>?(p-k+):;
while(k+j<=len+len&&c[k+j]==c[j+]) j++;
Next[k]=j, a=k;
}
else Next[k]=L;
}
ans1=ans2=ans3=;
for(int i=;i<=len;i++){
if(Next[i]>=len){ if(ans2) break; ans2++; }
else {
if(c[i+Next[i]]<c[Next[i]+]) ans1++;
else ans3++;
}
}
}
int main(){
int T,Cas=;
scanf("%d",&T);
while(T--){
scanf("%s",c+);
exKMP();
printf("Case %d: %d %d %d\n",++Cas,ans1,ans2,ans3);
}
return ;
}
最新文章
- python sokct 包详解
- 使用centos引导内核错误:kernel: pnp 00:0b: can&#39;t evaluate _CRS: 8
- 2-ls 显示目录内容
- golang channel buffer
- Java-Stack
- 使用gradle创建java程序
- CodeForces 617C【序枚举】
- C# 之 FileSystemWatcher事件多次触发的解决方法
- centos7搭建NIS与NFS综合应用
- Android中的测试类配置AndroidManifest.xml
- mysql配置文件转载
- Linux中fork()函数详解(转载)
- 最想做的三个Delphi项目:Paint,IM,SQL,另外还有Smart,TMS,FMX,UML,FreePascal,Python4Delphi,Cheat Engine
- C#HTTP代理的实现之注册表实现
- Spring事务配置的五种方式和spring里面事务的传播属性和事务隔离级别
- 使用MyBatis时接收值和返回值选择Map类型或者实体类型
- [bzoj1369] [Baltic2003]Gem
- bootstrap-table分页数据前台不显示
- chrome浏览器快捷键大全
- Kafka配置说明