题解归档 - cf2225F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2225F
• 本地来源：problems/cf2225F/idea.md
• 题目链接：https://codeforces.com/contest/2225/problem/F
• 原始标题：cf2225F - String Cutting

思路

cf2225F - String Cutting

Pattern

The k-th string after sorting can be maximized by considering exactly k
parts. With exactly k parts, the k-th sorted string is simply the maximum
part. Therefore the task is to find the lexicographically maximum substring
that can be one part of a valid partition into exactly k parts, each of
length at least l.

If l*k > n, no partition exists.

Claim

For a chosen answer substring starting at i, the prefix before it must be
cut into some number a of parts and the suffix after it into k-1-a parts.
Only lengths matter for feasibility:

• if i == 0, then a = 0;
• otherwise the prefix must contain at least one part, and can contain at most
  floor(i/l) parts.

For each i, take a = min(k-1, floor(i/l)), which leaves the fewest required
parts on the right. Then the lexicographically best substring with this start
is the longest possible one:

j = n-1 if no right part is needed, otherwise j = n-1-(k-1-a)*l.

All feasible candidates are enumerated by their start i; the answer is the
lexicographically largest candidate substring.

Comparison

There can be O(n) candidates and total input length is 1e6, so direct string
comparison is too slow. The implementation uses rolling hashes for LCP-based
comparison, with special handling for all-equal and short-period strings.

Checks

• Sample matches expected output.
• python tools/stress2.py cf2225F -n 1000 --keep-fail passed against brute.

• Large random performance checks:

  • n=200000: completed in about 0.034s.
  • n=1000000: completed in about 0.085s.

Risk

Substring comparison uses 64-bit rolling hashes, so theoretical hash collisions
are possible but negligible in local testing.

代码

来源：problems/cf2225F/solution.cpp

#include<bits/stdc++.h>
using namespace std;

