说在前面
赶紧写完,,,,,就能快点回去洗澡了~
题目
BZOJ4310传送门
题目大意
给一个长度不超过100000的字符串。现在要把这个字符串分成K组（K不超过length），然后对于每一组，取其字典序最大的子串，得到一个集合S，记S中字典序最大的那个串为ss，询问ss字典序最小可以是什么
输入输出格式
输入格式： 第一行一个整数K，含义如题 接下来一行一个字符串
输出格式： 输出所求字符串
解法
看了hxy的题解 这个做法比较神 或者me太蠢 头一次知道后缀数组还可以这么玩
因为要最大的最小，不妨考虑二分求出答案 卧槽字符串怎么二分？ 首先，一个字符串的不同子串个数
=∑len−sa[i]−height[i]+1
=
∑
l
e
n
−
s
a
[
i
]
−
h
e
i
g
h
t
[
i
]
+
1
（me的字符串下标从1开始）。根据定义还是比较显然的，请一定要想明白！ 于是二分的上下界就有了。假设二分到了一个mid，求出第mid小的子串
s
s
，check的时候从后往前贪心的分组，如果分的组数大于K就不行。贪心分组是显然的，如果[i,j][i,j]的字典序大于了
s
s
，那么肯定在ii和
i+1
i
+
1
之间切一刀（第一个字母就比
s
s
大的情况特殊讨论）。快速比较字典序可以用ST表查LCP
那么如何求出第mid小的子串呢？从1到n枚举后缀的排名，如果mid大于了当前后缀贡献的数量，那么mid -= dif[i]，不然的话，说明所求字符串就是L=sa[i]L=sa[i]，
R=sa[i]+height[i]+mid−1
R
=
s
a
[
i
]
+
h
e
i
g
h
t
[
i
]
+
m
i
d
−
1
，这里也请一定要想明白！
然后这题就做完了
下面是自带大常数的代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
char ss[
100005] ;
int K ,
len , logg[
100005] , mi2[
30] , ST[
17][
100005];
int sa[
100005] , rk[
100005] , tp[
100005] , buc[
100005] , he[
100005] , dif[
100005] ;
bool cmp(
int *f ,
int x ,
int y ,
int d ){
return f[x] != f[y] || ( f[x] == f[y] && f[x+d] != f[y+d] ) ;
}
void Rsort(
int *rk ,
int *tp ,
int x ){
for(
int i =
1 ; i <= x ; i ++ ) buc[i] =
0 ;
for(
int i =
1 ; i <=
len ; i ++ ) buc[ rk[tp[i]] ] ++ ;
for(
int i =
1 ; i <= x ; i ++ ) buc[i] += buc[i-
1] ;
for(
int i =
len ; i ; i -- ) sa[ buc[rk[tp[i]]] -- ] = tp[i] ;
}
void getSA(){
int now =
127 , *tp = ::tp , *rk = ::rk ;
for(
int i =
1 ; i <=
len ; i ++ )
tp[i] = i , rk[i] = ss[i] ;
Rsort( rk , tp ,
now ) ;
for(
int l =
1 , p =
0 ; ; l <<=
1 ,
now = rk[ sa[
len] ] , p =
0 ){
for(
int i =
len - l +
1 ; i <=
len ; i ++ ) tp[++p] = i ;
for(
int i =
1 ; i <=
len ; i ++ )
if( sa[i] - l >
0 ) tp[++p] = sa[i] - l ;
Rsort( rk , tp ,
now ) ; swap( tp , rk ) ; rk[ sa[
1] ] =
1 ;
for(
int i =
2 ; i <=
len ; i ++ )
rk[ sa[i] ] = rk[ sa[i-
1] ] + cmp( tp , sa[i] , sa[i-
1] , l ) ;
if( rk[ sa[
len] ] ==
len ) break ;
}
if( ::rk != rk ) memcpy( ::rk , rk , sizeof( ::rk ) ) ;
for(
int i =
1 , j , k =
0 ; i <=
len ; he[ rk[i++] ] = k )
for( j = sa[ rk[i]-
1 ] , k = k ? k -
1 : k ; ss[i+k] == ss[j+k] ; k ++ ) ;
}
void preWork(){
logg[
1] =
0 , logg[
2] =
1 , logg[
3] =
1 ;
for(
int i =
4 ; i <=
len ; i ++ ) logg[i] = logg[i>>
1] +
1 ;
for(
int i =
0 ; i <=
20 ; i ++ ) mi2[i] = (
1 << i ) ;
getSA() ;
for(
int i =
1 ; i <=
len ; i ++ ) ST[
0][i] = he[i] ;
for(
int i =
1 ; i <= logg[
len] ; i ++ )
for(
int j =
1 ; j + mi2[i-
1] <=
len ; j ++ )
ST[i][j] = min( ST[i-
1][j] , ST[i-
1][ j+mi2[i-
1] ] ) ;
}
int Query(
int L ,
int R ){
if( L == R ) return
len - L +
1 ;
L = rk[L] , R = rk[R] ;
if( L > R ) swap( L , R ) ; L ++ ;
int len = logg[ R - L +
1 ] ;
return min( ST[
len][L] , ST[
len][ R-mi2[
len]+
1 ] ) ;
}
int global_L , global_R ;
void getString( long long
left ,
int i =
1 ){
for( ;
left > dif[i] ;
left -= dif[i++] ) ;
global_L = sa[i] , global_R = sa[i] + he[i] +
left -
1 ;
}
bool check(){
for(
int i =
len , cut =
len +
1 , cnt =
0 ; i ; i -- ){
int LCP = Query( global_L , i ) ;
if( !LCP && ss[global_L] < ss[i] ) return
false ;
LCP = min( LCP , min( global_R - global_L +
1 , cut - i ) ) ;
if( LCP == cut - i ) continue ;
if( LCP == global_R - global_L +
1 || ss[ global_L+LCP ] < ss[i+LCP] ){
cut = i +
1 ; cnt ++ ;
if( cnt > K ) return
false ;
}
} return
true ;
}
void solve(){
int ansL , ansR ;
long long lf =
1 , rg =
0 ;
for(
int i =
1 ; i <=
len ; i ++ ) rg += ( dif[i] =
len - sa[i] +
1 - he[i] ) ;
while( lf <= rg ){
long long
mid = ( lf + rg ) >>
1 ;
getString(
mid ) ;
if( check() )
ansL = global_L , ansR = global_R , rg =
mid -
1 ;
else lf =
mid +
1 ;
}
for(
int i = ansL ; i <= ansR ; i ++ )
printf(
"%c" , ss[i] ) ;
}
int main(){
scanf(
"%d%s" , &K , ss +
1 ) ; K -- ;
len = strlen( ss +
1 ) ;
preWork() ; solve() ;
}
