CF1204D2 Kirk and a Binary String (hard version)

形式化题意

给你一个长为 的仅包含 和 的串，要求尽可能多地将里面的 改成 使得在得到的新串中，对于 ，两个串的 区间内的最长不降子序列等长。

策略分析

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

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

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

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

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

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

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

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

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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();
}