CF-1243B2 Character Swap (Hard Version) 题解

题目大意

给你一个长度为n的两个字符串，你可以交换$s1[i],s2[j]$，最多可以交换2n次，需要你判断能否使两字符串相同，能的话输出交换顺序。

解题思路

说实话这个题目还真不难。。

但是我就是没想到啊啊啊。

感觉自己脑袋越来越不好用了。

这个字符串长度不长，可以直接用模拟。

模拟两个字符串的交换过程，并且记录交换顺序即可。

当他们两个位置相同的时候不需要去交换。

然后交换的时候分两种情况，具体看代码吧。

顺便记录一下，了解到了一个新算法：sunday算法，用来匹配字符串的，有机会之后再补。

完整代码

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

vector<pair<int,int>>v;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		char s1[100], s2[100];
		cin >> s1+1 >> s2+1;
		int cnt[200];
		memset(cnt, 0, sizeof(cnt));
		v.clear();
		for (int i = 1; i <= n; i++) {
			cnt[s1[i]]++, cnt[s2[i]]++;
		}
		int flag = 1;
		for (int i = 'a'; i <= 'z'; i++) {
			if (cnt[i] & 1) {
				flag = 0;
				break;
			}
		}
		if (!flag) {
			cout << "No" << endl;
			continue;
		}
		cout << "Yes" << endl;
		int c = 0;
		for (int i = 1; i <= n; i++) {
			if (s1[i] != s2[i]) {
				for (int j = i + 1; j <= n; j++) {
					if (s1[i] == s1[j]) {
						swap(s2[i], s1[j]);
						v.push_back(make_pair(j, i));
						c++;
						break;
					}
					if (s1[i] == s2[j]) {
						swap(s1[i + 1], s2[j]);
						v.push_back(make_pair(i+1, j));
						swap(s2[i], s1[i + 1]);
						v.push_back(make_pair(i+1, i));
						c += 2;
						break;
					}
				}
			}
		}
		cout << c << endl;
		for (auto x : v) {
			cout << x.first << ' ' << x.second << endl;
		}
	}
}