「RHOI-1」小园香径独徘徊题解

Ecrade_ · 2023-05-15 21:53:43 · 题解

首先考虑仅执行前两种操作可以得到的最小字符串。

一个显然的贪心是，若当前 S 的首字符大于 T 的首字符就执行第二个操作，否则执行第一个操作。不难证明其正确性。

回到原问题。

先将题意转化为：将 S 分成前后两个部分 A,B，对 A 从左到右执行前两种操作，对 B 从右到左执行第三种操作。令对 A 执行第一种操作在 T 中形成的字符串为 C，对 A 执行第二种操作在 T 中形成的字符串为 D。

我们可以将第三种操作视作将 B 不改变顺序地穿插到 C 中的任意位置，即形成一个字符串 E，使得 E 能够恰好划分为两个分别与 B,C 相同的子序列。最终 T 即为 E+D，其中 + 表示字符串的拼接。

以第二个样例中 S=\mathsf{{\color{orange}d}{\color{orange}c}{\color{orange}b}{\color{yellowgreen}c}{\color{orange}a}{\color{yellowgreen}d}{\color{cornflowerblue}b}} 构造出 T=\mathsf{{\color{orange}a}{\color{cornflowerblue}b}{\color{orange}b}{\color{orange}c}{\color{orange}d}{\color{yellowgreen}c}{\color{yellowgreen}d}} 为例，将 S 分为前后两个部分 A=\mathsf{{\color{orange}d}{\color{orange}c}{\color{orange}b}{\color{yellowgreen}c}{\color{orange}a}{\color{yellowgreen}d}},B=\mathsf{{\color{cornflowerblue}b}}，对橙色部分执行第一种操作，对绿色部分执行第二种操作，得到 C=\mathsf{{\color{orange}a}{\color{orange}b}{\color{orange}c}{\color{orange}d}},D=\mathsf{{\color{yellowgreen}c}{\color{yellowgreen}d}}，再将 B 插入 C 中得到 E=\mathsf{{\color{orange}a}{\color{cornflowerblue}b}{\color{orange}b}{\color{orange}c}{\color{orange}d}}，最终 T=E+D=\mathsf{{\color{orange}a}{\color{cornflowerblue}b}{\color{orange}b}{\color{orange}c}{\color{orange}d}{\color{yellowgreen}c}{\color{yellowgreen}d}}。

观察整个 T 的构造流程，我们接下来需要解决三个问题：

若确定了 A，如何构造最优的 C,D？
若确定了 B,C，如何构造最优的 E？
如何划分 A,B？

对于第一个问题，我们一开始已经解决了。形式化地来讲，我们对 A 中所有前缀最小字符进行第一种操作，对剩余字符进行第二种操作，其中前缀最小字符指的是不大于自身之前任意字符的字符。可以观察到，这样形成的 C 一定是个单调不降的字符序列。

对于第二个问题，由于 C 中字符单调不降，故我们依然可以采取一个贪心的策略：若 B 的首字符大于 C 的首字符，则将 C 的首字符加入到 E 的末尾并将 C 的首字符删去，否则将 B 的首字符加入到 E 的末尾并将 B 的首字符删去。

对于第三个问题，暴力枚举 A,B 的划分位置。

按照上述过程模拟，我们便得到了一个 O(n^2) 的做法。

考虑优化。

瓶颈在于枚举 A,B 的划分位置上，考虑能否缩小枚举范围。

不难发现，对 S 中所有前缀最小字符均进行第一种操作一定不劣。也就是说，令 S 中最小字符的最后出现位置为 p，则将 S_p 及其之前的字符都归到 A 中一定不劣。那么此时整个 C 和 D 的一段前缀就确定下来了。

令 S 中 S_{p+1} 记其之后的字符构成的字符串为 X，则我们需要选取 X 的一个后缀作为 B，剩余部分就接在已经确定的 D 的后面。既然 B 最终在 D 前，那么我们希望选出来的 B 的字典序尽可能小。一个自然的想法是直接选取 X 的最小后缀作为 B，但很可惜这是错的。一个简单的反例是 S=\mathsf{{\color{orange}c}{\color{orange}b}{\color{yellowgreen}d}{\color{orange}a}{\color{cornflowerblue}b}{\color{cornflowerblue}c}{\color{cornflowerblue}b}}，此时最优的 B 应当是 \mathsf{{\color{cornflowerblue}b}{\color{cornflowerblue}c}{\color{cornflowerblue}b}}，而不是字典序最小的 \mathsf{{\color{cornflowerblue}b}}。

