【学习笔记】P9348 小园香径独徘徊

发布时间:2023年12月18日

题目传送门

yly说要有题解,于是就有了这篇博客。

大佬博客,做法基本是照搬的。

考虑枚举分解点 p p p,对 S [ 1 : p ? 1 ] S[1:p-1] S[1:p?1]执行操作 1 , 2 1,2 1,2,对 S [ p : n ] S[p:n] S[p:n]执行操作 3 3 3

考虑 S [ 1 : p ] S[1:p] S[1:p],从左往右遍历字符串,如果当前字符小于等于之前遍历过的最小字符,那么执行操作 1 1 1;否则执行操作 2 2 2。换句话说,对所有的前缀最小值执行操作 1 1 1,否则执行操作 2 2 2。类似的结论:[ARC153E] Deque Minimization

还有一个结论,记最后一个前缀最小值的下标为 q q q,则分界点一定在 q q q之后,即 p > q p>q p>q,这是如果不这么做,那么最终串的前缀(开头)最小字符的数目会减少。

现在,将 [ 1 : q ] [1:q] [1:q]中的前缀最小值提取出来并翻转,记作 T [ 1 : m ] T[1:m] T[1:m],直接插入到末尾的记作 T [ m + 1 : q ] T[m+1:q] T[m+1:q],并且 T [ q + 1 : n ] = S [ q + 1 : n ] T[q+1:n]=S[q+1:n] T[q+1:n]=S[q+1:n]。那么我们需要将 T [ 1 : m ] {T}[1:m] T[1:m] T [ p : n ] {T}[p:n] T[p:n]归并起来( p > q p>q p>q),使得字典序最小。

这个问题本身只能 D P DP DP求解,但是注意到题目的特殊性质: T [ 1 : m ] T[1:m] T[1:m]是单调不减的,因此我们对于 T [ p : n ] T[p:n] T[p:n]中的每个字符,依次插入 T [ 1 : m ] T[1:m] T[1:m]中,即找到 T [ 1 : m ] T[1:m] T[1:m]中小于这个字符的最大的位置,插入到这个位置之后即可(注意保证插入的位置必须单调不减)。

这样我们得到了 O ( n 2 ) O(n^2) O(n2)的解法。

发现慢的原因在于枚举分界点,一个简单的想法是取 T [ q + 1 : n ] T[q+1:n] T[q+1:n]的最小后缀,但是这样会WA。发现一个更长的后缀可能更优的条件是:所有字典序比它小的后缀一定是这个后缀的前缀,因此按长度从小到大遍历所有可能的后缀,这段前缀的插入位置已经被计算过了,只需增量构造即可。

细节有一点点多,采用的是逐位比较的方式(稍微有一点点抽象),最后要对两个后缀比大小(辅助检查,字符串常规操作)。注意这些操作都是在 T T T串上完成的。

刚开始Lyndon+哈希被卡了。遂换成了sa(对 T T T串做后缀排序)。

复杂度 O ( n log ? n ) O(n\log n) O(nlogn)

有人对同一个串建了两次sa,喜提两倍常数。

ps:貌似不需要写ST表,但是懒得改了。

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e6+5;
int T,n;
string str,str1,str2,str3,res;
int x[N],y[N],z[N],c[N],sa[N],h[N],f[25][N],m,cnt;
void build(string&s){
    n=s.size();
    m=26;
    for(int i=1;i<=n<<1;i++)z[i]=0;
    for(int i=1;i<=n;i++)c[x[i]=s[i-1]-'a'+1]++;
    for(int i=1;i<=m;i++)c[i]+=c[i-1];
    for(int i=1;i<=n;i++)sa[c[x[i]]--]=i;
    for(int i=1;i<=m;i++)c[i]=0;
    for(int len=1;len<=n;len<<=1){
        cnt=0;
        for(int i=n-len+1;i<=n;i++)y[++cnt]=i;
        for(int i=1;i<=n;i++)if(sa[i]>len)y[++cnt]=sa[i]-len;
        for(int i=1;i<=n;i++)c[x[i]]++;
        for(int i=1;i<=m;i++)c[i]+=c[i-1];
        for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i];
        for(int i=1;i<=m;i++)c[i]=0;
        for(int i=1;i<=n;i++)z[i]=x[i];
        x[sa[1]]=1;cnt=1;
        for(int i=2;i<=n;i++) {
            if(z[sa[i]]!=z[sa[i-1]]||z[sa[i]+len]!=z[sa[i-1]+len]){
                cnt++;
            }
            x[sa[i]]=cnt;
        }
        m=cnt;
    }
    int tmp=0;
    for(int i=1;i<=n;i++){
        if(x[i]==1){
            tmp=0;
            continue;
        }
        int k=max(0,tmp-1),j=sa[x[i]-1];
        while(i+k<=n&&j+k<=n&&s[i+k-1]==s[j+k-1])k++;
        h[x[i]]=tmp=k;
    }
    for(int i=1;i<=n;i++)f[0][i]=h[i];
    for(int i=1;i<=__lg(n);i++){
        for(int j=1;j<=n-(1<<i)+1;j++){
            f[i][j]=min(f[i-1][j],f[i-1][j+(1<<i-1)]);
        }
    }
}
int lcp(int l,int r){
    l++,r++;if(l>n||r>n)return 0;if(l==r)return n-l+1;
    if((l=x[l])>(r=x[r]))swap(l,r);
    int k=__lg(r-l++);
    return min(f[k][l],f[k][r-(1<<k)+1]);
}
int sol(int p){
    build(str3);
    int it=0,it2=0,q2=n,q3=n,len=0,tp=str1.size();
    for(int _i=1;_i<=n;_i++){
        int i=sa[_i]-1;
        if(i<=p)continue;
        if(n-i>=len&&lcp(q2,i)>=len){
            int ok=-1;
            for(int j=i+len;j<n;j++){
                while(it<tp&&str3[it]<str3[j]){
                    if(str3[it]!=str3[it2]&&ok==-1)ok=(str3[it]<str3[it2]);
                    it++,it2++;
                }
                if(str3[j]!=str3[it2]&&ok==-1)ok=(str3[j]<str3[it2]);
                it2++;
            }
            if(~ok){
                if(ok)it2=it,q3=i;
                else break;
            }
            else{
                int tmp=min(lcp(it,it2),i-it);
                if(tmp!=i-it&&str3[it+tmp]<str3[it2+tmp])it2=it,q3=i;
            }
            q2=i,len=n-q2;
        }
        else{
            break;
        }
    }
    return q3;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>str,n=str.size();
        str1.clear(),str2.clear();
        int p=-1;char c='{';
        for(int i=0;i<n;i++){
            if(str[i]<=c)c=str[i],p=i,str1+=str[i];
            else str2+=str[i];
        }
        reverse(str1.begin(),str1.end()),str3=str1+str2;
        int q=sol(p);
        res.clear();
        int it=0,tp=str1.size();
        for(int i=q;i<n;i++){
            while(it!=tp&&str3[it]<str3[i])res+=str3[it++];
            res+=str3[i];
        }while(it!=tp)res+=str3[it++];
        c='{';
        for(int i=0;i<p;i++){
            if(str[i]>c)res+=str[i];
            c=min(c,str[i]);
        }
        for(int i=p+1;i<q;i++)res+=str3[i];
        cout<<res<<"\n";
    }
}
文章来源:https://blog.csdn.net/cqbzlydd/article/details/135055103
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。