题解：CF1381A1 Prefix Flip (Easy Version)

蒟 / 2024-07-19 / 原文

思路

~~这道题直接用下一题的代码就行了~~

$C1$：

注意到限制 $3n$ 很大，于是看每一位是不是一样的，再操作，如样例一：

转化第一位：$01 \to 11$。

转化第二位：$11 \to 00 \to 10$。

每次把当前位子提到第一位，然后翻转第一位，最后翻转回去，最多 $3n$ 次，不用暴力操作直接计答案时间复杂度 $O(n)$。

$C2$：

注意到限制 $2n$ 缩小了，考虑将每一位转化为相同的 $0/1$，如样例二：

转化第一个字符串：$01011 \to 11011 \to 00011 \to 11111$。

转化第二个字符串：$11100 \to 00000$。

这个可以从前面开始遍历，如果这个位置与后一个位置不同，那么就对这一个位置之前的进行操作，这样可以保证在处理这个位置时前面的位置上的数全部相同在转化第二个字符串时因为一、二、四位都在转化时满足要求，所以跳过了这几个步骤。

把两个字符串都进行上面的操作，会的到两个全是 $0/1$ 的字符串，如果不相同的话再整体翻转一次就行了，最多 $n-1+n-1+1$ 次，即 $2n - 1$ 次操作满足要求。

Code

就只放 $C2$ 的代码了

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int n;

char a[N],b[N];

int ans1[N],ans2[N];

int main() {
	ios::sync_with_stdio(0);
	int T;
	cin>>T;
	while(T--) {
		cin>>n>>(a+1)>>(b+1);
		int res1 = 0,res2 = 0; 
		for(int i = 1; i < n; ++i) {
			if(a[i] != a[i+1]) ans1[++res1] = i;
			if(b[i] != b[i+1]) ans2[++res2] = i;
		}
		if(a[n] != b[n]) ans1[++res1] = n;
		cout<<res1 + res2<<"\n";
		for(int i = 1; i <= j; ++i)	cout<<ans1[i]<<" ";
		for(int i = k; i > 0; --i) cout<<ans2[i]<<" ";
		cout<<"\n";
	}
	return 0;
}