题解：CF1923F Shrink-Reverse
xiezheyuan
·
·
题解
明天要讲 SA，提前写一道 SA 题。
简要题意
有一个长度为 n 的 01 串 S，你可以执行下列两种操作至多 k 次：
- 交换：选定 1\leq i,j\leq n 并交换 S_i,S_j。
- Shrink-Reverse 变换（以下简称变换）：先删除 S 的所有前导 0，然后将 S 翻转。
你需要使 S 表示的二进制数尽可能小，输出这个二进制数值的最小值对 10^9+7 取模。
## 思路
超级高明题，难点不在 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$，足以通过本题。
```cpp
#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
```