[Hard] CF1923F Shrink-Reverse

xiezheyuan2025/2/4约 1694 字大约 8 分钟

简要题意

有一个长度为 $n$ 的 $01$ 串 $S$ ，你可以执行下列两种操作至多 $k$ 次：

交换：选定 $1\leq i,j\leq n$ 并交换 $S_i,S_j$ 。
Shrink-Reverse 变换（以下简称变换）：先删除 $S$ 的所有前导 $0$ ，然后将 $S$ 翻转。

你需要使 $S$ 表示的二进制数尽可能小，输出这个二进制数值的最小值对 $10^9+7$ 取模。

$2\leq n\leq 5\times 10^5$ 。

思路

超级高明题，难点不在 SA 本身。

Part 1

难点在于意识到这些结论。

引理 1：我们总是在执行所有交换后进行变换。

证明：假如我们在一次变换后进行交换，我们一定可以在找到这两个位置在变换前的下标，改为在变换前进行交换。也就是说在变换前交换是不劣的。

引理 2：我们不会执行超过一次变换。

证明：不妨先研究一下变换的过程：

\textcolor{grey}{0\cdots0}\textcolor{red}{\text{AB}}\textcolor{blue}{0\cdots 0}\xrightarrow{\text{Shrink-Reverse}} \textcolor{grey}{0\cdots 0}\textcolor{red}{\text{BA}}\xrightarrow{\text{Shrink-Reverse}}\textcolor{red}{\text{AB}}\xrightarrow{\text{Shrink-Reverse}}\textcolor{red}{\text{BA}}

在上面的示意图中，灰色的 $0$ 表示前导 $0$ ，蓝色的 $0$ 表示后导 $0$ ，中间红色的 $\mathrm{AB}$ 表示以 $1$ 开头和结尾的串，用 $\text{AB},\text{BA}$ 区分顺序。

当我们进行超过 $2$ 次变换时，便陷入 BA 与 AB 的循环，那么执行奇数次变换，不如执行一次变换（因为前导 $0$ 在最终比较时是忽略的），执行偶数次变换，不如执行两次变换。所以我们最多执行 $2$ 次变换。

进一步地，考察进行两次变换的影响，发现仅仅在原串的基础上去除了后导 $0$ 。那么有一种非常神奇的策略：仅执行一次变换，接下来进行调整。

具体的调整策略是，如果中间串全是 $1$ ，那么无需调整。否则将外侧的一个 $1$ 与内部的一个 $0$ 交换（当然，需要根据引理 1 将这个操作等效替代为变换前的操作），这样有效位数就减小了，比变换两次更优。

Part 2

由于引理 2，我们只能进行 $0$ 次或 $1$ 次变换。现在考虑进行 $0$ 次的情况。

很容易设计一个贪心，将高位的 $1$ 与低位的 $0$ 交换，正确性是显然的。这个贪心很容易用双指针实现。

同时观察到这个贪心的本质是将 $1$ 尽可能的靠拢在一个区间中。这个思路是可以沿用的。

Part 3

现在考虑进行 $1$ 次的情况。

根据前面的分析，我们很容易感受出操作的策略是什么，就是选定一个区间，保留其中的所有 $1$ ，然后将区间外的 $1$ 与区间内交换。

由于我们需要在长度相同的情况下，让字典序最小，于是我们希望 $1$ 在后面，所以需要从后往前填区间外的 $1$ 。

观察这样的区间 $[L,R]$ 的限制。首先需要将区间外的所有 $1$ 都填进去，所以 $R-L+1$ 要不小于整个序列的 $1$ 的数量。

另外我们有操作次数的限制，所以区间外的 $1$ 的数量必须不大于 $k-1$ 。

我们发现固定区间的一端，另一端对区间是否合法的影响是单调的，于是可以用双指针维护。

Part 4

最后我们可以用双指针得到若干个固定左端点，最短的合法区间。我们需要选择最优的。

观察到对于两个候选的子串 $a,b$ ，如果 $a$ 的长度比 $b$ 小，那么我们肯定选择 $a$ 。

