题解：CF2225F String Cutting

DrDuck · 2026-04-26 21:38:41 · 题解

奶奶题目不光卡我单模哈希，双模哈希底数选 131 和 137 都要卡，害我白白多调一个小时。

诈骗题。

首先分成 k 段一定最优，因为如果分更多段合起来一定不劣。

枚举一个 i，我们假设 i 是字典序最大的那个子串的左端点，我们需要确定一个 j 作为右端点，并且 j 尽可能大来使字典序尽量大。我们尽量在 i 的左边多分段，这样 j 的右边段数就尽可能小，然后右边每一段长度全取 l，这样 j 就能尽可能大。然后对于每一个子串 s_is_{i+1}\dots s_{j-1}s_j 再取字典序最大的那一个即可。比较字典序可以用哈希 + 二分 lcp 实现。

时间复杂度 O(n \log n)。

:::success[CODE]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e+6 + 6;
int T, n, m, k;
char s[maxn];
struct Hash {
    int base, mod;
    int f[maxn], g[maxn];
    inline void init() {
        g[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i] = (f[i - 1] * base % mod + s[i]) % mod;
            g[i] = g[i - 1] * base % mod;
        }
    }
    inline int ret(int l, int r) {
        return (f[r] - f[l - 1] * g[r - l + 1] % mod + mod) % mod;
    }
}h1, h2;
inline bool chk(int l1, int r1, int l2, int r2) {
    int l = 1, r = min(r1 - l1 + 1, r2 - l2 + 1), res = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (h1.ret(l1, l1 + mid - 1) == h1.ret(l2, l2 + mid - 1) && h2.ret(l1, l1 + mid - 1) == h2.ret(l2, l2 + mid - 1)) {
            res = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    if (res == min(r1 - l1 + 1, r2 - l2 + 1)) return r1 - l1 + 1 < r2 - l2 + 1;
    return s[l1 + res] < s[l2 + res];
}
inline void GOGOGO() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    h1.init(), h2.init();
    int l = 0, r = 0;
    for (int i = 1; i + m - 1 <= n; i++) {
        if (i != 1 && i <= m) continue;
        int cnt = (i - 1) / m;
        cnt = k - cnt - 1;
        if (cnt < 0) {
            if (k == 1) break;
            cnt = 0;
        }
        cnt *= m;
        int j = n - cnt;
        if (j - i + 1 < m) continue;
        if (!l || chk(l, r, i, j)) {
            l = i;
            r = j;
        }
    }
    if (!l) cout << "NO" << '\n';
    else {
        cout << "YES" << '\n';
        for (int i = l; i <= r; i++) cout << s[i];
        cout << '\n';
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    h1.base = 97, h1.mod = 998244353;
    h2.base = 101, h2.mod = 1e+9 + 7;
    while (T--) GOGOGO();
    return 0;
}

:::