【题解】CF1215C Swap Letters

题面传送门

解决思路

首先容易得知，两个字符串中 \(b\)（或 \(a\)）的个数为偶数时，一定有解。为奇数则一定无解。

其次考虑怎么交换。对照样例三：

in:

8

babbaabb

abababaa

out:

发现，每一对交换的字符有共同点：

要不是串一都为 \(a\)，串二都为 \(b\) 的一对
要不是串一都为 \(b\)，串二都为 \(a\) 的一对

简单思考后发现这样成对交换就是最优的。（换一次就可以匹配上两位）

于是，考虑先统计出串一为 \(a\)，串二为 \(b\) 的位数 \(cnt1\)，并将相应位置存入 \(ans1\) 数组。同时统计出串一为 \(b\)，串二为 \(a\) 的位数 \(cnt2\)，并将相应位置存入 \(ans2\) 数组。

这时发现一个问题，\(cnt1\) 和 \(cnt2\) 不一定为偶数，有可能不能各自成对匹配完。但可以发现， \(cnt1\) 与 \(cnt2\) 必同奇偶。由于偶数成对匹配更优，所以只可能剩下 一位串一为 \(a\)，串二为 \(b\) 与 一位串一为 \(b\)，串二为 \(a\) 。

这时就出现了样例一的情况：

in:

4

abab

aabb

out:

所以只要按着样例一的顺序特判输出即可：

printf("%d %d\n",ans1[cnt1],ans1[cnt1]);

printf("%d %d\n",ans1[cnt1],ans2[cnt2]);

AC Code

#include<bits/stdc++.h>

using namespace std;

int n,ans1[200005],ans2[200005],cnt,cnt1,cnt2;

string s1,s2;

int main(){

	scanf("%d",&n);

	cin>>s1>>s2;

	for(int i=0;i<n;i++){

		if(s1[i]=='b') cnt++;

		if(s2[i]=='b') cnt++;

	}

	if(cnt%2==1) printf("-1");

	else{

		for(int i=0;i<n;i++){

			if(s1[i]=='a'&&s2[i]=='b') ans1[++cnt1]=i+1;

			if(s2[i]=='a'&&s1[i]=='b') ans2[++cnt2]=i+1;

		}

		if(cnt1%2==0){

			printf("%d\n",cnt1/2+cnt2/2);

			for(int i=1;i<=cnt1;i+=2){

				printf("%d %d\n",ans1[i],ans1[i+1]);

			}

			for(int i=1;i<=cnt2;i+=2){

				printf("%d %d\n",ans2[i],ans2[i+1]);

			}

		}

		else{

			printf("%d\n",cnt1/2+cnt2/2+2);

			for(int i=1;i<=cnt1-1;i+=2){

				printf("%d %d\n",ans1[i],ans1[i+1]);

			}

			for(int i=1;i<=cnt2-1;i+=2){

				printf("%d %d\n",ans2[i],ans2[i+1]);

			}

			printf("%d %d\n",ans1[cnt1],ans1[cnt1]);

			printf("%d %d\n",ans1[cnt1],ans2[cnt2]);

		}

	}

	return 0;

}

巴特西

【题解】CF1215C Swap Letters

题面传送门

解决思路

AC Code

最新文章

热门文章