题解：P16103 [ICPC 2019 NAIPC] Cutting Strings

· · 题解

题意简述

从字符串 s 中删除至多 k 个两两不相交的子串，求剩余字符串的最大字典序。

解题思路

按答案从左到右处理。已经确定的答案前缀保持不动，记尚未处理的原串后缀从位置 pos 开始，剩余删除次数仍为 k。

若 k=0，后面的字符都必须保留，直接追加整个后缀。否则，设当前后缀中的最大字符为 c。可以删除前面较小的字符，让结果以 c 开始，因此答案的下一个字符必须为 c。

不能简单保留第一次出现的 c。例如 ababb 且 k=1，保留第一个 b 会得到 babb，而删除前缀 aba 可以得到更大的 bb。需要一起考虑答案开头能连续保留多少个 c。

将后缀中每个极长的连续 c 段称为一个块。若后缀本身以 c 开始，开头的整块可以直接保留。保留这些字符不消耗删除次数，也不影响后面删除区间的选择；即使原方案删除了这一块，将它补回也仅会在结果开头增加若干个最大字符，因此不会更差。

取走开头免费保留的一块后，其余每个 c 块前面都存在至少一个小于 c 的字符。要将若干块连接成答案开头连续的 c，每保留一块，就需要一次删除操作，删去上一块末尾与当前块开头之间的整段。中间没有保留的 c 块也可以一起删掉。

反过来，任意连接方案都必须删除这些间隔。不同间隔之间隔着保留的字符，不能合并为同一次删除，故连接若干块所需的删除次数恰好等于所选块数。块内没有必要再删字符：保留整个块不会多消耗操作，且能增加开头连续的 c。

设剩余共有 q 个块，长度依次为 b_1,\dots,b_q。

第二种情况中，长度和可能对应多种选择。它们开头连续的 c 数量相同，而最后选中块之后的原串后缀必须原样保留。因此平局的唯一比较对象，就是最后一块后面的整个后缀，而非这一块的位置或它后面的第一个字符。

将块长降序排序，记第 k 大的长度为 t，长度严格大于 t 的块数为 g。取得最大长度和的方案必须选中所有长度大于 t 的块，再从长度等于 t 的块中选出 k-g 个，不能选中更短的块。

由此可以枚举哪一块作为最后选中的块。记最后一个长度大于 t 的块编号为 l，若不存在则令 l=0；记前 j 块中长度等于 t 的块数为 u_j。第 j 块能作为最后一块，当且仅当满足：

j\ge l\land b_j\ge t\land u_j\ge k-g

前两个条件保证所有必须选中的长块都已出现，且当前块本身可以被选中。第三个条件保证所需的等长块数量足够。若当前块长为 t，从前面和当前的等长块中选出 k-g 个并包含当前块；若当前块更长，则它必然是最后一个必须选中的长块。两种情况都能构造出以当前块结尾的最优选择，所以这些条件也充分。

用后缀数组预处理原串所有后缀的字典序排名，在合法的最后一块中，选择块后后缀排名最大的一项。空后缀的排名设为 0，小于任何非空后缀。答案追加长度最大的 k 个块所提供的 c，再追加选定的原串后缀，即可结束。

代码中的 a 保存块长和块后的下标，b 用于排序。lim 对应 t，lst 对应 l；扫描候选块时，sum 从 g 开始累加遇到的等长块数量，所以 sum>=k 对应 u_j\ge k-g。rnk 使用从 1 开始的后缀下标，而字符串下标从 0 开始，因此块后的下标需要加一再查询排名。

预处理每个后缀的最大字符后，每次完整连接所有块都会使剩余后缀的最大字符严格下降。若当前开头的最大字符块已经包含后缀中全部最大字符，也直接进入下一轮。小写字母至多有 26 种，所以块扫描的总开销为 O(|\Sigma|n)。不足以连接所有块的分支至多进入一次，其中排序与倍增后缀数组需要 O(n\log n)，总时间复杂度为 O(|\Sigma|n+n\log n)，空间复杂度为 O(n)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;
const int N=100005;
int sa[N],rnk[N*2],tmp[N*2],c[N],b[N];
pii a[N];
char mx[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int k;
        string s;
        cin>>k>>s;
        int n=s.size();
        mx[n]=0;
        for(int i=n-1;i>=0;i--)mx[i]=max(s[i],mx[i+1]);
        string ans;
        int pos=0;
        while(pos<n)
        {
            if(!k){ans+=s.substr(pos);break;}
            char ch=mx[pos];
            while(pos<n&&s[pos]==ch)ans+=s[pos++];
            int cnt=0;
            for(int i=pos;i<n;i++)
            {
                if(s[i]!=ch)continue;
                int j=i;
                while(i<n&&s[i]==ch)i++;
                cnt++;
                a[cnt]={i-j,i};
                b[cnt]=i-j;
            }
            if(!cnt)continue;
            if(cnt<=k)
            {
                for(int i=1;i<=cnt;i++)ans.append(a[i].first,ch);
                k-=cnt;
                pos=a[cnt].second;
                continue;
            }
            sort(b+1,b+cnt+1,greater<int>());
            for(int i=1;i<=k;i++)ans.append(b[i],ch);
            int lim=b[k],lst=0,sum=0;
            for(int i=1;i<=cnt;i++)
            {
                if(a[i].first<=lim)continue;
                lst=i;
                sum++;
            }
            fill(rnk,rnk+2*n+1,0);
            fill(tmp,tmp+2*n+1,0);
            fill(c,c+27,0);
            for(int i=1;i<=n;i++)c[rnk[i]=s[i-1]-'a'+1]++;
            for(int i=1;i<=26;i++)c[i]+=c[i-1];
            for(int i=n;i>=1;i--)sa[c[rnk[i]]--]=i;
            int m=26;
            for(int i=1;i<n;i<<=1)
            {
                int len=0;
                for(int j=n-i+1;j<=n;j++)tmp[len++]=j;
                for(int j=1;j<=n;j++)if(sa[j]>i)tmp[len++]=sa[j]-i;
                fill(c,c+m+1,0);
                for(int j=0;j<n;j++)c[rnk[tmp[j]]]++;
                for(int j=1;j<=m;j++)c[j]+=c[j-1];
                for(int j=n-1;j>=0;j--)sa[c[rnk[tmp[j]]]--]=tmp[j];
                copy(rnk,rnk+n+1,tmp);
                m=0;
                for(int j=1;j<=n;j++)
                {
                    if(j==1||tmp[sa[j]]!=tmp[sa[j-1]]||tmp[sa[j]+i]!=tmp[sa[j-1]+i])m++;
                    rnk[sa[j]]=m;
                }
                if(m==n)break;
            }
            int res=-1;
            for(int i=1;i<=cnt;i++)
            {
                if(a[i].first==lim)sum++;
                if(i<lst||a[i].first<lim||sum<k)continue;
                if(res==-1||rnk[a[i].second+1]>rnk[res+1])res=a[i].second;
            }
            ans+=s.substr(res);
            break;
        }
        cout<<ans<<'\n';
    }
    return 0;
}