题解：CF1243B2 Character Swap (Hard Version)

· · 题解

首先我们先来考虑怎么判断 Yes 和 No，只要判断一下每个字母的数量是不是有偶数个就可以了，如果是奇数肯定不能平均分配给 s 和 t。（可以先做一下 Easy Version，感觉比本题的判断 Yes 和 No 还要复杂一点）。

接下来就要考虑如何操作，使得 s 和 t 相等，注意：操作次数不需要最少，只要不超过 2n 就可以。

我们可以设 l_{a} 表示 s 和 t 两个字符串中 a 字母数量的总和，那么 l_{a}\div2 就是操作后两个字符串中 a 字母应有的数量，设 sl_{a} 表示 a 字母在 s 中的数量，如果 s_{i}\ne t_{i}，此时需要进行操作，操作分为两种情况。

如果 sl_{s_{i}}\times 2\le l_{s_{i}}（用 \times 2 可以减少 \div2 下取整的问题），直接交换 s_{i} 和 t_{i}，此时 t_{i+1} 到 t_{n} 一定有 t_{j}=t_{i}（t_{i} 也就是交换前的字符 s_{i}），找到 s_{j}\ne t_{j}（已经相等的位置，尽量不要去破坏它）并且 t_{j}=t_{i} 后，交换 s_{i} 和 t_{j}，此时满足 s_{i}=t_{i}。

如果 sl_{s_{i}}\times 2> l_{s_{i}}，那么 s_{i+1} 到 s_{n} 一定存在 s_{j}=s_{i}，找到 s_{j}\ne t_{j} 并且 s_{j}=s_{i} 后，交换 s_{j} 和 t_{i}，此时满足 s_{i}=t_{i}。

注意：l 和 sl 要随时更新。

那么这种方法的操作次数是否不超过 2n 呢？让我们来证明一下。

可以发现如果 s_{i}\ne t_{i}，那么最坏的情况就是 sl_{s_{i}}\times 2\le l_{s_{i}}，需要操作两次，即使 s 和 t 每一位都不相同，每次都是最坏情况，那么也只需要进行 2n 次，所以这种操作方法是合法的。

代码如下：

#include<bits/stdc++.h>
using namespace std;
char s[55],t[55];
int sl[30],l[30];
struct Node{
    int l,r;
}ans[105];
int main(){
    int k;
    scanf("%d",&k);
    while(k--){
        int n;
        scanf("%d",&n);
        scanf("%s%s",s+1,t+1);
        int cnt=0;
        for(int i=0;i<26;i++) l[i]=sl[i]=0;
        for(int i=1;i<=n;i++){
            sl[s[i]-'a']++;
            l[s[i]-'a']++;
            l[t[i]-'a']++;
        }
        int f=0;
        for(int i=0;i<26;i++){
            if(l[i]%2){
                f=1;
                break;
            }
        }
        if(f){
            printf("No\n");
            continue;
        }
        printf("Yes\n");
        for(int i=1;i<=n;i++){
            if(s[i]!=t[i]){
                if(sl[s[i]-'a']*2<=l[s[i]-'a']){
                    swap(s[i],t[i]);
                    ans[++cnt]={i,i};
                    sl[t[i]-'a']--;
                    sl[s[i]-'a']++;
                    for(int j=i+1;j<=n;j++){
                        if(t[i]==t[j]&&s[j]!=t[j]){
                            swap(s[i],t[j]);
                            ans[++cnt]={i,j};
                            sl[t[j]-'a']--;
                            sl[s[i]-'a']++;
                            break;
                        }
                    }
                }
                else{
                    for(int j=i+1;j<=n;j++){
                        if(s[i]==s[j]&&s[j]!=t[j]){
                            swap(s[j],t[i]);
                            ans[++cnt]={j,i};
                            sl[t[i]-'a']--;
                            sl[s[j]-'a']++;
                            break;
                        }
                    }
                }
            }
        }
        printf("%d\n",cnt);
        for(int i=1;i<=cnt;i++){
            printf("%d %d\n",ans[i].l,ans[i].r);
        }
    }
    return 0;
}