CF1237H Balanced Reversals

H - Balanced Reversals

1. 首先可以将相邻的两个点分到一个组中

2. 特判无解的情况：00的数量不相等或11的数量不相等

3. 若10的数量相等（此时01的数量也相等，因为知道10的数量后01的数量就确定了，cnt01=n2−cnt00−cnt11−cnt10），可以发现这一规律：

11 00 10 01 ⇒4,601 11 00 10，也就是说若想将某一组点放到队首并且此时除了这一组点的顺序是反的其他点的顺序照旧，只需进行两次操作，x−1,x+1（设x为当前这一组点的第一个的下标）

根据此规律，我们可以先构造出一个与所求序列刚好反过来的序列，最后再将构造出的这个序列翻一遍即可。为了节省次数，可以只处理前n−2个字符，因为保证所有所求序列中的点对在初始序列中都出现过，所以最后剩下这一点对一定就是所求序列末尾的点对（刚好对应上且顺序相同），于是最后的翻转就变成了翻转前n−2个字符

1. 若不相等，就先变成相等的再解决

bel=cnt01−cnt10

若相等，一定有bela==belb，若没有，设我们翻转a的前缀p可以使得bela′==belb，则可以列出式子bela′=bela−2∗belp=belb⇒belp=bela−belb2，可以通过分类cnt01+cnt10以及其对应的cnt01与cnt10的奇偶来讨论证明bela与belb的奇偶性相同

所以，枚举a的前缀求满足条件的前缀即可

但不一定是通过翻转a来使得相等，若翻转a，需要|bela|⩾|belb|，因为可以发现a的某一前缀的bel一定是其上一个前缀的bel值±1/0得到，也就是说从0到bela间的数（不包含0，包含bela）一定是a的某一前缀的bel，在这种情况下得到的belp一定是从0到bela间的某一个数（不包含0，包含bela），可以通过分类正负的方法证明

同理，若|bela|⩽|belb|，则是翻转b，此时belp=belb−bela2

若翻转a，则就是初始序列在一开始就先翻转；若翻转b，则是初始序列所有的翻转已完成后再翻转

#include<bits/stdc++.h>
using namespace std;
const int N=4005;
int n,bal_a,bal_b,bal0,bal1,ans[N],cnt,flag;
string a,b;
void rever(string &a,int r){ for(int i=0;r-i>i;++i) swap(a[i],a[r-i]); }
void rs(string &a,int t){
	int now=0;
	for(int i=0;i<n;i+=2){
		if(a[i]=='0'&&a[i+1]=='1') ++now;
		if(a[i]=='1'&&a[i+1]=='0') --now;
		if(now==t){
			flag=i+2,rever(a,i+1);
			break;
		}
	}
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		cin>>a,cin>>b,cnt=flag=bal_a=bal_b=bal0=bal1=0;
		n=a.size();
		for(int i=0;i<n;i+=2){
			if(a[i]=='0'&&a[i+1]=='1') ++bal_a;
			if(a[i]=='1'&&a[i+1]=='0') --bal_a;
			if(a[i]=='0'&&a[i+1]=='0') ++bal0;
			if(a[i]=='1'&&a[i+1]=='1') ++bal1; 
			if(b[i]=='0'&&b[i+1]=='1') ++bal_b;
			if(b[i]=='1'&&b[i+1]=='0') --bal_b;
			if(b[i]=='0'&&b[i+1]=='0') --bal0;
			if(b[i]=='1'&&b[i+1]=='1') --bal1;
		}
		if(bal0||bal1){ printf("-1\n"); continue; } 
		if(bal_a-bal_b){
			if(abs(bal_a)>=abs(bal_b)) rs(a,(bal_a-bal_b)/2),ans[++cnt]=flag,flag=0;
			else rs(b,(bal_b-bal_a)/2);
		}
		for(int i=0;i<n-2;i+=2)
			for(int j=i;j<n;j+=2)
				if(b[i]==a[j]&&b[i+1]==a[j+1]){
					(j)&&(ans[++cnt]=j),ans[++cnt]=j+2;
					rever(a,j-1),rever(a,j+1);
					break;
				}
		printf("%d\n",cnt+(n-2?1:0)+(flag?1:0));
		for(int i=1;i<=cnt;++i) printf("%d ",ans[i]);
		if(n-2) printf("%d ",n-2);
		if(flag) printf("%d",flag);
		printf("\n");
	}
	return 0;
}