【sorting】CF855div3 2. Unforgivable Curse (hard version)

素颜马尾好姑娘i 2024-03-22 11:41 178阅读 0赞

[Problem - E2 - Codeforces][]

题意：

给你两个长度为n的只有英文的字符串a,b，然后给你一个k，你可以使si和s(i+k)或者si和s(i+k+1)交换，问你能否通过任意次交换，使得a，b字符串相等。

![7e7e78c98b454d1b8a0f18e7b5ecd8db.png][]

思路：

这种定长交换有个套路，就是%K的位置都是在同一个连通块里的，因此直接并查集就行

Code：

#include <bits/stdc++.h>
    
    using namespace std;
    #define int long long
    #define pii pair<int,int>
    #define endl "\n"
    
    clock_t startTime;
    
    double getCurrentTime()
    {
        return (double) (clock() - startTime) / CLOCKS_PER_SEC;
    }
    
    void solve()
    {
        int n,k;cin>>n>>k;
        string s,t;cin>>s>>t;
        s="?"+s,t="?"+t;
        vector<int>f(n+5);
        for(int i=1;i<=n;i++)   f[i]=i;
        vector<vector<int>>a1(n+5),a2(n+5);
        function<int(int)>findd=[&](int x)
        {
            if(f[x]==x) return x;
            return f[x]=findd(f[x]);
        };
        for(int i=1;i<=n;i++)
        {
            if(i+k>n) break;
            f[findd(i)]=findd(i+k);
            if(i+k+1<=n)f[findd(i)]=findd(i+k+1);
        }
        for(int i=1;i<=n;i++)
        {
            a1[findd(i)].push_back(s[i]);
            a2[findd(i)].push_back(t[i]);
        }
        for(int i=1;i<=n;i++)
        {
            std::sort(a1[i].begin(), a1[i].end());
            std::sort(a2[i].begin(), a2[i].end());
            if(a1[i]!=a2[i])
            {
                cout<<"NO"<<endl;
                return;
            }
        }
        cout<<"YES"<<endl;
    }
    
    signed main()
    {
        startTime=::clock();
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        int t = 1;
        cin >> t;
        while (t--)
            solve();
    }

[Problem - E2 - Codeforces]: https://codeforces.com/contest/1800/problem/E2
[7e7e78c98b454d1b8a0f18e7b5ecd8db.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/3ed3e323cda845b5bd872281dfa0f02c.png