【bzoj4486】【JSOI2015】串分割

老省选题了。

首先考虑怎么比较超长数字的大小？

参见UTR1的那道题

先比size，然后比较字典序即可。

接下来考虑下切割的问题。

因为要将字符串切割成k份，所以这个字符串只会存在n/k个本质不同的起始位置。

然后可能会发现，如果能够整除的话，将这些起始位置直接后缀排序就可以了。

那么如果不能整除怎么办?

我们可以发现，如果有多余的，那么最长的字符串一定最多比别人多1

这个贪心的正确性比较的显然。

那么我们怎么处理长度不同的呢？

将之前的比较二分即可。

#include<bits/stdc++.h>

#define N 400010

using namespace std;

int t1[N],t2[N],a[N],sa[N],rk[N],c[],h[N];

int n,m,k,cnt;

char s[N];

void calcsa(int n,int m){

    int *x=t1,*y=t2,f=,p=;

    for(int i=;i<=m;i++)c[i]=;

    for(int i=;i<=n;i++)c[x[i]=a[i]]++;

    for(int i=;i<=m;i++)c[i]+=c[i-];

    for(int i=n;i;i--)sa[c[x[i]]--]=i;

    for(int i=;i<=n&&p<=n;i<<=){p=;

        for(int j=n-i+;j<=n;j++)y[++p]=j;

        for(int j=;j<=n;j++)if(sa[j]>i)y[++p]=sa[j]-i;

        for(int j=;j<=m;j++)c[j]=;

        for(int j=;j<=n;j++)c[x[y[j]]]++;

        for(int j=;j<=m;j++)c[j]+=c[j-];

        for(int j=n;j>=;j--)sa[c[x[y[j]]]--]=y[j];

        swap(x,y);x[sa[]]=;p=;

        for(int j=;j<=n;j++)

        x[sa[j]]=y[sa[j]]==y[sa[j-]]&&y[sa[j]+i]==y[sa[j-]+i]?p-:p++;

        m=p;

    }

    for(int i=;i<=n;i++)rk[sa[i]]=i;

    for(int i=;i<=n;i++){

        int j=sa[rk[i]-];

        if(f)f--;while(a[i+f]==a[j+f])f++;

        h[rk[i]]=f;

    }

}

inline bool check(int x){

    int p;

    for(int i=;i<=m;i++){

        int t=i;p=k;

        while(p--){

            if(rk[t]<=x)t+=m;else t+=m-;

            if(t>=n+i)return ;

        }

    }

    return ;

}

inline void work(){

    int l=,r=cnt;

    while(l<r){

        int mid=(l+r)>>;

        if(check(mid))r=mid;else l=mid+;

    }

    for(int i=;i<=n;i++)if(rk[i]==l)

    for(int j=i;j<=i+m-;j++)printf("%c",a[j]+'');

    puts("");

}

int main(){

    scanf("%d%d",&n,&k);scanf("%s",s+);

    for(int i=;i<=n;i++)a[++cnt]=s[i]-'';

    for(int i=;i<n;i++)a[++cnt]=s[i]-'';

    calcsa(cnt,);

    //for(int i=1;i<=cnt;i++)printf("%d ",sa[i]);puts("");

    m=n/k+(n%k!=);

    work();

}

巴特西

【bzoj4486】【JSOI2015】串分割

最新文章

热门文章