题解 CF594E 【Cutting the Line】

wucstdio · 2020-02-17 16:31:05 · 题解

部分几乎全部内容摘抄自 zzy 的解题报告，orz zzy。

题目来源

IOI2020 集训队作业中 AC 人数最少的一道，毒瘤字符串。

截至 2020 年 2 月 17 日的统计：

注：一共有 70 个人，所有作业题平均 AC 数量在 40 以上。

题目大意

给定一个长度为 n 的字符串 S，你需要把它划分成至多 k 段，也就是使得 S=s_1s_2\dots s_k，然后决定每一段翻转或者不翻转，最后再顺次拼接得到 T，求字典序最小的 T。

数据范围

预知识

符号含义：

一、\text{Lyndon} 分解

我们定义一个串是 \text{Lyndon} 串，当且仅当这个串的最小后缀就是这个串本身。

该命题等价于这个串是它的所有循环表示中字典序最小的。

引理 1：如果 u 和 v 都是 \text{Lyndon} 串并且 u<v，则 uv 也是 \text{Lyndon} 串。

证明：

1、若 \operatorname{len}(u)\ge\operatorname{len}(v)

这时，u 和 v 这两个串在 \operatorname{len}(v) 之前就出现了不同的字符，所以有 v>uv，又因为 v 是 \text{Lyndon} 串，所以 v 的所有后缀都大于 v，所以 uv 的所有后缀都大于 uv，故 uv 是 \text{Lyndon} 串。

2、若 \operatorname{len}(u)<\operatorname{len}(v)

若 u 不是 v 的前缀，那么有 v>uv，得证。

若 u 是 v 的前缀，那么如果 v<uv，则必有 v[\operatorname{len}(u)+1:]<v（也就是各自去掉了前 |u| 个字符），矛盾。

我们定义一个串 S 的 \text{Lyndon} 分解为一个字符串序列 A_1,A_2,\dots,A_m，满足：

可以证明这种划分存在且唯一。

存在性证明

初始令 m=|S| 并且 A_i=S[i]，然后每次不断找到 A_i<A_{i+1} 并且合并为一个串。最后一定能使得所有的 A_i\ge A_{i+1}。

唯一性证明

假设对于字符串 S 存在两个不同的 \text{Lyndon} 分解：

不妨设 \operatorname{len}(A_{i+1})>\operatorname{len}(A^\prime_{i+1})。

观察 A_{i+1} 在第二种分解中的对应情况。假设 A_{i+1}=A^\prime_{i+1}A^\prime_{i+2}\cdots A^\prime_{k}+(A^\prime_{k+1}[:l])。

那么由 \text{Lyndon} 串的性质可知：

矛盾。

引理2：若字符串 v 和字符 c 满足 vc 是某个 \text{Lyndon} 串的前缀，则对于字符 d>c 有 vd 是 \text{Lyndon} 串。

证明：

设该 \text{Lyndon} 串为 v+c+t。

则 \forall i \in [2,|v|],v[i:]+c+t>v+c+t，也就是说 v[i:]+c\ge v。

所以 v[i:]+d>v[i:]+c\ge v。

同时因为 c>v[1]，我们有 d>c>v[1]>v。

故 v+d 是一个 \text{Lyndon} 串。

\text{Duval} 算法

这个算法可以在 O(n) 时间复杂度，O(1) 空间复杂度内求出一个串的 \text{Lyndon} 分解。

该算法中我们仅需维护三个变量 i,j,k。

维持一个循环不变式：

• s[i,k-1]=t^h+v(h>1)$ 是没有固定的分解，满足 $t$ 是 $\text{Lyndon}$ 串，且 $v$ 是 $t$ 的可为空的不等于 $t$ 的前缀，且有 $s_g>s[i,k-1]

如下图：

当前读入的字符是 s[k]，令 j=k-|t|。

分三种情况讨论：

• 当 s[k]=s[j] 时，直接 k\leftarrow k+1,j\leftarrow j+1，周期 k-j 继续保持
• 当 s[k]>s[j] 时，由引理 2 可知 v+s[k] 是 \text{Lyndon} 串，由于 \text{Lyndon} 分解需要满足 s_i\ge s_{i+1}，所以不断向前合并，最终整个 t^h+v+s[k] 形成了一个新的 \text{Lyndon} 串。
• 当 s[k]<s[j] 时，t^h 的分解被固定下来，算法从 v 的开头处重新开始。

