526互联

Codeforces Round 855 (Div. 3)--E

发布时间 2023-04-30 13:47:37作者: zhujio

题意：

　　给定一个k，可以任意次交换满足 | i - j | = k 或 | i - j |=k+1 的两个位置的元素

　　很容易发现有区间内的字符是可以任意交换的，但是一个个字符考虑太混乱了（就是这样子把脑袋搞晕了），从左考虑那么（1，n - k）这个区间可以任意交换，从右考虑（k + 1， n）这个区间可以任意交换

　　那么假如两个区间有交集，则整个字符串都可以任意交换两个元素的位置，否则就考虑中间空出来的那段是不是相同即可

链接：Problem - E2 - Codeforces

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"

//不能随意变换的区间是（1，n-k）（k+1,n）

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        int n, k;
        string s1, s2;
        cin >> n >> k;
        cin >> s1 >> s2;
        s1 = " " + s1; s2 = " " + s2;
        int n1 = k + 1, n2 = n - k;
        string t1 = s1, t2 = s2;
        sort(t1.begin(), t1.end());
        sort(t2.begin(), t2.end());
        if (t1 != t2) {
            cout << "NO" << endl;
            continue;
        }
        if (n1 > n || n2 < 1) {
            if (s1 == s2)cout << "YES" << endl;
            else cout << "NO" << endl;
            continue;
        }
        if (n - k >= 1 + k) {
            cout << "YES" << endl;
        }
        else {
            string part3_s1 = s1.substr(n2 + 1, n1 - n2 - 1);
            string part3_s2 = s2.substr(n2 + 1, n1 - n2 - 1);
            if (part3_s2 == part3_s1)cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
    return 0;
}