本文主要是介绍[BZOJ1398] Vijos1382寻找主人 Necklace,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
传送门
http://www.lydsy.com/JudgeOnline/problem.php?id=1398
题目大意
求最小表示法
题解
constmaxn=1000010;
varx,ans1,ans2:array[0..maxn]of longint;i,j,k:longint;n:longint;cha:char;
begini:=0;while not eoln dobegin inc(i); read(cha); x[i]:=ord(cha)-48; end; n:=i; readln;i:=1; j:=2; x[n+1]:=maxlongint;while (i<=n)and(j<=n) dobegink:=0;while x[i+k]=x[j+k] doinc(k);if x[i+k]<x[j+k]then inc(j,k+1)else inc(i,k+1);if i=j then inc(j);end;k:=1;for j:=i to n dobegin ans1[k]:=x[j]; inc(k); end;for j:=1 to i-1 dobegin ans1[k]:=x[j]; inc(k); end;i:=0;while not eoln dobegin inc(i); read(cha); x[i]:=ord(cha)-48; end;n:=i; readln;i:=1; j:=2; x[n+1]:=maxlongint;while (i<=n)and(j<=n) dobegink:=0;while x[i+k]=x[j+k] doinc(k);if x[i+k]<x[j+k]then inc(j,k+1)else inc(i,k+1);if i=j then inc(j);end;k:=1;for j:=i to n dobegin ans2[k]:=x[j]; inc(k); end;for j:=1 to i-1 dobegin ans2[k]:=x[j]; inc(k); end;k:=1;for i:=1 to n doif ans1[i]<>ans2[i] then begin k:=0; break; end;if k=0 then begin writeln('No'); halt; end;writeln('Yes');for i:=1 to n-1 dowrite(ans1[i]);writeln(ans1[n]);
end.
这篇关于[BZOJ1398] Vijos1382寻找主人 Necklace的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!