复杂度分析：i 只会单调往右移动，同时 k 每次移动的距离不会超过 i 移动的距离，所以时间复杂度是 O(n) 的。

代码如下（刚贡献的P6129）：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[5000005];
int n,ans;
int main()
{
    scanf("%s",s+1);
    n=(int)strlen(s+1);
    for(int i=1;i<=n;)
    {
        int j=i,k=i+1;//初始化
        while(k<=n&&s[j]<=s[k])
        {
            if(s[j]<s[k])j=i;//合并为一整个
            else j++;//保持循环不变式
            k++;
        }
        while(i<=j)//从v的开头继续
        {
            ans^=i+k-j-1;
            i+=k-j;
        }
    }
    printf("%d\n",ans);
    return 0;
}

二、扩展 KMP / Z-algorithm

这个算法可以在 O(n) 的时间复杂度内求出一个串的所有后缀和这个串的LCP，在思路上和 manacher 有想通之处。

我们设 z_i 表示 s[i:] 和 s 的 LCP 长度。注意在这里要满足 i\ge 2。

我们设 [i,i+z_i-1] 为第 i 个位置的 Z-box。我们记录当前右端点最靠右的那个 Z-box 为 [l,r]。

假设现在要求出 z_i。分两种情况讨论：

• 若 i>r，那么令 l=r=i，暴力向后匹配。
• 否则，令 k=z_i-l+1，则如果 z_k< r-i+1，就直接让 z_i=z_k，否则先让 z_i=r-i+1，然后暴力匹配。

由于 r 只会单调往右，所以时间复杂度也是 O(n)。

再附一张图：

代码：

int l=0,r=0;
for(int i=2;i<=n;i++)
{
    if(i>r)
    {
        l=r=i;
        while(r<=n&&s[r-l+1]==s[r])r++;
        z[i]=r-l,r--;
    }
    else
    {
        int k=i-l;
        if(z[k]<r-i+1)z[i]=z[k];
        else
        {
            l=i;
            while(r<=n&&s[r-l+1]==s[r])r++;
            z[i]=r-l,r--;
        }
    }
}

解题过程

令 n=|S|。

Part 1：k=n

当 k=n 的时候，我们注意到不需要考虑分割数量的限制。

注意到，如果其中有一个子串没有翻转，那么我们可以把这个子串进一步分割成单个字符，并且每一个字符都翻转（因为单个字符所以是否翻转无影响），也就是说，一定存在一个最优解，满足划分出来的每一段都进行了翻转。

我们用 S^r 表示 S 的反串，则问题等价于每次从 S^r 中截取一个后缀并且拼接在当前字符串之后，直到 S^r 为空。

引理 3：一个字符串的最小后缀在这个字符串中出现的位置不交

证明：设最小后缀为 A，如果 A 出现的位置有交，则 A 必定有一个前缀等于后缀，那么 A 的那个后缀的字典序就要小于 A，我们就找到了一个更小的后缀，矛盾。

我们先找到 S^r 的最小后缀，假设它为 A，那么为了让最后得到的串字典序尽可能小，我们必然想使得 T 的开头出现尽可能多的 A。

可以发现，我们当前操作把后缀 A 拿出来一定不会让答案变劣。

至此，对于 k=n 的情况，我们已经有了思路：只需要每次取 S^r 的字典序最小的后缀，得到的 T 就是字典序最小的。

考虑 \text{Lyndon} 分解的性质。由于 s_m 是 \text{Lyndon} 串，并且对于任意 i<m 有 s_m\le s_i，所以 s_m 就是字典序最小的后缀。

做一遍 \text{Lyndon} 分解，时间复杂度 O(n)。

Part 2: k\neq n

当 k 变小的时候，我们不能随心所欲地进行分割，需要尽可能节约操作次数。

注意到，某些操作是可以合并的：

• 如果连续两次截取的字符串相同，那么可以合为一次。
• 如果连续两次截取的字符串都为回文串，那么可以合为一次。

第一条很简单，关于第二条，别忘了在原问题中我们是可以对字符串进行翻转的。

让 T 的开头出现尽可能多的 A，这个原则没变。我们把 S^r 中所有的 A 提出来并把 S^r 写成下面这种形式：

其中 s_0,s_1,\dots,s_{m-1} 是字符串序列，其中 s_1,s_2,\dots,s_{m-1} 不能为空串，c_1,c_2,\dots,c_m 是正整数序列。

