题面传送门
解决思路
首先容易得知,两个字符串中 \(b\)(或 \(a\)) 的个数为偶数时,一定有解。为奇数则一定无解。
其次考虑怎么交换。对照样例三:
in:
8
babbaabb
abababaa
out:
3
2 6
1 3
7 8
发现,每一对交换的字符有共同点:
要不是串一都为 \(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:
2
3 3
3 2
所以只要按着样例一的顺序特判输出即可:
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;
}