一、核心结论（官方解法）

这道题的解法极其简洁，只有两个关键点：

1. 无解判定： 如果二进制串 $s$ 中存在一段长度 $\ge k$ 的连续 $1$，直接输出 $\boldsymbol{NO}$。

   $$\text{存在 } [l,r],\ r-l+1 \ge k \text{ 且 } s_l=s_{l+1}=\dots=s_r=1 \implies \text{无解} $$

2. 有解构造： 把所有 $s_i=1$ 的位置从小到大填 $1,2,\dots,c$（$c$ 是 $1$ 的个数）。 把所有 $s_i=0$ 的位置从小到大填 $c+1,c+2,\dots,n$。 这个构造一定合法。

二、严谨证明（官方思路翻译）

1. 为什么连续 $1$ 长度 $\ge k$ 一定无解？

假设存在一段全 $1$ 的区间 $[l,r]$，满足：

这段区间里的每个位置 $i$ 都有 $s_i=1$，都必须满足： 所有长度 $\ge k$ 且包含 $i$ 的区间，最大值都不能是 $p_i$。

但这段 $[l,r]$ 本身就是一个长度 $\ge k$ 的区间，且里面所有位置都受约束。 区间里一定有一个位置是最大值，而这个位置的 $s_i=1$，违反约束。 $\implies$ 无解。

2. 为什么其他情况一定可以构造？

我们的构造规则：

• $s_i=1$ 的位置：填小数 $1 \sim c$
• $s_i=0$ 的位置：填大数 $c+1 \sim n$

对于任意长度 $\ge k$ 的区间 $[l,r]$： 因为没有长度 $\ge k$ 的连续 $1$，所以这个区间里至少有一个 $0$。 这个 $0$ 位置填的数一定比所有 $1$ 位置的数都大。

因此：

• 所有受约束的位置（$s_i=1$），永远不会成为任何长区间的最大值
• 直接满足题目所有要求

三、标程代码逐行详解

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n, k; 
	cin >> n >> k;
	string s; 
	cin >> s;
    // 前面加一个空格，让下标从 1 开始，方便处理
	s = " " + s;

    // 双指针：寻找所有连续 1 的段
	for (int i = 1, j = 1; i <= n; i = ++j) {
        // 当前是 1，开始统计连续段
		if (s[i] == '1') {
            // 一直往后跳，直到不是 1
			while (j < n && s[j + 1] == '1') j++;
            // 如果这段长度 >=k，直接输出 NO
			if (j - i + 1 >= k) {
				puts("NO");
				return;
			}
		}
	}

    // 没有非法段，输出 YES
	puts("YES");

    // c1：给 1 位置填的数（1,2,...）
    // c2：给 0 位置填的数（从 c+1 开始）
	int c1 = 0;
	int c2 = count(s.begin(), s.end(), '1');

	for (int i = 1; i <=n; i++) {
		if (s[i] == '1') cout << ++c1 << " ";
		else cout << ++c2 << " ";
	}
	cout << "\n";
}

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

四、代码执行逻辑

步骤 1：双指针检查连续 1

遍历字符串，找到每一段连续的 $1$。 如果某一段长度 $\ge k$，直接输出 $\text{NO}$。

步骤 2：统计 1 的个数

$c2 =$ 字符串中 $1$ 的数量。

步骤 3：构造排列

• 遇到 $s_i=1$：填 $1,2,3,\dots$
• 遇到 $s_i=0$：填 $c+1,c+2,\dots,n$

五、复杂度分析

• 时间复杂度：$\boldsymbol{O(n)}$ 每组测试用例
• 空间复杂度：$\boldsymbol{O(n)}$
• 满足题目限制：$\sum n \le 2 \times 10^5$

六、极简总结

1. 只要有一段连续 $1$ 长度 $\ge k$ $\rightarrow$ 输出 NO
2. 否则：1 填小数，0 填大数 $\rightarrow$ 输出 YES + 构造排列

这就是这道 *900 构造题的最优、最短、最清晰解法。