题解：CF2225F String Cutting
MaxBlazeResFire
·
·
题解
第 k 大与最大的优化方向相同，给定一个 \geq k+1 段的分割，合并两段，第 k 大一定不会变小。因此恰好分 k 段是对的；对于一个子串 t，如果其出现在恰好 k 段的合法分割中，则答案不小于 t。
根据自然取优原理，我们可以忽略所有限制，问题转化为求所有可以出现在合法 k 分割中的串的最大者。
枚举左端点 l，左侧能分出的段数已知，想要合法可以算出右侧可以取到的最大的 r。取出所有 [l,r]，二分哈希比一个字典序最大者即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 1000005
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
#define BASE make_pair( 29 , 31 )
#define mod1 998244353
#define mod2 1000000007
inline pii F( int x ){ return mp( x , x ); }
inline int chkred( int x , int mod ){ return x >= mod ? x - mod : x; }
inline pii operator +( pii A , pii B ){ return mp( chkred( A.fi + B.fi , mod1 ) , chkred( A.se + B.se , mod2 ) ); }
inline pii operator -( pii A , pii B ){ return mp( chkred( A.fi - B.fi + mod1 , mod1 ) , chkred( A.se - B.se + mod2 , mod2 ) ); }
inline pii operator *( pii A , pii B ){ return mp( A.fi * B.fi % mod1 , A.se * B.se % mod2 ); }
inline bool operator ==( pii A , pii B ){ return A.fi == B.fi && A.se == B.se; }
int n,k,l;
char s[MAXN];
pii pre[MAXN],pw[MAXN];
inline pii Hash( int l , int r ){ return pre[r] - pre[l - 1] * pw[r - l + 1]; }
inline bool cmp( int l1 , int r1 , int l2 , int r2 ){
int len1 = r1 - l1 + 1,len2 = r2 - l2 + 1;
int l = 0,r = min( len1 , len2 ),ans = -1;
while( l <= r ){
int mid = ( l + r ) >> 1;
if( Hash( l1 , l1 + mid - 1 ) == Hash( l2 , l2 + mid - 1 ) ) ans = mid,l = mid + 1;
else r = mid - 1;
}
if( ans != min( len1 , len2 ) ) return s[l1 + ans] < s[l2 + ans];
return len1 < len2;
}
inline void solve(){
scanf("%lld%lld%lld%s",&n,&l,&k,s + 1);
if( k * l > n ){ puts("NO"); return; }
for( int i = 1 ; i <= n ; i ++ ) pre[i] = pre[i - 1] * BASE + F( s[i] - 'a' + 1 );
int ansl = -1,ansr = -1;
for( int L = 1 ; L <= n ; L ++ ){
if( L <= l && L > 1 ) continue;
int c1 = min( ( L - 1 ) / l , max( 1ll , k - 1 ) ); if( c1 >= k ) continue;
int rem = k - 1 - c1;
int r = n - rem * l;
if( r - L + 1 < l ) continue;
// cerr << L << " " << r << "\n";
if( ansl == -1 ) ansl = L,ansr = r;
else if( cmp( ansl , ansr , L , r ) ) ansl = L,ansr = r;
}
puts("YES");
for( int i = ansl ; i <= ansr ; i ++ ) printf("%c",s[i]);
puts("");
}
signed main(){
pw[0] = F(1);
for( int i = 1 ; i < MAXN ; i ++ ) pw[i] = pw[i - 1] * BASE;
// lg2[0] = -1; for( int i = 1 ; i < MAXN ; i ++ ) lg2[i] = lg2[i >> 1] + 1;
int t = 1; scanf("%lld",&t);
while( t -- ) solve();
return 0;
}
```