题目链接：https://codeforces.com/contest/1382/problem/C2
给定一个只有0和1的字符串。定义操作为：取这个字符串的一段前缀，将这段前缀的所有位取反后翻转。求如何进行操作可以得到目标串
这个看了一眼提示......考虑先变成全0的串，然后再变成目标串（这个是怎么想到先变成全0的？？）。这两个过程都只需要至多n步。对于变成全0的过程，只要判断i和i+1位是否相同。如果不相同则对i进行操作。最后得到一个全1或全0的串，如果是全1的串再对n操作一次即可。对于全0串变成目标串的过程，我是用一个cnt判断当前操作了奇数次或偶数次，从而判断当前位置是否需要操作。详见代码的那个比较长的if
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;
int t,n,i,j,k;
char s1[maxn],s2[maxn];
void solve(){
vector<int> ans;
int num=0;s1[n+1]=‘0‘;
for (i=1;i<=n;i++)
if (s1[i]!=s1[i+1]) {
ans.push_back(i);num++;
}
for (i=1;i<=n;i++) s1[i]=‘0‘;
int cnt=0;
for (i=n;i>=1;i--)
if ((s2[i]==‘1‘&&cnt%2==0)||s2[i]==‘0‘&&cnt%2==1){
ans.push_back(i);
num++;cnt++;
}
cout<<num<<endl;
for (i=0;i<ans.size();i++) cout<<ans[i]<<‘ ‘;
cout<<endl;
}
int main(){
cin>>t;
while (t--){
cin>>n;
cin>>s1+1>>s2+1;
solve();
}
return 0;
}
原文：https://www.cnblogs.com/edmunds/p/13398495.html