题解 P1368 【工艺】
___new2zy___ · · 题解
题解 P1368 【工艺】
题目传送门：
https://www.luogu.org/problemnew/show/P1368
=================================================
事先声明：本人用的是最小表示法
（dalao们太厉害了，我都不知道SAM和后缀自动机是什么）
本人很蒻，所以只能给大家献上最小表示法了
（SAM去楼下看看吧）
希望管理员给本题加上一个最小表示法的标签，毕竟洛谷是没有这个分类的~~~
（本人找题做的时候就没有找到，还是学长安利的本题）
=================================================
咳咳，言归正传= =
这题其实是一个字符串的题，对于本题，我们姑且把这个序列叫做“字串”（接下来的叙述里请自行联想）
算法分析：最小表示法
本题的最小表示法就是找出字符串S的的循环同构串中字典序最小的一个。
那么什么是循环同构串呢？
我们设S= “bcad” ，且设S’是S的循环同构的串。那么S’可以是 “bcad” 或者 “cadb” , “adbc” , “dbca”
即在字符串S中从i>=0开始，从i循环到字符串末尾，再从头循环到i，所形成的字符就是S循环同构串。
又因为这样的同构串不止一个，所以我们要找出其中字典序最小的一个即为S的最小表示（即字符串从小到大排序，其中字典序最小的一个）
其实还是有最大表示法的，但本题从左到右进行操作，所以我们使用最小表示法即可
最小表示法其实就是找到位置i，从这个位置输出S，使得到的同构串字典序最小。
简介：最小表示法的实现方法：
假设有一个字符串S，请你求出S循环同构串的最小表示
设S的长度为len
1.利用两个指针i，j。初始化时i指向s[0]，j指向s[1]。
我们规定i和j在任意时刻都不能相等。
2.匹配长度k=0开始，检验s[i+k]和s[j+k]是否相等，相等k++，
一直下去，直到找到第一个不相同的字符
（若k试了一个字符串的长度也没找到不同，即整个串都是
相同的字符。则那个位置就是最小表示位置，算法终止并返回）
该过程中，我们发现s[i+k]和s[j+k]的关系有三种：1).s[i+k]>s[j+k], 由于s[i~ i+k-1 ]都不会是循环字符串的"最小表示"的前缀，i滑动到i+k+1处。
2).s[i+k]<s[j+k]，同理关系 1)，j滑动到 j+k+1 处。
3).s[i+k]==s[j+k]，则k++。
若滑动后i==j，将正在变化的那个指针在+1.直到i， j把整个字串都检验完毕，返回两者中小于len的值。
3.如果 k==len，则返回 min(i，j)=================================================
以上就是最小表示法的介绍
接下来放本题代码，code里也有进一步的解释
对于本题，过程还是要有些小变化的，解释中已给出
希望大家能理解最小表示法的过程
本题代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline int read()
{
int p=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
return f*p;}
int n,ans,A[300009];
int Min_show()
//最小表示法求出串的最小表示
{
int i=0,j=1,k=0;
//两个指针i,j,任意时刻i!=j,当前匹配长度为k
//循环同构串要复制一遍字串(成环)接在A序列后面
//由于数组过大,(i+k)%n和(j+k)%n代表了字串
//复制一遍接在原序列后各字符的对应位置
while(i<n&&j<n&&k<n)
{
if(A[(i+k)%n]==A[(j+k)%n])
//两个位置数值相等，匹配长度k++
k++;
else
{
if(A[(i+k)%n]>A[(j+k)%n])
//[i,i+k-1]与[j,j+k-1]相同
//那么在[i,i+k-1]中不可能有最小表示
//则i+=k+1,令k=0
i+=k+1;
else j+=k+1;
//同上
if(i==j)i++;
//任何时候都要满足i!=j
k=0;//匹配长度k归零
}
}
return min(i,j);//返回最小表示
}
int main()
{
n=read();
for(int i=0;i<n;i++)//初始字串
A[i]=read();
ans=Min_show();//求最小表示
for(int i=0;i<n;i++)//输出最小表示
printf("%d ",A[(i+ans)%n]);
return 0;
}=================================================
好啦，到这里就没有了~~~希望大家能理解最小表示法
有兴趣的同学还可以自行百度了解一下最大表示法
（其实和最小表示法差不多的，举一反三啊）
最后推广一下我的博客：
https://www.luogu.org/blog/new2zy/
拜拜~~~ >=<