都5202年了你的最小表示法不会还跑得这么慢吧

· · 算法·理论

文章标题中的 5202 采用的是最大表示法，实际是什么我忘了。

暴力

oi-wiki 的代码。

这里换一种写法，对下文帮助更大。

#include<bits/stdc++.h>
using namespace std;
int n,a[600005];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    int ans=1;
    for(int i=2;i<=n;i++){
        for(int k=0;k<n;k++){
            if(a[ans+k]>a[i+k]){
                ans=i;
                break;
            }
            if(a[ans+k]<a[i+k])break;
        }
    }
    for(int i=ans;i<ans+n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

一般做法

这里讲的不是我的做法，讲的是最常见的 \operatorname{O}(n) 做法，可以跳过。

这里插入一条广告。

以这道题为例：【模板】最小表示法。

考虑将输入的序列破环为链，并定义 S_x 表示从位置 x 开始的长度为 n 的连续段。

双指针枚举 i,j 表示当前正在判断 i 的大小和 j 的大小，其中 i 和 j 是两个可能为最小表示法的候选值，暴力比较 S_i 和 S_j 哪个更大，不妨设 a_{i+k} 和 a_{j+k} 不同，我们不妨设 a_{i+k}>a_{j+k}（若相反，交换 i,j 即可，但实现时无需交换），那么 S_i 不能成为最小表示法，那么可以证明，对于 \forall x\in [0,k]，S_{i+x} 一定也不是最小表示法，故直接令 i\gets i+k+1，则时间复杂度为 \operatorname{O}(n)。

给出对于 \forall x\in [0,k]，S_x 一定也不是最小表示法的证明。

对于 x\in [0,k]，那么考虑比较 S_{i+x} 与 S_{j+x}，那么由于 i+k>i+x 且对于 \forall y\in[x,k)，都有 a_{i+y}=a_{j+y}，那么 S_{i+x}>S_{j+x}，所以 S_{i+x} 不是最小表示法。

我只有 Necklace 的代码（以前写的）：

#include<bits/stdc++.h>
using namespace std;
#define int long long
string get(string s){
    int n=s.size();
    if(n==1)return s;
    s=" "+s+s;
    int i=1,j=2;
    while(i<=n&&j<=n){
        int k=0;
        while(k<n&&s[i+k]==s[j+k])k++;
        if(k==n)break;
        if(s[i+k]<s[j+k])swap(i,j);
        i+=k+1;
        if(i==j)i++;
    }
    return s.substr(min(i,j),n);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    string s,t;
    cin>>s>>t;
    if(get(s)==get(t)){
        cout<<"Yes\n"<<get(s);
    }else{
        cout<<"No\n";
    }
    return 0;
}

我的做法

感觉没学过最小表示法的情况下更容易想到这个做法？

将输入的序列破环为链之后，令 a_{2\times n}=+\inf，考虑优化暴力，令 j 为当前的答案，i 从 2 遍历到 n，那么需要比较 S_j 与 S_i（定义见上文），不妨设 a_{j+k}\neq a_{i+k}：

答案就是 j。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[600005];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];
    }
    a[2*n]=31;
    int i=2,j=1;
    while(i<=n){
        int k=0;
        while(k<n&&a[i+k]==a[j+k])k++;
        if(a[i+k]<a[j+k])j=i,i++;
        else i+=k+1;
    }
    for(int i=j;i<j+n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}

然后发现和最优解差远了，然后我就 copy 了最优解季军的快读快写，就拿到 rk1 了。