「vijos1382」寻找主人
Description
给定两个项链的表示，判断他们是否可能是一条项链。Input
输入文件只有两行，每行一个由0至9组成的字符串，描述一个项链的表示（保证项链的长度是相等的）。
Output
如果两条项链不可能同构，那么输出’No’，否则的话，第一行输出一个’Yes’，第二行输出该项链的字典序最小的表示。 设L = 项链长度， 对于50%的数据L <= 100000； 对于100%的数据L <= 1000000。
题解
http://wenku.baidu.com/link?url=Jtn398dsc9nSs3kcmQZoiJ88j2lwweD2TcBJaqJKHP0mqQpn76vrCqX_rTL6TPKSTCwrowgpcmidUIAaLK2tAAM50pk5OOerNK6gIN_nQqy
求出两个串的最小表示法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<map> #include<set> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define inf 1000000000 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int l1,l2; char a[1000005],b[1000005]; int mp(char *s,int l) { int i=0,j=1,k=0,t; while(i<l&&j<l&&k<l) { t=s[(i+k)%l]-s[(j+k)%l]; if(!t)k++; else { if(t>0)i=i+k+1; else j=j+k+1; if(i==j)i++; k=0; } } return min(i,j); } int main() { scanf("%s",a); scanf("%s",b); int l=strlen(a); int t1=mp(a,l); int t2=mp(b,l); for(int i=0;i<l;i++) if(a[(t1+i)%l]!=b[(t2+i)%l]) { puts("No");return 0; } puts("Yes"); for(int i=0;i<l;i++) printf("%c",a[(t1+i)%l]); return 0; } |
Subscribe
计数器 9787692
OI 课件=>
OI 课件=>