【CF1243B2】Character Swap (Hard Version)【思维】

题意：给定两个字符串，问是否存在交换方案使得两个字符串相同，方案为交换次数小于等于2n，且每次只交换s1与s2中的一个字符

题解：考虑从前往后枚举，当第i位不同时，考虑找后边的第j位，若存在这样的第j位，则存在方案

1、存在aj==ai且j>i，那么交换aj,bi

2、存在bj==ai且j>i，那么先交换aj,bj，在交换aj,bi

这样对于每个位置最多两次操作，故若存在方案则一定在2n次内交换完成

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
using namespace std;
int T,n;
char s1[51],s2[51];
struct node
{
    int a,b;
}mdf[1001];
int mdfn;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
      scanf("%d%s%s",&n,s1,s2);
      bool fl=0;mdfn=0;
      for(int i=0;i<n;i++)
      {
        if(s1[i]!=s2[i])
        {
          fl=0;
          for(int j=i+1;j<n;j++)
          {
            if(s1[j]==s1[i])
            {
              mdf[++mdfn]=(node){j,i};
              swap(s1[j],s2[i]);
              fl=1;break;
            }
            if(s2[j]==s1[i])
            {
              mdf[++mdfn]=(node){j,j};
              swap(s1[j],s2[j]);
              mdf[++mdfn]=(node){j,i};
              swap(s1[j],s2[i]);
              fl=1;break;
            }
          }
          if(!fl){printf("No
");fl=0;break;}
          fl=0;
        }
        if(i==n-1)fl=1;
      }
      if(fl)
      {
        printf("Yes
%d
",mdfn);
        for(int i=1;i<=mdfn;i++)printf("%d %d
",mdf[i].a+1,mdf[i].b+1);
      }
    }
    return 0;
}