CF1237H Balanced Reversals

首先可以将相邻的两个点分到一个组中
特判无解的情况：00的数量不相等或11的数量不相等
若10的数量相等（此时01的数量也相等，因为知道10的数量后01的数量就确定了，\(cnt_{01}=\frac{n}{2}-cnt_{00}-cnt{11}-cnt{10}\)），可以发现这一规律：

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

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

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

\(bel=cnt_{01}-cnt_{10}\)

若相等，一定有\(bel_a==bel_b\)，若没有，设我们翻转\(a\)的前缀\(p\)可以使得\(bel_{a'}==bel_b\)，则可以列出式子\(bel_{a'}=bel_a-2*bel_p=bel_b\ \ \ \ \Rightarrow\ \ \ \ bel_p=\frac{bel_a-bel_b}{2}\)，可以通过分类\(cnt_{01}+cnt_{10}\)以及其对应的\(cnt_{01}\)与\(cnt_{10}\)的奇偶来讨论证明\(bel_a\)与\(bel_b\)的奇偶性相同

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

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

同理，若\(|bel_a|\leqslant|bel_b|\)，则是翻转\(b\)，此时\(bel_p=\frac{bel_b-bel_a}{2}\)

若翻转\(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;

}

巴特西

CF1237H Balanced Reversals

最新文章

热门文章