Codeforces Round #658 (Div. 2)C1. Prefix Flip (Easy Version)（贪心）

从最后开始看，如果最后一个数不一样说明一定要转。PS:对于这样给定操作的题，把操作写成一个函数代码会比较清晰简单

AC代码：

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
//#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
vector<int>ans;
string a,b;
void invert(string &s,int len){
    for(int i=0;i<len;i++){
    	if(s[i]=='0')s[i]='1';
    	else s[i]='0';
	}
	//reverse(s.begin(),s.begin()+len);
	int l=0,r=len-1;
	while(l<r){
		swap(s[l],s[r]);
		l++,r--;
	}
	//cout<<s<<endl;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		cin>>a>>b;
		ans.clear() ;
		for(int i=n-1;i>=0;i--){
			if(a[i]!=b[i]){
				if(a[0]==b[i]&&i){
					ans.push_back(1);
					invert(a,1); 
				}
				invert(a,i+1);
				ans.push_back(i+1);
			}
		}
		cout<<ans.size();
		for(int i=0;i<ans.size();i++)cout<<" "<<ans[i];
		cout<<endl; 
	}
}

 

本文地址：https://blog.csdn.net/Alanrookie/article/details/107502242