题目链接：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;
}