题解：CF1243B2 Character Swap (Hard Version)

· · 题解

CF1243B2 题目传送门

题目大意

给你两个长度为 n 的只包含小写字母的字符串 S 和 T。最多进行 2n 次操作，每次选择两个数 i,j，其中 1 \leq i,j \leq n，交换 S_i,T_j。问能否使得 S 和 T 两个串完全相同。

解决思路

可以想到贪心。首先循环枚举两个串，直到发现某一位不同，再找从前往后第一个可以替换的字符，注意这里不是找与该字符位置相同的字符，而是第一个与 S 串该位置字符相同的字符。经过简单分析可得出两种情况：

最终看出最多的替换次数为 2 \times n 次，因此只需判断替换后是否可以相等即可。

注意事项

最终看出最多的替换次数为 2 \times n 次，因此只需判断替换后是否可以相等即可。

因此数组要开 2 \times n 的大小。

代码展示

#include <iostream>
#include <algorithm>
//拒绝万能头，从我做起
using namespace std;

const int N = 60; 
int k, n, ans[110][2];
char s[N], t[N];

int main()
{
    cin >> k;
    while(k--)
    {
        cin >> n >> s >> t;
        int cnt = 0;
        bool f1 = true;
        for(int i = 0; i < n; i++)
        {
            if(s[i] != t[i])
            {
                bool f2 = false;
                for(int j = i + 1; j < n; j++)
                {
                    if(s[i] == s[j])
                    {
                        ans[++cnt][0] = j;
                        ans[cnt][1] = i;
                        swap(s[j], t[i]);
                        f2 = true;
                        break;
                    }
                    if(s[i] == t[j])
                    {
                        ans[++cnt][0] = j;
                        ans[cnt][1] = j;
                        swap(s[j], t[j]);
                        ans[++cnt][0] = j;
                        ans[cnt][1] = i;
                        swap(s[j], t[i]);
                        f2 = true;
                        break;
                    }
                }
                if(!f2)
                {
                    f1 = false;
                    break;
                }
            }
        }
        if(!f1) cout << "No" << endl;
        else
        {
            cout << "Yes" << endl << cnt << endl;
            for(int i = 1; i <= cnt; i++)
                cout << ans[i][0] + 1 << " " << ans[i][1] + 1 << endl;
        }
    }
    return 0;
}