【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();
}
上一篇:Python itertools.combinations 和 itertools.permutations 等价代码实现


下一篇:【Java并发编程】之二:线程中断