那么问题出在哪儿呢？出在 “字典序最小” 的条件中包含了对于字符串长度的比较。对于 X 的两个后缀 s,s'\ (|s|<|s'|)，若 \forall 1\le i\le |s| 都有 s_i=s'_i，那么虽然 s 字典序比 s' 小，但若后面加上了 D，s' 却可能比 s 更优。

我们退而求其次，选择 X 中不考虑长度限制的字典序最小的若干后缀。但这样的字符串可能仍旧很多，无法直接模拟。

观察这些后缀的性质。令这些后缀分别为 s_1,s_2,\dots,s_k\ (|s_1|<|s_2|<\dots<|s_k|)，那么 \forall 1\le i<k 都有 s_i 为 s_{i+1} 的一段前缀，即 s_i 为 s_{i+1} 的一个 border，亦即 s_2,s_3,\dots,s_k 为 s_1 的 border。

接下来有两条路可走。

法一

依据这个性质，我们可以利用 s_i 的结果推出 s_{i+1} 的结果。具体地，要想比较 B=s_i 所构造出的 T 和 B=s_{i+1} 所构造出的 T' 的大小，我们可以在 T 的基础上，根据前文的贪心，暴力添加字符直至 B=s_{i+1}。在添加的过程中进行逐位比较，添加完成后，由于剩余的部分构成一段区间，那么直接利用你喜欢的方式比较即可。

时间复杂度瓶颈在于后缀排序。

#include<bits/stdc++.h>
using namespace std;
int t,n,nc,nd,ns,tp,sa[1000009],rnk[1000009],slen[1000009];
char s[1000009],C[1000009],D[1000009],T[1000009],ans[1000009];
inline int read(){
    int s = 0,w = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    return s * w;
}
namespace SAM{
    int tp,tot,cnt = 1,last = 1,tmp[26],hd[2000009],fa[2000009],dy[2000009],id[2000009],len[2000009],pos[2000009],suf[2000009],ch[2000009][26];
    struct st{int x,y;}eg[2000009];
    void addedge(int u,int v){eg[++ tot] = (st){v,hd[u]},hd[u] = tot;}
    void clear(){
        for (int i = 1;i <= cnt;i += 1){
            memset(ch[i],0,sizeof(ch[i]));
            fa[i] = dy[i] = id[i] = len[i] = pos[i] = suf[i] = 0;
        }
        cnt = last = 1;
    }
    void ins(int x,int y){
        int p = last,cur = ++ cnt;
        pos[cur] = y,suf[cur] = 1,len[cur] = len[last] + 1;
        while (p && !ch[p][x]) ch[p][x] = cur,p = fa[p];
        int q = ch[p][x];
        if (!q) fa[cur] = 1;
        else if (len[p] + 1 == len[q]) fa[cur] = q;
        else{
            int r = ++ cnt;
            fa[r] = fa[q],pos[r] = pos[q],len[r] = len[p] + 1;
            memcpy(ch[r],ch[q],sizeof(ch[q]));
            while (p && ch[p][x] == q) ch[p][x] = r,p = fa[p];
            fa[cur] = fa[q] = r;
        }
        last = cur;
    }
    void dfs(int u,bool fl,bool opt){
        if (suf[u]){
            if (opt){
                if (!fl) return;
                slen[++ ns] = n - pos[u] + 1;
            }
            else tp += 1,sa[tp] = pos[u],rnk[pos[u]] = tp;
        }
        for (int i = hd[u];i;i = eg[i].y) dfs(eg[i].x,fl,opt),fl = 0;
    }
    void work(int opt){
        tp = tot = 0;
        for (int i = 0;i < 26;i += 1) tmp[i] = 0;
        for (int i = 1;i <= cnt;i += 1) hd[i] = 0;
        for (int i = 1;i <= cnt;i += 1) dy[i] = T[pos[i] + len[fa[i]]] - 'a',tmp[dy[i]] += 1;
        for (int i = 1;i < 26;i += 1) tmp[i] += tmp[i - 1];
        for (int i = 1;i <= cnt;i += 1) id[tmp[dy[i]] --] = i;
        for (int i = cnt;i >= 1;i -= 1) if (fa[id[i]]) addedge(fa[id[i]],id[i]);
        dfs(1,1,opt);
    }
}
void clear(){
    SAM :: clear();
    nc = nd = ns = tp = 0;
    for (int i = 1;i <= n;i += 1) sa[i] = rnk[i] = slen[i] = 0;
}
int main(){
    t = read();
    while (t --){
        clear(),scanf("%s",s + 1),n = strlen(s + 1);
        int pos = 1;
        for (int i = 1;i <= n;i += 1) if (s[i] <= s[pos]){
            C[++ nc] = s[i];
            for (int j = pos + 1;j < i;j += 1) D[++ nd] = s[j];
            pos = i;
        }
        reverse(C + 1,C + nc + 1);
        for (int i = 1;i <= nc;i += 1) T[i] = C[i];
        for (int i = 1;i <= nd;i += 1) T[i + nc] = D[i];
        for (int i = pos + 1;i <= n;i += 1) T[i] = s[i];
        for (int i = n;i > pos;i -= 1) SAM :: ins(T[i] - 'a',i);
        SAM :: work(1);
        for (int i = pos;i >= 1;i -= 1) SAM :: ins(T[i] - 'a',i);
        SAM :: work(0);
        int fl = 0,res = 0,now = 1,cur = 1,cpos = 1,mnpos = n - slen[ns];
        for (int i = 1;i <= slen[ns];i += 1){
            while (cpos <= nc && T[cpos] < T[mnpos + i]){
                if (!fl && T[cpos] < T[cur]) fl = 1;
                if (!fl && T[cpos] > T[cur]) goto GG;
                cur += 1,cpos += 1;
            }
            if (!fl && T[mnpos + i] < T[cur]) fl = 1;
            if (!fl && T[mnpos + i] > T[cur]) goto GG;
            cur += 1;
            if (i == slen[now]){
                if (fl == 1 || rnk[cpos] < rnk[cur]) cur = cpos,res = slen[now];
                fl = 0,now += 1;
            }
        }
        GG:;
        cpos = 1;
        for (int i = 1;i <= res;i += 1){
            while (cpos <= nc && T[cpos] < T[mnpos + i]) ans[++ tp] = T[cpos ++];
            ans[++ tp] = T[mnpos + i];
        }
        while (cpos <= nc) ans[++ tp] = T[cpos ++];
        for (int i = 1;i <= nd;i += 1) ans[++ tp] = T[nc + i];
        for (int i = pos + 1;i <= n - res;i += 1) ans[++ tp] = T[i];
        for (int i = 1;i <= n;i += 1) putchar(ans[i]);
        puts("");
    }
    return 0;
}

