「Codeforces 939D」Love Rescue

发表于 | | 阅读次数:
字数统计: 525 字

Description

题目链接：Codeforces 939D

Tolya 和 Valya 各有一条 T 恤，上面分别有一个长度为 $n$，由小写字母组成的字符串 $S$ 和 $T$。你现在要通过变换 $(c_1,c_2)$ 使得这两个字符串变得一样。

具体来说，你每次可以选择一对小写字母 $(c_1,c_2)$ 并将两个字符串中的 $c_1$ 都变成 $c_2$。你需要求出使两个字符串变成一样的最少变换次数，并输出方案。

数据范围：$1\le n\le 10^5$

Solution

这道题的思路真的很妙啊！QAQ

我们用并查集来维护变换的过程，如果两个字符 $a,b$ 在同一个并查集内，那么意味着他们可以直接或间接变换成为相同字符。反之如果在不同并查集内，那么意味着不能变成相同字符。

接下来考虑字符串 $S$ 和 $T$ 的每一个对应位置，如果 $S_i$ 和 $T_i$ 不相同，那么他们一定要通过一系列变换变成相同的。此时有 $2$ 种情况：

  1. $S_i$ 和 $T_i​$ 在同一个并查集内，那么他们一定在之前的变换中变成相同字符了，不需要增加变换。
  2. $S_i$ 和 $T_i$ 在不同的并查集内，这意味着他们还不是相同字符，需要将他们所在并查集的根节点变成相同的。

时间复杂度：$O(n\cdot\alpha(\vert S\vert))$（其中 $\vert S\vert$ 为字符集大小，本题中 $\vert S\vert=26$）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#include <cstdio>
#include <algorithm>

const int N=1e5+5;
int n,tot,fa[26];
char s[N],t[N],ans[N][2];

int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main() {
    scanf("%d%s%s",&n,s+1,t+1);
    for(int i=0;i<26;++i) fa[i]=i;
    for(int i=1;i<=n;++i) {
        if(find(s[i]-'a')!=find(t[i]-'a')) {
            ++tot;
            ans[tot][0]=find(s[i]-'a')+'a';
            ans[tot][1]=find(t[i]-'a')+'a';
            fa[find(s[i]-'a')]=find(t[i]-'a');
        }
    }
    printf("%d\n",tot);
    for(int i=1;i<=tot;++i) printf("%c %c\n",ans[i][0],ans[i][1]);
    return 0;
}
0%