题面
给定一个长为 \(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();
}