专栏文章

题解：CF1243B2 Character Swap (Hard Version)

RRex01
CF1243B2题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqbhw9g
此快照首次捕获于
2025/12/04 02:05
3 个月前
此快照最后确认于
2025/12/04 02:05
3 个月前
查看原文

CF1243B2 题目传送门

题目大意

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

解决思路

可以想到贪心。首先循环枚举两个串，直到发现某一位不同，再找从前往后第一个可以替换的字符，注意这里不是找与该字符位置相同的字符，而是第一个与 SS 串该位置字符相同的字符。经过简单分析可得出两种情况：
  • 可以替换的字符在 SS 串内，直接替换即可；
  • 可以替换的字符不在 SS 串内，要先把该字符换到 SS 串中，然后再替换。
最终看出最多的替换次数为 2×n2 \times n 次，因此只需判断替换后是否可以相等即可。

注意事项

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

代码展示

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...