天赐的算法笔记 02 - CF 2136B Like The Bitset

大家好，今天算法题的主题，从题目的 title 上就足以体现，与 bitset 有关。

简单说，bitset 就是用某种形式将二进制数据组织起来的一种数据类型，方便我们对其中的每个 bit 进行操作。C++ 中就有相关的数据类型，更通俗的说，本题中我们将会遇到二进制字符串，及由 $0$ 合 $1$ 构成的字符串。
传送门：
CF 2136B

问题描述

给定一个长度为 $n$ 的二进制字符串 $S$ ，以及一个整数 $k$ 。
Aquawave 想要构造一个长度为 $n$ 的排列 $p$ ，使得对于每个 $1 \leq i \leq n$ （其中 $S_i=1$ ）满足以下条件：

对于每个长度至少为 $k$ （即 $r-l+1 \geq k$ ）的区间 $[l,r]$ （ $1 \leq l \leq r \leq n$ ），若其覆盖位置 $i$ （即 $l \leq i \leq r$ ），则 $p_l,p_{l+1},\cdots,p_r$ 中的最大元素并非 $p_i$ 。

请注意，对于带有 $S_i=0$ 的索引不存在此类约束。
您需要找到这样的排列，或确定此类排列不存在。
二进制字符串是指每个字符均为 $0$ 或 $1$ 的字符串。
长度为 $n$ 的排列是指由 $n$ 个从 $1$ 到 $n$ 的不同整数以任意顺序组成的数组。例如， $[1,3,2,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（因为 $2$ 在数组中出现了两次）， $[1,3,4]$ 也不是排列（因为 $n=3$ 但数组中出现了 $4$ ）。

输入格式

输入可简单表示如下：

T
n k
S

其中， $T$ 表示测试用例的数量， $n$ 是要处理的二进制字符串的长度， $k$ 是问题描述中的整数， $S$ 是二进制字符串。

输出格式

在第一行，如果能构造出符合题意的排列，输出 Yes，否则输出 No。不区分大小写。
如果可以，在下一行打印出一个符合题意的排列 $p$ 。

问题分析

本题的目标有两个：

判断符合题意的解的存在性；
如果判断存在可行解，给出任意一个。

这样我们的目标就明确了，分两步走。
首先，如何判断解的存在性？
根据问题描述，我们可以得出以下结论：
符合题意的序列 $p$ 的任何一个长度大于或等于 $k$ 的区间中的元素 $p_i$ ，如果当前下标对应的二进制字符串中的 $S_i$ 为 $1$ ， $p_i$ 一定不是该区间中的最大值。
由于每个区间都要满足要求，我们只需要找出一个反例，就能证明该序列不存在。
我们考察 $S$ 中每个长度为 $k$ 的区间，若其中所有元素都为 $1$ ，说明排列中的对应区间中的每个元素都不能是该区间的最大值，但这个区间中一定会有唯一的一个最大值，所以排列 $p$ 不存在。
那么我们验证了所有长度为 $k$ 的区间，没有找到反例，就能证明一定存在这样的排列吗？答案是，一定可以。
在这种情况下，我们得到了一个重要结论：
当区间长度等于 $k$ ，其中一定有某个下标对应的 $S_i=0$ ，扩大区间的范围也不会改变这个性质。
我们只需要将区间的最大值放置在不受题目条件限制的位置，及 $S_i=0$ 的地方，就能构造出这个排列。
那么，我们需要逐一考察每个区间，针对每个区间一个个尝试可能得组合吗？答案是，不用。
由于题目只需要我们给出一个符合题意的答案，所以，使用一些方法，可以方便的构造出符合题意的排列。
下面是我的思路，也会有对这种思路合理性的证明，也欢迎大家在评论里给出自己的方法。

我的思路

将所有 $S_i=0$ 位置的 $p_i$ ，按先后顺序，设为 $n,n-1,...,n-m+1$ ，其中 $m$ 是 $S$ 中 $0$ 的个数。
将所有 $S_i=1$ 位置的 $p_i$ 按先后顺序，设为 $x,x-1,\cdots,2,1$ ，其中 $x$ 是 $S$ 中 $1$ 的个数。

显然， $x=n-m$。
根据上面的构造方法，我们可以得出结论：
使用该方法构造的排列中，每个长度大于等于 $k$ 的区间中的元素，都有 $p_i>p_j$ ，其中 $S_i=0$ ， $S_j=1$ 。
任意收缩或放大区间的范围都不会影响此性质，显然，这样的排列一定符合题意。
下面是实现代码：

#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> a(n + 1), p(n + 1);
    int m = n;
    int cnt = 0;

    for (int i = 0; i < n; i++)
    {
        a[i + 1] = s[i] - '0';
        if (!a[i + 1])
            p[i + 1] = m--;
        cnt = a[i + 1] * (cnt + 1); // 一旦 S_i 为 0，计数器就会被清零
        if (cnt == k)
        {
            cout << "NO\n"; // 不能构造排列
            return;
        }
    }
    cout << "YES\n"; // 可以构造排列

    for (int i = 1; i <= n; i++)
    {
        if (a[i])
            p[i] = m--;
    }
    for (int i = 1; i <= n; i++)
        cout << p[i] << ' ';
    cout << '\n';
}

int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

总结

我的思路的时空复杂度为 $O(n)$ 。其中蕴含了贪心的算法思想。好了，我要去看官方题解的思路了。