case 1：k\ge 3

注意到，如果这个时候我们取的是 c_mA，那么至少可以使得开头出现 c_m+\max_{i=1}^{m-1}c_i 个 A，而如果在别的位置分割，无论如何不可能出现这些个 A。

所以此时就是取最后的一段 c_mA。

但是我们很快找到了一组反例：S^r=\text{efcdbbbaaa},k=3。

此时，A=\text{``a''},S=\text{``efcdbbb''}+3A。

如果我们第一次把 3A 分割出来了，那么问题变成了 S=\text{``efcdbbb''},k=2，最终得到的 T 最优是 \text{``aaabbbdcef''}。

而如果我们第一次截取的是 \text{``bbbaaa''} 并且将它翻转，那么可以得到 T=\text{``aaabbbcdef''}，显然后者才是最优解。

究其原因，我们发现此时 \text{``aaa''} 和 \text{``bbb''} 都是回文串，而两次都是回文串的话可以合并为一次。

由于一个串的最小后缀除非长度为 1 否则不可能是回文（要不然直接拿最后一个字符当后缀就更优了），所以发生上面这种情况当且仅当 A 和截取后的 S^r 的最小后缀长度都是 1。特判这种情况。

在具体实现上，在 \text{Lyndon} 分解的过程中，先把 S^r 末尾所有相等的 \text{Lyndon} 串（设它们是 s_k,s_{k+1},\cdots,s_m）合并并且将其添加到 T 的末尾，然后如果 s_m 和 s_{k-1} 长度都是 1 就不消耗步数，否则让 k-1。

case 2：k\le 2

证明：如下图：

我们发现 SB_i 前面出现了两个 t，而 t=B_i=A_i^{k_i}，这显然矛盾。

定理 3 告诉我们，SB_p,SB_{p+1},\dots,SB_m 这些串一定满足后一个长度不大于前一个的 1\over 2，所以至多只会有 O(\log n) 个。

枚举 O(\log n) 个断点，然后二分+哈希比较大小，这一部分的时间复杂度可以做到 O(\log^2n)。

继续分析性质

首先假设 SB_i 比 SB_{i-1} 更优秀。

再来一张大图：

直线表示平移，曲线表示翻转。

看下面两个，由于 SB_i 比 SB_{i-1} 优秀，所以 X^r<Y。

再看上面两个，由于 X^r<Y，所以我们就可以直接得出 SB_i 比 SB_{i-2} 优秀。

换句话说，我们只需要找到最大的 q，满足 SB_q 比 SB_{q-1} 优秀，那么令 t_1=SB_q 就是答案。

由于一次比较是 O(\operatorname{len}(SB_i)) 的，所以我们从 SB_m 往前一个串一个串暴力比较，时间复杂度就是 O(n)，因此暴力算几项就完事了！!1

至此，我们就得到一个非常优美的算法 2了：

步骤 1：特判 k=1，并且将 S 翻转得到 S^r，对 S^r 进行 \text{Lyndon} 分解。

步骤 2：如果 k\ge 3，则每次截取最后一段 B_m，如果 A_m 和 S_{m-1} 长度都是 1 则不消耗步数。

步骤 3：如果 k=2，则进行分类讨论：

