← 返回题目列表

Codeforces · 2136/B

B. 喜欢 Bitset

中文机器翻译题面 查看原题

给你一个长度为$$$n$$$的二进制字符串$$$^{\text{*}}$$$ $$$s$$$,以及一个整数$$$k$$$。

Aquawave 想要构造一个长度为 $$$n$$$ 的排列$$$^{\text{†}}$$$ $$$p$$$,因此对于每个 $$$1\le i\le n$$$,其中 $$$s_i=\mathtt{1}$$$,以下成立:

  • 对于每个长度至少为$$$k$$$(即$$$r - l + 1 \geq k$$$)的区间$$$[l, r]$$$ ($$$1\le l\le r\le n$$$),如果它覆盖位置$$$i$$$(即$$$l \leq i \leq r$$$),则其中的最大元素$$$p_l, p_{l+1}, \ldots, p_r$$$ 是 不 $$$p_i$$$。

请注意,有 no 对 $$$s_i = \mathtt{0}$$$ 的索引的此类约束。

你必须找到这样的排列,或者确定这样的排列不存在。

$$$^{\text{*}}$$$二进制字符串是每个字符为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$ 的字符串。

$$$^{\text{†}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq n$$$) — $$$s$$$ 的长度和语句中的整数。

第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$ ($$$s_i = \mathtt{0}$$$ 或 $$$\mathtt{1}$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例:

  • 如果至少存在一种可能的排列:
    • 打印“是"在输出的第一行;
    • 然后,在第二行打印 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$, 所有 $$$p_i$$$-s 都是不同的) — 您构建的排列。
  • 否则,打印“NO”在单行输出中。

您可以在任何情况下输出令牌(上限或下限)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

如果有多个答案,您可以输出其中任何一个。

示例

输入
复制

6
2 1
00
4 3
0010
5 2
11011
7 5
1111110
8 4
00101011
10 2
1000000010

输出
复制

YES
1 2
YES
1 4 3 2
NO
NO
YES
6 5 2 3 4 8 1 7
YES
1 2 3 4 5 6 7 9 8 10

注意

在第一个测试用例中,您可以输出长度 $$$n = 2$$$ 的任意排列,因为所有 $$$s_i$$$-s 都等于 $$$\mathtt{0}$$$。

在第二个测试用例中, $$$p=[1, 4, 3, 2]$$$ 是有效答案,因为:

  • $$$s_i = \tt{1}$$$ 的唯一位置是 $$$i = 3$$$。存在三个不同的区间 $$$[l, r]$$$ 覆盖索引 $$$3$$$,其长度至少为 $$$k=3$$$:$$$[1, 3]$$$、$$$[1, 4]$$$ 和 $$$[2, 4]$$$;
  • 并且,对于三个区间中的每一个,$$$p_l, \ldots, p_r$$$ 中的最大元素应该是 $$$p_2 = 4$$$,它不等于 $$$p_3 = 3$$$。