题解 洛谷P6095 [JSOI2015]串分割

后缀数组 + 二分练习

---

题意

给定首位相接的数字串 $s$ ，将其划分为 $k$ 段，使得 $k$ 段所表示的数字中最大的数最小，求出最大数。
其中 $3 \leq n \leq 2 \cdot 10^5, 2 \leq k \leq n$ 。

思路

观察很容易发现最终分成的 $k$ 段数字串的长度只可能是 $\lceil \frac{n}{k} \rceil$ 或者 $\lfloor \frac{n}{k} \rfloor$ 。可以反证，若最优解存在两个相邻数字串的长度之差大于等于 $2$ ，显然可以将较长串划分一个数字给较短串，最大值一定不会变大。
且观察到要求最大数字尽可能小，考虑可以二分答案值。从而将问题转换为了判定问题 $\rightarrow$ 即判定能否将给定串分成不超过 $k$ 份使得每一份表示的数都小于等于二分求得的数，具体操作如下。
给定的数字串是一个环，首先想到断环成链，我们考虑枚举断点，再从断开处开始贪心地分割，每次尽可能分割出 $\lceil \frac{n}{k} \rceil$ 长度的字符，如果分割出的数字串大于二分值则分割 $\lceil \frac{n}{k} \rceil - 1$ 个字符，最后判断 $k$ 次分割能否将串 $s$ 分完。这样总共枚举 $n$ 个断点，每次判断 $k$ 次，判断复杂度是 $O(n \cdot k)$ 的，但考虑存在重复分割的情况，实际上只需要枚举前 $\lceil \frac{n}{k} \rceil$ 个断点就可以了，总复杂度为 $O(\frac{n}{k} \cdot k) = O(n)$ 。
考虑为什么这样贪心是对的，假设我当前操作分割出了 $\lceil \frac{n}{k} \rceil$ 个数字，但因此下次操作只能分出 $\lceil \frac{n}{k} \rceil - 1$ 个，这样两次分割的总长度与我这一次分割 $\lceil \frac{n}{k} \rceil - 1$ 个，下一次分割$\lceil \frac{n}{k} \rceil$ 个（分割 $\lceil \frac{n}{k} \rceil - 1$ 个的最优情况）的总长度相同，若当前分割之后下一次还能继续分 $\lceil \frac{n}{k} \rceil$ 个，结果就更优了，所以贪心分割是正确的。
考虑实现，最终的答案一定是 $s$ 的一段子串，我们将串 $s$ 复制一份为 $s' = s + s$ ，求出 $s'$ 的 $SA$ ，我们二分答案在 $SA$ 中的排名 $p$ ，单次判断枚举 $s'$ 的前 $\lceil \frac{n}{k} \rceil$ 个点为起点，判断当前起点往后 $\lceil \frac{n}{k} \rceil$ 长度的串与二分对应串的字典序与 $lcp$ 长度，满足则跳，最后判断 $k$ 次操作之后的终点位置减去起点位置是否大于等于 $n$ 即可。
二分加判断的总复杂度为 $O(n \cdot logn)$ 。

代码

注意数组大小为 $n$ 的两倍。

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

using ll=long long;

constexpr int N=4e5+5;

int n,k,len;
struct SA{
    int n,m;
    char s[N];
    int sa[N],rk[N],height[N],h[N];
    int minn[21][N],lg[N];
    void init(int _n,int _m){
        n=_n;
        m=_m;
    }
    void buildsa(){
        static int oldrk[N<<1],id[N],px[N],cnt[N];
        int i,p,w;
        for(i=1;i<=m+1;i++) cnt[i]=0;
        for(i=1;i<=n+1;++i) sa[i]=rk[i]=id[i]=px[i]=0;
        for(i=1;i<=n*2;i++) oldrk[i]=0;
        for(i=1;i<=n;++i) ++cnt[rk[i]=(s[i]-'0')];
        for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;
        for(w=1;;w<<=1,m=p){
            for(p=0,i=n;i>n-w;--i) id[++p]=i;
            for(i=1;i<=n;++i)
            if(sa[i]>w) id[++p]=sa[i]-w;
            for(i=1;i<=m;i++) cnt[i]=0;
            for(i=1;i<=n;++i) ++cnt[px[i]=rk[id[i]]];
            for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
            for(i=n;i>=1;--i) sa[cnt[px[i]]--]=id[i];
            for(i=1;i<=n;i++) oldrk[i]=rk[i];
            for(p=0,i=1;i<=n;++i)
            rk[sa[i]]=(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])?p:++p;
            if(p==n){
                for(i=1;i<=n;++i) sa[rk[i]]=i;
                break;
            }
        }
    }
    void buildheight(){
        for(int i=1;i<=n+1;++i) height[i]=h[i]=0;
        int k=0;
        for(int i=1;i<=n;i++){
            if(rk[i]==1) continue;
            if(k) --k;
            int j=sa[rk[i]-1];
            while(j+k<=n&&i+k<=n&&s[i+k]==s[j+k]) k++;
            height[rk[i]]=k;
        }
        for(int i=1;i<=n;i++) h[i]=height[rk[i]];
        for(int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
        for(int i=1;i<=n;i++) minn[0][i]=height[i];
        for(int j=1;(1<<j)<=n;j++)
            for(int i=1;i+(1<<j)-1<=n;i++) minn[j][i]=min(minn[j-1][i],minn[j-1][i+(1<<(j-1))]);
    }
    int get_lcp(int l,int r){
        if(l==r) return n-l+1;
        l=rk[l],r=rk[r];
        if(l>r) swap(l,r);
        l++;
        int k=lg[r-l+1];
        return min(minn[k][l],minn[k][r-(1<<k)+1]);
    }
}sa;

int check(int mid){
    for(int i=1;i<=len;i++){
        int pos=i;
        for(int j=1;j<=k;j++) pos+=len-(sa.rk[pos]>mid&&sa.get_lcp(pos,sa.sa[mid])<len);
        if(pos>=i+n) return 1;
    }
    return 0;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin>>n>>k;
    len=n/k+(n%k!=0);
    cin>>sa.s+1;
    for(int i=1;i<=n;i++) sa.s[i+n]=sa.s[i];
    sa.init(n*2,9);
    sa.buildsa();
    sa.buildheight();
    int l=1,r=n*2,ans=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    for(int i=sa.sa[ans];i<=sa.sa[ans]+len-1;i++) cout<<sa.s[i];

    return true&&false;
}