首页 > 代码库 > 【BZOJ 1398】 1398: Vijos1382寻找主人 Necklace (最小表示法)
【BZOJ 1398】 1398: Vijos1382寻找主人 Necklace (最小表示法)
1398: Vijos1382寻找主人 Necklace
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 308 Solved: 129Description
给定两个项链的表示,判断他们是否可能是一条项链。
Input
输入文件只有两行,每行一个由0至9组成的字符串,描述一个项链的表示(保证项链的长度是相等的)。
Output
如果两条项链不可能同构,那么输出’No’,否则的话,第一行输出一个’Yes’第二行输出该项链的字典序最小的表示。 设L = 项链长度,L <= 1000000。Sample Input
2234342423
2423223434
Sample Output
Yes
2234342423HINT
Source
【分析】
最小表示法。。有点忘了。。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 #define Maxn 1000010 8 9 char s1[2*Maxn],s2[2*Maxn]; 10 int l; 11 12 int mymin(int x,int y) {return x<y?x:y;} 13 14 int ffind(char *s) 15 { 16 int i=0,j=1,k=0; 17 while(i+k<=l&&j+k<=l) 18 { 19 if(s[i+k]==s[j+k]) k++; 20 else if(s[i+k]<s[j+k]) j+=k+1,k=0; 21 else i+=k+1,k=0; 22 if(i==j) j++; 23 } 24 return mymin(i,j); 25 } 26 27 int main() 28 { 29 scanf("%s%s",s1,s2); 30 l=strlen(s1); 31 for(int i=0;i<l;i++) s1[i+l]=s1[i]; 32 for(int i=0;i<l;i++) s2[i+l]=s2[i]; 33 int a=ffind(s1),b=ffind(s2); 34 bool ok=1; 35 for(int i=0;i<l;i++) if(s1[a+i]!=s2[b+i]) {ok=0;break;} 36 if(!ok) printf("No\n"); 37 else 38 { 39 printf("Yes\n"); 40 for(int i=0;i<l;i++) printf("%c",s1[a+i]); 41 printf("\n"); 42 } 43 return 0; 44 }
2017-04-17 08:14:10
【BZOJ 1398】 1398: Vijos1382寻找主人 Necklace (最小表示法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。