题目描述

难度分:$1500$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$k(1 \leq k \leq 2 \times 10^5)$和两个长为$n$的字符串$s$和$t$，只包含小写字母。

你可以执行如下操作任意次：

• 选择下标$i$和$j$，交换$s[i]$和$s[j]$，要求$|i-j|=k$或者$|i-j|=k+1$。

能否把$s$变成$t$？输出YES或NO。

输入样例

7
6 3
talant
atltna
7 1
abacaba
aaaabbc
12 6
abracadabraa
avadakedavra
5 3
accio
cicao
5 4
lumos
molus
4 3
uwjt
twju
4 3
kvpx
vxpk

输出样例

YES
YES
NO
YES
NO
YES
NO

算法

并查集+贪心

把索引绝对差为$k$或$k+1$的索引对用并查集合并到一个组里面，构建一个映射“组$id$$\rightarrow$字母$\rightarrow$该字母在$s$中的索引集合”$mp$。

然后遍历$i \in [1,n]$，只要发现$s[i] \neq t[i]$，就在$mp[rootId][t[i]]$（其中$rootId$是$i$的根节点）中二分查找是否存在满足$j \gt i$的$j$，存在就交换$s[i]$和$s[j]$。

最后检查一下$s$和$t$是否相等即可。

复杂度分析

时间复杂度

遍历$i \in [1,n]$检查$s[i]$和$t[i]$是否相等的时间复杂度为$O(n)$。如果$s[i] \neq t[i]$，需要进行交换操作，找到$j$的时间复杂度是$O(log_2n)$，瓶颈在于二分查找。因此，算法整体的时间复杂度为$O(nlog_2n)$。

空间复杂度

除了输入的$s$串和$t$串，空间消耗的瓶颈在于并查集的根节点数组$p$，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <set>

using namespace std;
int T, n, k;
const int N = 200010;
char s[N], t[N];
int p[N];

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        p[rx] = ry;
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        scanf("%s", s + 1);
        scanf("%s", t + 1);
        for(int i = 1; i <= n; i++) {
            p[i] = i;
        }
        for(int i = 1; i + k <= n; i++) {
            merge(i, i + k);
            if(i + k + 1 <= n) {
                merge(i, i + k + 1);
            }
        }
        unordered_map<int, unordered_map<char, set<int>>> mp;
        for(int i = 1; i <= n; i++) {
            int root = find(i);
            mp[root][s[i]].insert(i);
        }
        bool flag = true;
        for(int i = 1; i <= n; i++) {
            if(s[i] == t[i]) continue;
            int root = find(i);
            if(!mp[root].count(t[i])) {
                flag = false;
                break;
            }
            auto& st = mp[root][t[i]];
            auto it = st.upper_bound(i);
            if(it == st.end()) {
                flag = false;
                break;
            }
            int j = *it;
            mp[root][t[i]].erase(j);
            mp[root][s[i]].erase(i);
            mp[root][s[i]].insert(j);
            swap(s[i], s[j]);
        }
        if(flag) {
            for(int i = 1; i <= n; i++) {
                if(s[i] != t[i]) {
                    flag = false;
                    break;
                }
            }
        }
        if(flag) puts("YES");
        else puts("NO");
    }
    return 0;
}