题解：CF2225F String Cutting

· · 题解

赛时看到 E 是不可做题就去看 F 了，已经知道结论但我比较 O(n) 个子串大小非要写 SA，最后没写出来。

题意：把 s 分为至少 k 个连续段，要求任意一段长度 >l，最大化排名为 k 的连续段字典序。|s|\le 10^6。

结论：恰分成 k 段不劣。

::::info[证明：]

假设我们分成了超过 k 段，记段数为 x，那么我们找到排名为 x 的段，将其向前或向后合并一段，显然答案不会变小。重复此操作直到 x=k。 :::: 那么此时我们考虑答案形态，如果答案是 [l,r]，那么显然这个区间越长越好，那么我们可以枚举 l， 求出此时 r 的最大值，然后对所有形如 [i,R_i] 的子串取 \max，根据答案形态，显然可以统计到答案，我们用哈希二分比较即可。复杂度 O(n\log n)。我不知道我赛时为什么要写一个 SA 然后用 ST 表维护两个后缀的 LCP 再做。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,P1=998244353,P2=1e9+7,b1=1235,b2=97;
int T,n,k,l,r[N];
string s; 
struct HSH{int a,b;}H[N],mi[N];
HSH operator+(HSH x,int y){x.a=(1ll*x.a*b1+y)%P1,x.b=(1ll*x.b*b2+y)%P2;return x;}
HSH operator-(HSH x,HSH y){x.a=((x.a-y.a)%P1+P1)%P1,x.b=((x.b-y.b)%P2+P2)%P2;return x;}
HSH operator*(HSH x,HSH y){x.a=1ll*x.a*y.a%P1,x.b=1ll*x.b*y.b%P2;return x;}
HSH Q(int l,int r){return H[r]-H[l-1]*mi[r-l+1];}
bool operator==(HSH x,HSH y){return x.a==y.a&&x.b==y.b;}
int check(int i){int t=min((i-1)/l+1,k);if((t!=1||i==1)&&i<=n-(k-t+1)*l+1) return n-(k-t)*l;return 0;}
bool big(int l,int r,int L,int R){
    if(s[l]!=s[L]) return s[l]>s[L];
    int z=1,y=min(r-l+1,R-L+1);
    while(z<=y){int mid=(z+y)>>1;if(Q(l,l+mid-1)==Q(L,L+mid-1)) z=mid+1;else y=mid-1;}
    if(l+y-1==r||L+y-1==R) return r-l+1>R-L+1;
    return s[l+y]>s[L+y];
}void solve(){
    cin>>n>>l>>k>>s,s='|'+s;
    if(n<1ll*l*k){cout<<"NO\n";return;}cout<<"YES\n";
    for(int i=1;i<=n;i++) r[i]=check(i),H[i]=H[i-1]+s[i];
    int L=1,R=r[1];
    for(int i=2;i<=n;i++)if(r[i]&&big(i,r[i],L,R)) L=i,R=r[i];
    for(int i=L;i<=R;i++) cout<<s[i];cout<<'\n';
}int main(){
    cin>>T,mi[0]={1,1};for(int i=1;i<N;i++) mi[i]=mi[i-1]+0;
    while(T--) solve();
    return 0;
}