「Codeforces 939D」Love Rescue

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%