Bit Flipping

题意翻译

### 题目描述 给定一个长为 $n$ 的 01 串，你可以进行 $k$ 次操作。每次操作中，你可以选择任意一位，并将除了这一位以外的其它位翻转（1 变 0,0 变 1），输出 $k$ 次操作后能获得的字典序最大的字符串，并输出每一位在操作中被选择的次数。若有多解输出任意一解。 01 串 $a$ 在字典序上大于 01 串 $b$ 当且仅当： - 在 $a$ 和 $b$ 从前往后第一个不同的位上，$a$ 为 $1$ 而 $b$ 为 $0$。 ### 输入格式 第一行一个正整数 $t$ 表示数据组数（$1\le t\le 1000$），接下来依次输入每组数据： 每组数据包括两行，第一行两个正整数 $n$ 和 $k$（$1\le n\le 2\cdot 10^5;0\le k\le 10^9$）； 第二行一个长度为 $n$ 的 01 串表示原始串。 各组数据的 $n$ 之和不超过 $2\cdot 10^5$。 ### 样例输出 对于每组数据输出两行。 第一行一个 01 串表示 $k$ 次操作后得到的字典序最大的 01 串。 第二行 $n$ 个数，记为 $f_1,f_2,…,f_n$，$f_i$ 表示这 $k$ 次操作中选到第 $i$ 位的次数。这些数之和需保证为 $k$。 ### 样例解释 对于第一组数据，下面是 3 次操作的过程： - 第一次选择第 1 位：$\color{red}{\underline{1}00001\rightarrow \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$，是能够得到的字典序最大的串。

题目描述

You are given a binary string of length $ n $ . You have exactly $ k $ moves. In one move, you must select a single bit. The state of all bits except that bit will get flipped ( $ 0 $ becomes $ 1 $ , $ 1 $ becomes $ 0 $ ). You need to output the lexicographically largest string that you can get after using all $ k $ moves. Also, output the number of times you will select each bit. If there are multiple ways to do this, you may output any of them. A binary string $ a $ is lexicographically larger than a binary string $ b $ of the same length, if and only if the following holds: - in the first position where $ a $ and $ b $ differ, the string $ a $ contains a $ 1 $ , and the string $ b $ contains a $ 0 $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. Each test case has two lines. The first line has two integers $ n $ and $ k $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ; $ 0 \leq k \leq 10^9 $ ). The second line has a binary string of length $ n $ , each character is either $ 0 $ or $ 1 $ . The sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output two lines. The first line should contain the lexicographically largest string you can obtain. The second line should contain $ n $ integers $ f_1, f_2, \ldots, f_n $ , where $ f_i $ is the number of times the $ i $ -th bit is selected. The sum of all the integers must be equal to $ k $ .

输入输出样例

输入样例 #1

6
6 3
100001
6 4
100011
6 0
000000
6 1
111001
6 11
101100
6 12
001110

输出样例 #1

111110
1 0 0 2 0 0 
111110
0 1 1 1 0 1 
000000
0 0 0 0 0 0 
100110
1 0 0 0 0 0 
111111
1 2 1 3 0 4 
111110
1 1 4 2 0 4

说明

Here is the explanation for the first testcase. Each step shows how the binary string changes in a move. - Choose bit $ 1 $ : $ \color{red}{\underline{1}00001} \rightarrow \color{red}{\underline{1}}\color{blue}{11110} $ . - Choose bit $ 4 $ : $ \color{red}{111\underline{1}10} \rightarrow \color{blue}{000}\color{red}{\underline{1}}\color{blue}{01} $ . - Choose bit $ 4 $ : $ \color{red}{000\underline{1}01} \rightarrow \color{blue}{111}\color{red}{\underline{1}}\color{blue}{10} $ . The final string is $ 111110 $ and this is the lexicographically largest string we can get.