• 两次均翻转：答案即为 S。
• 两次均不翻转：答案即为 S^r 的最小表示。
• 第一次翻转，第二次不翻转：用 KMP 算法实现查询 LCP。
• 第一次不翻转，第二次翻转：暴力比较求出最后一个 SB_q 比 SB_{q-1} 优秀，则 t_1=SB_q 就是答案。

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

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char s[10000005],t[5000005],t1[5000005],t2[5000005],t3[5000005],t4[5000005];
int n,k,m,nowl,z[10000005],A[5000005],l[5000005];
void extend(char*s,int l)//在t串之后新加入s[:l-1]
{
    for(int i=0;i<l;i++)t[++nowl]=s[i];
}
void solve1(int n)//两段都翻转，直接就是原串
{
    for(int i=1;i<=n;i++)t1[i]=s[n-i+1];
}
void solve2(int n)//两段都不翻转，最小表示法
{
    for(int i=n+1;i<=2*n;i++)s[i]=s[i-n];
    int i=1,j=2,k=0;
    while(i<=n&&j<=n&&k<n)
    {
        if(s[i+k]==s[j+k])k++;
        else if(s[i+k]<s[j+k])j+=k+1,k=0;
        else i+=k+1,k=0;
        if(i==j)j++;
    }
    for(int x=0;x<n;x++)t2[x+1]=s[min(i,j)+x];
}
void solve3(int n)//第一段翻转第二段不翻转，扩展 KMP
{
    for(int i=n+1;i<=2*n;i++)s[i]=s[n-(i-n)+1];
    n*=2;
    z[1]=n;
    int l=1,r=1;
    for(int i=2;i<=n;i++)
    {
        if(r<i)
        {
            l=r=i;
            while(r<=n&&s[r]==s[r-l+1])r++;
            z[i]=r-l;
            r--;
        }
        else
        {
            if(z[i-l+1]<r-i+1)z[i]=z[i-l+1];
            else
            {
                l=i;
                while(r<=n&&s[r]==s[r-l+1])r++;
                z[i]=r-l;
                r--;
            }
        }
    }//以上为扩展KMP算法
    n/=2;
    int j=n+1;
    for(int i=n;i>=1;i--)
    {
        int l=i,r=j-1;
        l=n-l+1,r=n-r+1;
        int len=z[r+n];
        if(len<l-r+1)
        {
            if(s[len+1]>s[j-len-1])j=i;
        }
        else
        {
            len=j-i;
            l=len+1,r=j-1;
            if(s[z[l]+1]<s[l+z[l]])j=i;
        }
    }
    int tot=0;
    for(int i=n;i>=j;i--)t3[++tot]=s[i];
    for(int i=1;i<j;i++)t3[++tot]=s[i];
}
void solve4(int n)//第一次不翻转，第二次翻转，暴力比较
{
    int p=m;
    while((A[p+1]-A[p])*2<=(A[p]-A[p-1]))
    {
        bool flag=0;
        for(int i=A[p]-1;i>=A[p-1];i--)
        {
            if(s[i]<s[n-i+A[p-1]])
            {
                flag=1;
                break;
            }
            if(s[i]>s[n-i+A[p-1]])break;
        }
        if(flag)break;
        p--;
    }
    p=A[p];
    int tot=0;
    for(int i=p;i<=n;i++)t4[++tot]=s[i];
    for(int i=p-1;i>=1;i--)t4[++tot]=s[i];
}
void update(char*t1,char*t2,int n)//取字典序最小
{
    for(int i=1;i<=n;i++)
    {
        if(t1[i]<t2[i])return;
        if(t2[i]<t1[i])break;
    }
    for(int i=1;i<=n;i++)t1[i]=t2[i];
}
void solve(int n)
{
    solve1(n);
    solve2(n);
    solve3(n);
    solve4(n);
    update(t1,t2,n);
    update(t1,t3,n);
    update(t1,t4,n);
    extend(t1+1,n);
}
int main()
{
    scanf("%s",s+1);
    n=(int)strlen(s+1);
    scanf("%d",&k);
    for(int i=1;i*2<=n;i++)swap(s[i],s[n-i+1]);//取反串
    if(k==1)//特判k=1
    {
        for(int i=1;i<=n;i++)t[i]=s[n-i+1];
        for(int i=1;i<=n;i++)
        {
            if(s[i]<t[i])
            {
                printf("%s\n",s+1);
                return 0;
            }
            if(s[i]>t[i])
            {
                printf("%s\n",t+1);
                return 0;
            }
        }
        printf("%s\n",s+1);
        return 0;
    }
    for(int i=1;i<=n;)//Lyndon分解
    {
        int j=i,k=i+1;
        while(s[j]<=s[k])
        {
            if(s[j]<s[k])j=i;
            else j++;
            k++;
        }
        A[++m]=i;
        l[m]=k-j;
        while(i<=j)i+=k-j;
    }
    A[m+1]=n+1;
    while(m&&k>=3)//当k>=3时
    {
        extend(s+A[m],A[m+1]-A[m]);
        if(l[m]!=1||l[m-1]!=1)k--;
        m--;
    }
    if(!m)
    {
        printf("%s\n",t+1);
        return 0;
    }
    solve(A[m+1]-1);//当k=2时
    printf("%s\n",t+1);
    return 0;
}

总结

本道题涉及到了后缀自动机，\text{Lyndon} 分解，扩展 KMP，最小表示法等等多种字符串冷门算法，综合考察了选手对前沿字符串算法的掌握能力、调试代码能力和肝脏承受能力，难度适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。给出题人点赞！