[Codeforces] CF1659B Bit Flipping

题面

给定一个长为 \(n\) 的 01 串，你可以进行 \(k\) 次操作。每次操作中，你可以选择任意一位，并将除了这一位以外的其它位翻转（\(1\) 变 \(0\),\(0\) 变 \(1\)），输出 \(k\) 次操作后能获得的字典序最大的字符串，并输出每一位在操作中被选择的次数。若有多解输出任意一解。

思路

可以发现，操作的从次数对于每个位置被操作的次数都有影响。

• 如果\(k\)是奇数，那么每个位置都会被翻过奇数次，也就是\(1\)次

• 如果\(k\)是偶数，那么每个位置就不会被翻转

所以对应的如果\(k\)是奇数的，那每次保护的（即不会被翻转的）应该是\(0\)

反之，如果\(k\)是偶数，那么每次就保护\(1\)

可以发现，如果想要字典序最大，所保护的\(0\)或\(1\)都应该尽量靠前

当所有的都被操作后，剩余的操作就都放在最后一位即可

被保护：即每次翻转时，需要选择一个的位置，使其不变

代码

#include<bits/stdc++.h>
using namespace std;
const int Maxn=2e5+10;
int n,k,now;
string s;
int ans[Maxn];
void run()
{
	cin>>n>>k>>s;now=k;memset(ans,0,(n+1)*4);
	for(int i=1;i<n && now;i++)
	{
		if(s[i-1]=='1' && k%2==1) ans[i]++,now--;
		else if(s[i-1]=='0' && k%2==0) ans[i]++,now--;
	}
	ans[n]+=now;
	for(int i=1;i<=n;i++) if((k-ans[i])%2==1) s[i-1]=(s[i-1]=='0'?'1':'0');
	cout<<s<<endl;
	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
	cout<<endl;
}
int main()
{
	int t;
	cin>>t;
	while(t--) run();
}