CF1800E2. Unforgivable Curse (hard version) 题解并查集

劝君 / 2024-11-17 / 原文

题目链接：https://codeforces.com/contest/1800/problem/E2

视频讲解：https://www.bilibili.com/video/BV1tZ1FYPELp?p=2

把下标 $i$ 对应到图中编号为 $i$ 的节点。

节点 $i$ 和 $i+k$ 之间连一条边，节点 $i$ 和 $i+k+1$ 之间也连一条边。

同一个连通块里的节点对应的字符可以互相换。

然后可以发现，在和节点 $i$ 处在同一个并查集的所有节点（对应到字符串 $s$ 和 $t$ 中是下标）在 $s$ 和 $t$ 中的所有字符必须是一样的。

具体来说，假设节点 $2$ 所在的连通块的节点集合为 $\{ 2, 3, 4, 5, 7, 11 \}$，则：

$s_2, s_3, s_4, s_5, s_7, s_{11}$ 中字符 'a' 出现的次数需要和 $t_2, t_3, t_4, t_5, t_7, t_{11}$ 中字符 'a' 出现的次数相同；
$s_2, s_3, s_4, s_5, s_7, s_{11}$ 中字符 'b' 出现的次数需要和 $t_2, t_3, t_4, t_5, t_7, t_{11}$ 中字符 'b' 出现的次数相同；
……
$s_2, s_3, s_4, s_5, s_7, s_{11}$ 中字符 'z' 出现的次数需要和 $t_2, t_3, t_4, t_5, t_7, t_{11}$ 中字符 'z' 出现的次数相同。

只有满足上述所有条件，字符串 $s$ 才能变得和字符串 $t$ 相等。

代码实现时，我用 $cnt1_{i,j}$ 表示字符串以 $i$ 为根节点的节点集合对应字符串 $s$ 中字符 $j$ 出现的次数，用 $cnt2_{i,j}$ 表示字符串以 $i$ 为根节点的节点集合对应字符串 $t$ 中字符 $j$ 出现的次数。

则必须要满足：

对于任意 $1 \le i \le n, 0 \le j \le 25$ 都有 $cnt1_{i,j} = cnt2_{i,j}$ 才输出 YES；否则，输出 NO。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

int T, n, k, f[maxn], cnt1[maxn][26], cnt2[maxn][26];
char s[maxn], t[maxn];

void init() {
	for (int i = 1; i <= n; i++) {
		f[i] = i;
		for (int j = 0; j < 26; j++)
			cnt1[i][j] = cnt2[i][j] = 0;
	}
}

int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}

void funion(int x, int y) {
	int a = find(x), b = find(y);
	f[a] = f[b] = f[x] = f[y] = min(a, b);
}

bool check() {
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < 26; j++)
			if (cnt1[i][j] != cnt2[i][j])
				return false;
	return true;
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%s%s", &n, &k, s+1, t+1);
		init();
		for (int i = 1; i + k <= n; i++) {
			funion(i, i+k);
			if (i+k+1 <= n)
				funion(i, i+k+1);
		}
		for (int i = 1; i <= n; i++) {
			cnt1[find(i)][s[i]-'a']++;
			cnt2[find(i)][t[i]-'a']++;
		}
		puts(check() ? "YES" : "NO");
	}
	return 0;
}