P6095 [JSOI2015] 串分割 题解

· · 题解

洛谷 P6095 [JSOI2015] 串分割 题解

题目简要

给定一个长度为 n 的数字串，需要将其分割成 k 段，使得所有段中字典序最大的段尽可能小。

思路

  1. 由于是数字串且不含前导零，因此长度更长的数字串一定更大，每段长度只能是 L = \lceil n/k \rceil 或 L-1，目标是让所有段中字典序最大的段最小化
  2. 答案具有单调性：如果存在方案使得最大段不超过 x，那么对于任何 y > x 也一定存在方案，所以考虑二分答案，我们二分答案在后缀数组中的排名，检查是否存在一种分割方式使得所有段的字典序都不超过当前二分的排名。
  3. 对于二分答案的 check ，我们对于每个可能的起始位置，贪心模拟分割过程：
    • 如果当前位置开始长度为 L 的子串排名小于等于当前二分值，则选择长度为 L 的段
    • 否则选择长度为 L-1 的段
    • 检查 k 次分割后是否能覆盖整个原字符串

贪心的正确性：能选 L 长度时选择 L-1 不会使结果更优。

  1. 通过构建后缀数组，我们可以快速比较任意子串的字典序大小。

复杂度

代码实现


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

const int N = 4e5 + 5;
char s[N];
int n, k, m, len;
int sa[N], rk[N], ork[N], buc[N], id[N];

bool cmp(int a, int b, int w) {
    return ork[a] == ork[b] && ork[a + w] == ork[b + w];
}

void build() {
    int p = 0, M = 1 << 7;
    for (int i = 1; i <= n; i++) buc[rk[i] = s[i]]++;
    for (int i = 1; i <= M; i++) buc[i] += buc[i - 1];
    for (int i = n; i; i--) sa[buc[rk[i]]--] = i;

    for (int w = 1; ; w <<= 1, M = p, p = 0) {
        for (int i = n - w + 1; i <= n; i++) id[++p] = i;
        for (int i = 1; i <= n; i++) if (sa[i] > w) id[++p] = sa[i] - w;

        memset(buc, 0, sizeof(buc));
        memcpy(ork, rk, sizeof(rk));
        p = 0;

        for (int i = 1; i <= n; i++) buc[rk[i]]++;
        for (int i = 1; i <= M; i++) buc[i] += buc[i - 1];
        for (int i = n; i; i--) sa[buc[rk[id[i]]]--] = id[i];

        for (int i = 1; i <= n; i++) 
            rk[sa[i]] = cmp(sa[i - 1], sa[i], w) ? p : ++p;
        if (p == n) break;
    }
}

bool check(int mid) {
    for (int i = 1; i <= len; i++) {
        int cur = 0;
        for (int j = 1; j <= k; j++) {
            int p = (i + cur - 1) % m + 1;
            if (rk[p] <= mid) cur += len;
            else cur += len - 1;
        }
        if (cur >= m) return true;
    }
    return false;
}

int main() {
    cin >> n >> k;
    cin >> (s + 1);
    len = (n - 1) / k + 1;
    m = n;

    for (int i = 1; i <= n; i++) s[i + n] = s[i];
    n *= 2;

    build();

    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    for (int i = 0; i < len; i++) 
        cout << s[sa[l] + i];
    cout << endl;

    return 0;
}//完结撒花，蒟蒻的第一篇紫题题解！