法二

根据 border 的性质，我们可将 |s_1|,|s_2|,\dots,|s_k| 分成 O(\log k) 段等差数列。记有 c 段等差数列，第 i 段由 s_{l_i},s_{l_i+1},\dots,s_{r_i} 构成。

可以根据调整法证明，最优的 B 一定只存在于每段的首两项和末一项，即 s_{l_i},s_{l_i+1},s_{r_i} 之中。枚举这些位置直接模拟即可。

时间复杂度为 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
int t,n,fl,nc,nd,ns,tp,sa[1000009],rnk[1000009],ban[1000009],slen[1000009];
char s[1000009],C[1000009],D[1000009],T[1000009],ans[1000009];
inline int read(){
    int s = 0,w = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
    while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
    return s * w;
}
namespace SAM{
    int tp,tot,cnt = 1,last = 1,tmp[26],hd[2000009],fa[2000009],dy[2000009],id[2000009],len[2000009],pos[2000009],suf[2000009],ch[2000009][26];
    struct st{int x,y;}eg[2000009];
    void addedge(int u,int v){eg[++ tot] = (st){v,hd[u]},hd[u] = tot;}
    void clear(){
        for (int i = 1;i <= cnt;i += 1){
            memset(ch[i],0,sizeof(ch[i]));
            fa[i] = dy[i] = id[i] = len[i] = pos[i] = suf[i] = 0;
        }
        cnt = last = 1;
    }
    void ins(int x,int y){
        int p = last,cur = ++ cnt;
        pos[cur] = y,suf[cur] = 1,len[cur] = len[last] + 1;
        while (p && !ch[p][x]) ch[p][x] = cur,p = fa[p];
        int q = ch[p][x];
        if (!q) fa[cur] = 1;
        else if (len[p] + 1 == len[q]) fa[cur] = q;
        else{
            int r = ++ cnt;
            fa[r] = fa[q],pos[r] = pos[q],len[r] = len[p] + 1;
            memcpy(ch[r],ch[q],sizeof(ch[q]));
            while (p && ch[p][x] == q) ch[p][x] = r,p = fa[p];
            fa[cur] = fa[q] = r;
        }
        last = cur;
    }
    void dfs(int u,bool fl,bool opt){
        if (suf[u]){
            if (opt){
                if (!fl) return;
                slen[++ ns] = n - pos[u] + 1;
            }
            else tp += 1,sa[tp] = pos[u],rnk[pos[u]] = tp;
        }
        for (int i = hd[u];i;i = eg[i].y) dfs(eg[i].x,fl,opt),fl = 0;
    }
    void work(int opt){
        tp = tot = 0;
        for (int i = 0;i < 26;i += 1) tmp[i] = 0;
        for (int i = 1;i <= cnt;i += 1) hd[i] = 0;
        for (int i = 1;i <= cnt;i += 1) dy[i] = T[pos[i] + len[fa[i]]] - 'a',tmp[dy[i]] += 1;
        for (int i = 1;i < 26;i += 1) tmp[i] += tmp[i - 1];
        for (int i = 1;i <= cnt;i += 1) id[tmp[dy[i]] --] = i;
        for (int i = cnt;i >= 1;i -= 1) if (fa[id[i]]) addedge(fa[id[i]],id[i]);
        dfs(1,1,opt);
    }
}
void upd(){
    for (int i = 1;i <= n;i += 1){
        if (ans[i] < T[i]) return;
        if (ans[i] > T[i]){
            for (int j = 1;j <= n;j += 1) ans[j] = T[j];
            return;
        }
    }
}
void simulate(int o){
    int nc = 0,nd = 0,pos = 1;
    for (int i = 1;i <= o;i += 1){
        if (s[i] <= s[pos]) C[++ nc] = s[i],pos = i;
        else D[++ nd] = s[i];
    }
    reverse(C + 1,C + nc + 1);
    int tp = 0,cpos = 1;
    for (int i = o + 1;i <= n;i += 1){
        while (cpos <= nc && C[cpos] < s[i]) T[++ tp] = C[cpos ++];
        T[++ tp] = s[i];
    }
    while (cpos <= nc) T[++ tp] = C[cpos ++];
    for (int i = 1;i <= nd;i += 1) T[++ tp] = D[i];
    if (!fl) for (int i = 1;i <= n;i += 1) ans[i] = T[i];
    else upd();
    fl = 1;
}
void clear(){
    SAM :: clear();
    fl = nc = nd = ns = tp = 0;
    for (int i = 1;i <= n;i += 1) sa[i] = rnk[i] = ban[i] = slen[i] = 0;
}
int main(){
    t = read();
    while (t --){
        clear(),scanf("%s",s + 1),n = strlen(s + 1);
        int pos = 1;
        for (int i = 1;i <= n;i += 1) if (s[i] <= s[pos]){
            C[++ nc] = s[i];
            for (int j = pos + 1;j < i;j += 1) D[++ nd] = s[j];
            pos = i;
        }
        reverse(C + 1,C + nc + 1);
        for (int i = 1;i <= nc;i += 1) T[i] = C[i];
        for (int i = 1;i <= nd;i += 1) T[i + nc] = D[i];
        for (int i = pos + 1;i <= n;i += 1) T[i] = s[i];
        for (int i = n;i > pos;i -= 1) SAM :: ins(T[i] - 'a',i);
        SAM :: work(1);
        for (int i = pos;i >= 1;i -= 1) SAM :: ins(T[i] - 'a',i);
        SAM :: work(0);
        for (int i = 2;i < ns;i += 1) if (slen[i] - slen[i - 1] == slen[i + 1] - slen[i]) ban[i] = 1;
        for (int i = 0;i <= ns;i += 1){
            if (i <= 1 || i == ns || !ban[i - 1] || !ban[i]) simulate(n - slen[i]);
        }
        for (int i = 1;i <= n;i += 1) putchar(ans[i]);
        puts("");
    }
    return 0;
}

「RHOI-1」小园香径独徘徊 题解

法一

法二

「RHOI-1」小园香径独徘徊题解