P6095 解题报告

Hoks · 2024-04-12 20:09:28 · 题解

前言

比较简单的 \mathrm{SA} 题，适合刚入门喵。

广告：『从入门到入土』串串学习笔记。

思路分析

首先题目说要把长度为 n 的数字串切成 k 段使得值最大的最小。

不难发现切出来的数字串长度只可能为 \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 更优还是 \lceil\frac{n}{k}\rceil-1 更优即可。

貌似没有什么好的处理方法了？

发现这些断出来的字符串的具体大小并不确切知晓，很影响做题。

不难发现如果有一种方案能断出的最大的值为 x。

那么我们对于 y,y\ge x 必然是存在方案的。

也就是答案是数字串大小具有单调性。

考虑二分出数字串大小，接着尝试 check。

考虑贪心，能断为 \lceil\frac{n}{k}\rceil 的就断为 \lceil\frac{n}{k}\rceil，不能的就断为 \lceil\frac{n}{k}\rceil-1。

思索下为什么是对的。

考虑反证，如果能断为 \lceil\frac{n}{k}\rceil 的断为了 \lceil\frac{n}{k}\rceil-1，那么下一次可以断 \lceil\frac{n}{k}\rceil 的话，其断出的总长度为 2\times\lceil\frac{n}{k}\rceil-1。

但如果我们考虑把能断为 \lceil\frac{n}{k}\rceil 的都断为 \lceil\frac{n}{k}\rceil，下一次最短也会断 \lceil\frac{n}{k}\rceil-1，其总长度 x 必然满足 x\ge2\times\lceil\frac{n}{k}\rceil-1。

也就是把能断为 \lceil\frac{n}{k}\rceil 的全断严格不劣于把他断为 \lceil\frac{n}{k}\rceil-1。

接着考虑怎么比较数字串大小，考虑二分出排名 rk，那么从 i 开始长度为 \lceil\frac{n}{k}\rceil/\lceil\frac{n}{k}\rceil-1 的串即为后缀 i 的前缀。

又因为前缀的排名严格不大于原串，所以直接比较原后缀的排名与二分的排名即可。

最后要求输出最大值数字串，考虑存下排名的值输出这个排名的后缀长为 \lceil\frac{n}{k}\rceil 的前缀即可。

代码

#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define int long long
using namespace std;
const int N=4e5+10,mod=1e9+7,INF=0x3f3f3f3f3f3f3f3f;
int n,k,m,ans;char s[N];
namespace Fast_IO
{
    static char buf[1000000],*paa=buf,*pd=buf,out[10000000];int length=0;
    #define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
    inline int read()
    {
        int x(0),t(1);char fc(getchar());
        while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
        while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
        return x*t;
    }
    inline void flush(){fwrite(out,1,length,stdout);length=0;}
    inline void put(char c){if(length==9999999) flush();out[length++]=c;}
    inline void put(string s){for(char c:s) put(c);}
    inline void print(int x)
    {
        if(x<0) put('-'),x=-x;
        if(x>9) print(x/10);
        put(x%10+'0');
    }
    inline bool chk(char c) { return !(c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='0'&&c<='9'); }
    inline bool ck(char c) { return c!='\n'&&c!='\r'&&c!=-1&&c!=' '; }
    inline void rd(char s[],int&n)
    {
        s[++n]=getchar();
        while(chk(s[n])) s[n]=getchar();
        while(ck(s[n])) s[++n]=getchar();
        n--;
    }
}
using namespace Fast_IO;
namespace SA
{
    const int lim=20,ST=127;
    int sa[N],rk[N],old[N],c[N],h[N],st[lim+1][N];
    inline void get_SA()
    {
        m=ST;
        for(int i=1;i<=n;i++) ++c[rk[i]=s[i]];
        for(int i=2;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[rk[i]]--]=i;
        for(int k=1;k<=n;k<<=1)
        {
            int tot=0;
            for(int i=n-k+1;i<=n;i++) old[++tot]=i;
            for(int i=1;i<=n;i++) if (sa[i]>k) old[++tot]=sa[i]-k;
            for(int i=1;i<=m;i++) c[i]=0;
            for(int i=1;i<=n;i++) c[rk[i]]++;
            for(int i=2;i<=m;i++) c[i]+=c[i-1];
            for(int i=n;i>=1;--i) sa[c[rk[old[i]]]--]=old[i],old[i]=0;
            swap(rk,old);rk[sa[1]]=1;tot=1;
            for(int i=2;i<=n;i++) rk[sa[i]]=(old[sa[i]]==old[sa[i-1]]&&old[sa[i]+k]==old[sa[i-1]+k])?tot:++tot;
            if(tot==n) break;m=tot;
        }
    }
    inline void get_height()
    {
        for(int i=1,k=0,j;i<=n;i++)
        {
            if(k) --k;j=sa[rk[i]-1];
            while(s[i+k]==s[j+k]) k++;
            h[rk[i]]=k;
        }
    }
    inline void get_ST()
    {
        for(int i=1;i<=n;i++) st[0][i]=h[i];
        for(int j=1;j<=lim;j++)
            for(int i=1;i+(1<<j)-1<=n;i++)
                st[j][i]=min(st[j-1][i],st[j-1][i+(1<<j-1)]);
    }
    inline int lcp(int l,int r){int k=log2(r-l);l++;return min(st[k][l],st[k][r-(1<<k)+1]);}
}
using namespace SA;
signed main()
{
    read(),k=read();rd(s,n);for(int i=1;i<=n;i++) s[i+n]=s[i];n<<=1;get_SA();get_height();
    int l=1,r=n,len=((n>>1)-1)/k+1;
    while(l<=r)
    {
        int f=0;
        for(int i=1;i<=len;i++)
        {
            int cur=0;
            for(int j=1;j<=k;j++)
            {
                int x=(i+cur-1)%(n>>1)+1;
                if(rk[x]<=mid) cur+=len;
                else cur+=len-1;
            }f|=cur>=(n>>1);
        }if(f) ans=mid,r=mid-1;
        else l=mid+1;
    }
    for(int i=0;i<len;i++) put(s[sa[ans]+i]);
    genshin:;flush();return 0;
}