CF1654F Minimal String Xoration 题解

倍增处理，先倍长字符串，然后记 $f_{i,j}$ 表示从 $i$ 位置开始长度为 $2^j$ 的字符串，则最终答案就是 $f_{*,n}$ 中字典序最小的串。

但是这样的话根据主定理可知倍增过程中串长之和是 $O(n^2\log n)$ 级别的，无法通过。此时注意到倍增过程和后缀排序没有本质区别，因此类比后缀数组维护 rk 和 sa 两个数组即可得到倍增过程中某一层所有串的字典序相对大小关系，最后再 $O(n)$ 时间复杂度还原出字典序最小的串即可。

理论上可以做到 $O(n\log n)$ ，但是这里偷懒写了 $O(n\log^2n)$ 。

代码，~~本来看到都写的差不多不想贴了来着~~

int sa[N], rk[N], seq[N];
inline void sol() {
    int n; cin >> n; n = 1 << n;
    string s; cin >> s;
    for (int i = 0; i < n; ++i) sa[i] = i, rk[i] = s[i] - 'a';
    sort(sa, sa + n, [&](auto &l, auto &r) { return rk[l] < rk[r]; });
    for (int j = 1; j < n; j <<= 1) {
        sort(sa, sa + n, [&](auto &l, auto &r) {
            return rk[l] < rk[r] || rk[l] == rk[r] && rk[l ^ j] < rk[r ^ j];
        });
        int idx = 0;
        for (int i = 0; i < n; ++i)
            if (!i || rk[sa[i - 1]] < rk[sa[i]] || rk[sa[i - 1]] == rk[sa[i]] && rk[sa[i - 1] ^ j] < rk[sa[i] ^ j]) seq[sa[i]] = idx++;
            else seq[sa[i]] = seq[sa[i - 1]];
        for (int i = 0; i < n; ++i) rk[i] = seq[i];
    } string res;
    for (int i = 0; i < n; ++i) res.push_back(s[sa[0] ^ i]);
    cout << res << '\n';
}

← 返回题解列表

隐藏／恢复文章

随机文章