题解 CF1204D2 Kirk and a Binary String (hard version)

CF1204D2 Kirk and a Binary String (hard version)

形式化题意

给你一个长为 $n$ 的仅包含 $0$ 和 $1$ 的串，要求尽可能多地将里面的 $1$ 改成 $0$ 使得在得到的新串中，对于 $\forall l,r\in [1,n](l \le r)$，两个串的 $[l,r]$ 区间内的最长不降子序列等长。

策略分析

题中给的数据范围是 $10^5$，我们很容易去思考一些 $O(n \log n)$ 的做法，从而去找数据结构来维护，但这是 CF 的题，所以我们坚信这一定是一道人类智慧题。所以我们充分发扬人类智慧，$O(n)$ 来构造这个题。

对于只有 $0,1$ 的串来讲，一个序列想要不降其实只需要满足两个条件：

• 如果当前位为 $0$，那么后面无论 $0,1$ 都是不降的；
• 如果当前位为 $1$，那么后面为 $1$ 才是不降的。

那么我们是不是很容易发现本题的构造原则：一个 $1$ 能够被替换成 $0$ 当且仅当这个 $1$ 后面的 $1$ 的个数大于等于 $0$ 的个数。这个结论说出来很抽象，我们用一个例子来理解。

0 1 1 1 1 1 0 0 0
1 2 3 4 5 6 7 8 9 

为了方便读者观看，这个串下面的数字是其下标。我们以下标为 $2$ 的这个下标的位置为例，$[2,9]$ 区间内的最长不降子序列是 1 1 1 1 1，这一位改成 $0$ 后变成 0 1 1 1 1，不管怎么变长度都不会变，因为其后 $1$ 比 $0$ 多，最长不降子序列一定是连着一坨 $1$。然而对于下标为 $4$ 这个位置的 $1$ 来讲，这一位后面的 $0$ 比 $1$ 多，我们将这一位换成 $0$ 后，$[4,9]$ 区间内的最长不降子序列从 1 1 1 变成了 0 0 0 0，不符合我们的构造条件。

出现这种情况的原因是，对于当前位来讲，它的最长不降子序列只能是一堆 $1$，这是我们刚刚提到过的结论，改成 $0$ 后就有了三种选择，而我们必须让它别无选择，这就要求更改的这一位只能继续选后面连一堆 $1$，那么我们发现这种别无选择的情况就必须让当前位后的 $1$ 的数量比 $0$ 的数量多，这就证明了我们刚刚得出的结论，这道题也就做完了。

在写代码的时候，我们可以把维护个数改成维护 $0$ 与 $1$ 的个数的差值，这样可以简化代码难度，当 $0$ 的个数减去 $1$ 的个数非正时就把这一位的 $1$ 换掉。

参考代码

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

namespace SHAWN {
    string s;
    int cnt;
    int work()
    {
        cin >> s;
        for (int i = s.size() - 1; i >= 0; --i) {
            if (s[i] == '0') { ++cnt; }
            else if (s[i] == '1' && cnt <= 0) { s[i] = '0'; }
            else { --cnt; }
        }
        cout << s << '\n';
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}