题目分析:构好后缀数组,然后二分答案就好了~_~
代码如下:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std ; typedef long long LL ; #define rep( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i ) #define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i ) #define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i ) #define clr( a , x ) memset ( a , x , sizeof a ) #define ls ( o << 1 ) #define rs ( o << 1 | 1 ) #define lson ls , l , m #define rson rs , m + 1 , r #define mid ( ( l + r ) >> 1 ) const int MAXN = 20005 ; int s[MAXN] ; int a[MAXN] , cnt ; int t1[MAXN] , t2[MAXN] , c[MAXN] , xy[MAXN] ; int sa[MAXN] , rank[MAXN] , height[MAXN] ; int vis[MAXN] , Time ; int n , k ; int cmp ( int *r , int a , int b , int d ) { return r[a] == r[b] && r[a + d] == r[b + d] ; } void getHeight ( int n , int k = 0 ) { For ( i , 0 , n ) rank[sa[i]] = i ; rep ( i , 0 , n ) { if ( k ) -- k ; int j = sa[rank[i] - 1] ; while ( s[i + k] == s[j + k] ) ++ k ; height[rank[i]] = k ; } } void da ( int n , int m = cnt + 1 ) { int *x = t1 , *y = t2 ; rep ( i , 0 , m ) c[i] = 0 ; rep ( i , 0 , n ) ++ c[x[i] = s[i]] ; rep ( i , 1 , m ) c[i] += c[i - 1] ; rev ( i , n - 1 , 0 ) sa[-- c[x[i]]] = i ; for ( int d = 1 , p = 0 ; p < n ; d <<= 1 , m = p ) { p = 0 ; rep ( i , n - d , n ) y[p ++] = i ; rep ( i , 0 , n ) if ( sa[i] >= d ) y[p ++] = sa[i] - d ; rep ( i , 0 , m ) c[i] = 0 ; rep ( i , 0 , n ) ++ c[xy[i] = x[y[i]]] ; rep ( i , 1 , m ) c[i] += c[i - 1] ; rev ( i , n - 1 , 0 ) sa[-- c[xy[i]]] = y[i] ; swap ( x , y ) ; p = 0 ; x[sa[0]] = p ++ ; rep ( i , 1 , n ) x[sa[i]] = cmp ( y , sa[i - 1] , sa[i] , d ) ? p - 1 : p ++ ; } getHeight ( n - 1 ) ; } int unique ( int n ) { int cnt = 0 ; sort ( a , a + n ) ; rep ( i , 1 , n ) if ( a[i] != a[cnt] ) a[++ cnt] = a[i] ; return cnt + 1 ; } int search ( int x , int l = 0 , int r = cnt - 1 ) { while ( l < r ) { int m = ( l + r ) >> 1 ; if ( a[m] >= x ) r = m ; else l = m + 1 ; } return l ; } int check ( int h ) { int t = 0 ; ++ Time ; //if ( h == 1 ) printf ( "ok\n" ) ; For ( i , 2 , n ) { if ( height[i] < h ) { if ( t >= k ) return 1 ; ++ Time ; t = 0 ; } else { if ( vis[sa[i - 1]] != Time ) { ++ t ; vis[sa[i - 1]] = Time ; } if ( vis[sa[i]] != Time ) { ++ t ; vis[sa[i]] = Time ; } } } if ( t >= k ) return 1 ; return 0 ; } void solve () { rep ( i , 0 , n ) { scanf ( "%d" , &s[i] ) ; a[i] = s[i] ; } cnt = unique ( n ) ; rep ( i , 0 , n ) s[i] = search ( s[i] ) + 1 ; s[n] = 0 ; //rep ( i , 0 , n ) printf ( "%d " , s[i] ) ; //printf ( "\n" ) ; //printf ( "%d %d\n" , n , cnt ) ; da ( n + 1 ) ; int l = 1 , r = n ; while ( l < r ) { int m = ( l + r + 1 ) >> 1 ; if ( check ( m ) ) l = m ; else r = m - 1 ; } printf ( "%d\n" , r ) ; } int main () { Time = 0 ; clr ( vis , 0 ) ; while ( ~scanf ( "%d%d" , &n , &k ) ) solve () ; return 0 ; }