如果 $a,b$ 长度相同，观察到我们需要从后往前将 $0$ 替换为 $1$ 。那么如果 $a$ 的字典序比 $b$ 小，那么最终替换后 $a$ 的字典序仍然不比 $b$ 大。这是因为我们定义字典序小，是因为 $a_i=0$ 而 $b_i=1$ （ $[1,i-1]$ 都相同），而若 $a_i$ 未被替换为 $0$ ，则结论显然成立。否则 $a_i$ 后面的 $0$ 均是 $1$ ，由于 $a,b$ 的 $0/1$ 数量相同（都会是 $k-1$ ，因为 $1$ 的数量在离散意义上是连续的，根据介值定理可以得到本结论），所以 $b_i$ 后面也都是 $1$ ，此时 $a=b$ 。本结论得证。

于是现在的问题是，需要比较若干个区间翻转后的字典序的大小，将字符串翻转后使用后缀数组即可做到比较时 $O(1)$ 。

最终时间复杂度 $O(n\log^\mu(n))$ ，复杂度瓶颈在 SA 的构建。若使用倍增配合一般的排序求后缀数组， $\mu=2$ ，若改用基数排序， $\mu=1$ ，若利用 SA-IS 或 DC3 等科技， $\mu=0$ 。

代码

我的实现 $\mu=2$ ，足以通过本题。

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

constexpr int mod = 1e9 + 7;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

template<int N>
struct SuffixArray {
    int sa[N], rk[N], tmp[N];

    void build(const string &s){
        int n = s.size() - 1;
        for(int i=1;i<=n;i++) sa[i] = i, rk[i] = s[i];
        for(int k=1;k<n;k<<=1){
            auto mk = [=](int x){ return make_pair(rk[x], rk[x + k]); };
            sort(sa + 1, sa + n + 1, [mk](int x, int y){ return mk(x) < mk(y); });
            for(int i=1,p=0;i<=n;i++){
                if(mk(sa[i - 1]) == mk(sa[i])) tmp[sa[i]] = p;
                else tmp[sa[i]] = ++p;
            }
            copy(tmp + 1, tmp + n + 1, rk + 1);
        }
    }
};

const int N = 5e5 + 5;
int n, k;
string s;
SuffixArray<N> sa;

string solve0(){
    s = ' ' + s;
    int L = 1, R = n;
    string ret = s;
    for(int i=1;i<=k;i++){
        while(L <= n && s[L] != '1') L++;
        while(R >= 1 && s[R] != '0') R--;
        if(L > n || R < 1 || L > R) break;
        swap(ret[L], ret[R]);
        L++, R--;
    }
    return ret;
}

struct node{
    int pos, len;
    bool operator<(const node &rhs) const {
        return len == rhs.len ? sa.rk[pos] < sa.rk[rhs.pos] : len < rhs.len;
    }
};

string solve1(){
    reverse(s.begin(), s.end());
    s = " " + s;
    sa.build(s);
    int R = 0, cnt = 0, total = count(s.begin(), s.end(), '1');
    vector<node> vct;
    for(int L=1;L<=n;L++){
        while(R <= n && !((R - L + 1 >= total) && (total - cnt <= k - 1))) cnt += s[++R] == '1';
        if(R > n) break;
        vct.push_back({L, R - L + 1});
        cnt -= s[L] == '1';
    }
    auto [pos, len] = *min_element(vct.begin(), vct.end());
    string ret = s.substr(pos, len);
    int ext = total - count(ret.begin(), ret.end(), '1');
    reverse(ret.begin(), ret.end());
    for(char& ch : ret){
        if(ch == '0' && (--ext) >= 0) ch = '1';
    }
    reverse(ret.begin(), ret.end());
    return ret;
}

string wash(string s){
    s = s.substr(s.find('1'));
    if(s.empty()) s = "0";
    return s;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> k >> s;
    string ret1 = wash(solve0()), ret2 = wash(solve1()), ans;
    if(ret1.size() < ret2.size()) ans = ret1;
    else if(ret1.size() > ret2.size()) ans = ret2;
    else ans = min(ret1, ret2);
    int ret = 0;
    for(char ch : ans) ret = Add(Add(ret, ret), ch == '1');
    cout << ret << '\n';
    return 0;
}

// Written by xiezheyuan