B. Bit Flipping

思路:分情况讨论,一个数

x

x

x翻转偶数次不变,翻转奇数次变成x^1

1.

k

k

k为奇数,则如果一个数不被选到,那么翻转k(奇数次),则原来是

0

0

0就能变成1,原来是

1

1

1就变成

0

0

0。那么,我们肯定优先从左到右,优先翻转原来为

1

1

1的,这样前面尽可能多的的

1

1

1被翻转了

k

1

k - 1

k1次,翻转偶数次还是1。

2.k为偶数,同理,我们肯定优先从左到右优先翻转原来为

0

0

0的。

3.假设操作完

1

1

1或者2以后还有剩余,就把剩余的

k

k

k全部给最后一个。假如最后剩下的

k

k

k为偶数,则翻转没有任何效果。假如最后剩下的

k

k

k为奇数,为了使字典序最大,优先把最后一个改成

0

0

0(因为k多出来了,前面肯定都是

1

1

1了)。

代码:

#include <bits/stdc++.h>
#define PII pair<int,int>
#define LL long long
#define fi first
#define debug(x) cout << #x << " = " << x << endl;
#define se second
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define sz(x) (int)x.size()
#define INF 2e9
#define mod 998244353

using namespace std;

const int N = 200010;
int n, k;
char str[N];
int ans[N];

void solve()
{
	cin >> n >> k;
	scanf("%s", str + 1);
	for(int i = 1; i <= n; i ++ ) ans[i] = 0;
	if(k % 2 == 1){
		for(int i = 1; i <= n; i ++ ){
			if(str[i] == '1' && k){
				k --;
				ans[i] ++;
			}else if(str[i] == '1'){
				str[i] = '0';
			}else{
				str[i] = '1';
			}
		}
		ans[n] += k;
		if(k % 2 == 1){
			if(str[n] == '1') str[n] = '0';
			else str[n] = '1';
		}
	}else{
		for(int i = 1; i <= n; i ++ ){
			if(str[i] == '0' && k){
				k --;
				str[i] = '1';
				ans[i] ++;
			}
		}
		ans[n] += k;
		if(k % 2 == 1){
			if(str[n] == '1') str[n] = '0';
			else str[n] = '1';
		}		
	}
	printf("%s\n", str + 1);
	for(int i = 1; i <= n; i ++ ){
		cout << ans[i] << " ";
	}
	cout << endl;
}

int main()
{
	int test = 1;
	scanf("%d",&test);
	while(test -- )
	{
		solve();
	}
	return 0;
}