Unforgivable Curse()-其他

Unforgivable Curse()

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
const int N=2e5+10;
typedef long long ll;
 
int n,k;
string s1,s2;
int p[N];
 
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
void solve()
{
    scanf("%d%d",&n,&k);
    cin>>s1>>s2;
    
    bool fg=true;
    for(int i=0;i<n;i++) p[i]=i;
    for(int i=0;i<n;i++)
    {
        if(i+k<n)
        {
            int pa=find(i),pb=find(i+k);
            if(pa!=pb) p[pb]=pa;
        }
        if(i+k+1<n)
        {
            int pa=find(i),pb=find(i+k+1);
            if(pa!=pb) p[pb]=pa;
        }
    }
    vector<vector<int>> v(n,vector<int>());
    for(int i=0;i<n;i++)
    {
        int pa=find(i);
        v[pa].push_back(i);
    }
    for(int i=0;i<n;i++)
    {
        if(v[i].size()==0) continue;
        string a="",b="";
        for(auto x:v[i])
        {
            a+=s1[x];
            b+=s2[x];
        }
        
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        
        if(a!=b)
        {
            fg=false;
            break;
        }
    }
    
    if(fg) puts("YES");
    else puts("NO");
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
const int N=2e5+10;
typedef long long ll;
 
int n,k;
string s1,s2;
int p[N];
 
int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}
void solve()
{
    scanf("%d%d",&n,&k);
    cin>>s1>>s2;
    
    bool fg=true;
    for(int i=0;i<n;i++) p[i]=i;
    for(int i=0;i<n;i++)
    {
        if(i+k<n)
        {
            int pa=find(i),pb=find(i+k);
            if(pa!=pb) p[pb]=pa;
        }
        if(i+k+1<n)
        {
            int pa=find(i),pb=find(i+k+1);
            if(pa!=pb) p[pb]=pa;
        }
    }
    vector<vector<int>> v(n,vector<int>());
    for(int i=0;i<n;i++)
    {
        int pa=find(i);
        v[pa].push_back(i);
    }
    for(int i=0;i<n;i++)
    {
        if(v[i].size()==0) continue;
        string a="",b="";
        for(auto x:v[i])
        {
            a+=s1[x];
            b+=s2[x];
        }
        
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        
        if(a!=b)
        {
            fg=false;
            break;
        }
    }
    
    if(fg) puts("YES");
    else puts("NO");
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}