using ull=unsigned long long;
const ull BASE=1000003ULL;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        int n,l,k;
        string s;
        cin>>n>>l>>k>>s;
        if(1LL*l*k>n){
            cout<<"NO\n";
            continue;
        }
        bool same=true;
        for(int i=1;i<n;i++) if(s[i]!=s[0]) same=false;
        int per=n;
        if(!same&&n>=20000){
            vector<int> pi(n);
            for(int i=1;i<n;i++){
                int j=pi[i-1];
                while(j&&s[i]!=s[j]) j=pi[j-1];
                if(s[i]==s[j]) j++;
                pi[i]=j;
            }
            int p=n-pi[n-1];
            if(p<n) per=p;
        }
        bool periodic=!same&&per<=10000;
        vector<ull> h,pw;
        vector<ull> ph,pp;
        string cyc;
        vector<int> rotRank;
        if(periodic){
            cyc=s.substr(0,per)+s.substr(0,per);
            ph.assign(cyc.size()+1,0);
            pp.assign(cyc.size()+1,1);
            for(int i=0;i<(int)cyc.size();i++){
                pp[i+1]=pp[i]*BASE;
                ph[i+1]=ph[i]*BASE+(ull)(cyc[i]-'a'+1);
            }
            vector<int> ord(per);
            iota(ord.begin(),ord.end(),0);
            sort(ord.begin(),ord.end(),[&](int a,int b){
                return cyc.compare(a,per,cyc,b,per)<0;
            });
            rotRank.assign(per,0);
            for(int i=0;i<per;i++) rotRank[ord[i]]=i;
        }else if(!same){
            h.assign(n+1,0);
            pw.assign(n+1,1);
            for(int i=0;i<n;i++){
                pw[i+1]=pw[i]*BASE;
                h[i+1]=h[i]*BASE+(ull)(s[i]-'a'+1);
            }
        }
        auto getHash=[&](int L,int len)->ull{
            return h[L+len]-h[L]*pw[len];
        };
        auto getPHash=[&](int L,int len)->ull{
            return ph[L+len]-ph[L]*pp[len];
        };
        if(same||periodic){
            int bestL=0,bestLen=0;
            bool has=false;
            for(int i=0;i+l<=n;i++){
                int a;
                if(i==0) a=0;
                else{
                    if(i<l) continue;
                    a=min(k-1,i/l);
                    if(a==0) continue;
                }
                int b=k-1-a;
                int j=(b==0?n-1:n-1-b*l);
                if(j-i+1<l) continue;
                int len=j-i+1;
                bool take=!has;
                if(has&&same) take=len>bestLen;
                else if(has){
                    int pa=i%per,pb=bestL%per;
                    if(pa==pb) take=len>bestLen;
                    else if(min(len,bestLen)>=per) take=rotRank[pa]>rotRank[pb];
                    else{
                        int lo=0,hi=min({per,len,bestLen});
                        while(lo<hi){
                            int mid=(lo+hi+1)>>1;
                            if(getPHash(pa,mid)==getPHash(pb,mid)) lo=mid;
                            else hi=mid-1;
                        }
                        if(lo==min(len,bestLen)) take=len>bestLen;
                        else take=cyc[pa+lo]>cyc[pb+lo];
                    }
                }
                if(take){
                    has=true;
                    bestL=i;
                    bestLen=len;
                }
            }
            cout<<"YES\n"<<s.substr(bestL,bestLen)<<"\n";
            continue;
        }
        int zBase=-1,zOff=0,zCnt=0;
        vector<int> z;
        auto buildZ=[&](int b){
            string t;
            t.reserve(n-b+1+n);
            t.append(s.begin()+b,s.end());
            t.push_back('{');
            t+=s;
            z.assign(t.size(),0);
            int L=0,R=0;
            for(int i=1;i<(int)t.size();i++){
                if(i<=R) z[i]=min(R-i+1,z[i-L]);
                while(i+z[i]<(int)t.size()&&t[z[i]]==t[i+z[i]]) z[i]++;
                if(i+z[i]-1>R){
                    L=i;
                    R=i+z[i]-1;
                }
            }
            zBase=b;
            zOff=n-b+1;
            zCnt=0;
        };
        auto hashLcp=[&](int a,int b,int lim){
            int lo=0,hi=lim;
            while(lo<hi){
                int mid=(lo+hi+1)>>1;
                if(getHash(a,mid)==getHash(b,mid)) lo=mid;
                else hi=mid-1;
            }
            return lo;
        };
        auto better=[&](int a,int lena,int b,int lenb)->bool{
            if(periodic){
                int pa=a%per,pb=b%per;
                if(pa==pb) return lena>lenb;
                if(min(lena,lenb)>=per) return rotRank[pa]>rotRank[pb];
                if(cyc[pa]!=cyc[pb]) return cyc[pa]>cyc[pb];
                int lo=0,hi=min({per,lena,lenb});
                while(lo<hi){
                    int mid=(lo+hi+1)>>1;
                    if(getPHash(pa,mid)==getPHash(pb,mid)) lo=mid;
                    else hi=mid-1;
                }
                if(lo==min(lena,lenb)) return lena>lenb;
                return cyc[pa+lo]>cyc[pb+lo];
            }
            if(s[a]!=s[b]) return s[a]>s[b];
            int lim=min(lena,lenb),common;
            if(zBase==b) common=min(z[zOff+a],lim);
            else{
                zCnt++;
                if(zCnt==1024&&n>=20000){
                    buildZ(b);
                    common=min(z[zOff+a],lim);
                }else common=hashLcp(a,b,lim);
            }
            if(common==lim) return lena>lenb;
            return s[a+common]>s[b+common];
        };
        int bestL=0,bestLen=0;
        bool has=false;
        for(int i=0;i+l<=n;i++){
            int a;
            if(i==0) a=0;
            else{
                if(i<l) continue;
                a=min(k-1,i/l);
                if(a==0) continue;
            }
            int b=k-1-a;
            int j=(b==0?n-1:n-1-b*l);
            if(j-i+1<l) continue;
            int len=j-i+1;
            bool take=!has||(same?len>bestLen:better(i,len,bestL,bestLen));
            if(take){
                has=true;
                bestL=i;
                bestLen=len;
                zBase=-1;
                zCnt=0;
                z.clear();
            }
        }
        cout<<"YES\n"<<s.substr(bestL,bestLen)<<"\n";
    }
    return 0;
}