CF1659B Bit Flipping

给定一个长度为 $n$ 的二进制字符串。你有恰好 $k$ 次操作机会。每次操作，你必须选择一个比特位。除了被选择的那个比特位外，其余所有比特位的状态都会翻转（$0$ 变为 $1$，$1$ 变为 $0$）。你需要输出在用完所有 $k$ 次操作后，能够得到的字典序最大的字符串。同时，输出每个位被选择的次数。如果有多种方案，可以输出任意一种。 对于长度相同的二进制字符串 $a$ 和 $b$，当且仅当在第一个不同的位置，$a$ 的该位为 $1$ 且 $b$ 的该位为 $0$ 时，$a$ 的字典序大于 $b$。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。 每个测试用例包含两行。第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5$；$0 \leq k \leq 10^9$）。 第二行包含一个长度为 $n$ 的二进制字符串，每个字符为 $0$ 或 $1$。 所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出两行。 第一行输出你能得到的字典序最大的字符串。 第二行输出 $n$ 个整数 $f_1, f_2, \ldots, f_n$，其中 $f_i$ 表示第 $i$ 位被选择的次数。所有整数之和必须等于 $k$。

以下是第一个测试用例的解释。每一步展示了在一次操作后字符串的变化。 - 选择第 $1$ 位：$\color{red}{\underline{1}00001} \rightarrow \color{red}{\underline{1}}\color{blue}{11110}$。 - 选择第 $4$ 位：$\color{red}{111\underline{1}10} \rightarrow \color{blue}{000}\color{red}{\underline{1}}\color{blue}{01}$。 - 选择第 $4$ 位：$\color{red}{000\underline{1}01} \rightarrow \color{blue}{111}\color{red}{\underline{1}}\color{blue}{10}$。 最终字符串为 $111110$，这是可以得到的字典序最大的字符串。 由 ChatGPT 4.1 翻译