题解 P1368 【工艺】
硫代硫酸钠
·
·
题解
估计很多人都是用SAM写的吧.
其实本题有O(n)的做法,即最小表示法.
最小表示法的优点:
$2.$ 好写
这里关于SAM的复杂度是$O(n\cdot |S|)$的,如果这个题出成|S|和n同阶SAM就凉了,所以SAM毕竟还是不是正解.
缺点是不具有扩展性.
我们维护两个指针i， j。初始化时i指向0, j指向1。
检验s[i+k] 与 s[j+k] 对应的字符是否相等
如果相等,就一直检查(除非整个串由且只由一种字符构成)
如果不相等:
1.s[i+k] > s[j+k]
此时i到i+k都不会作为开头存在.
2.s[i+k] < s[j+k]
此时j到j+k都不会作为开头存在.
最后min(i,j)就是答案了.
```
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<stack>
#include<queue>
#include<map>
#define size 600010
#define ll long long
#define db double
#define il inline
#define rint register int
#define gc getchar()
#define rep(i,s,n) for (register int i=s;i<=n;i++)
#ifdef WIN32
#define ld "%I64d"
#else
#define ld "%lld"
#endif
using namespace std;
il ll r()
{
char c; ll x,f=1;
for (c=gc;!isdigit(c);c=gc) if (c=='-') f=-1; x=c-'0';
for (c=gc;isdigit(c);c=gc) x=x*10+c-'0'; return x*f;
}
int n,a[size];
int min_representation()
{
int i=0,j=1,k=0;
while (i<n&&j<n&&k<n)
{
int t=a[(i+k)%n]-a[(j+k)%n];
if (t==0) k++;
else
{
if (t>0) i+=k+1;
else j+=k+1;
if (i==j) j++; k=0;
}
}
return min(i,j);
}
int main()
{
n=r(); rep(i,0,n-1) a[i]=r(),a[i+n]=a[i];
int t=min_representation();
rep(i,t,t+n-1) printf("%d ",a[i]);
return 0;
}
```