Equalizing Two Strings

F. Equalizing Two Strings

有几种情况可以直接判定结果：

① 字母对应个数不一样，可直接判NO

② 当不满足①时，如果有一个字母有2个及以上的个数，也可直接判YES

③ 当不满足①②时我们可以知道，此时的字符串最多也只有26个字符，所以可以直接暴力，一个字符串只交换相邻位的字符必然可以变成另一个字符串，而如果交换次数为偶数，则为YES，否则为NO。

其实很多时候E、F题也并没有想象中的那么难，可以尝试尝试，至少赛时把题目看看也好。

代码：

// Created by CAD on 2019/11/7.

#include <bits/stdc++.h>

#define mst(name, value) memset(name,value,sizeof(name))

using namespace std;

const int maxn=2e5+5;

int cnt1[30],cnt2[30];

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int q;  cin>>q;

    while(q--)

    {

        int n;

        string s,t;

        cin>>n>>s>>t;

        mst(cnt1,0),mst(cnt2,0);

        for(auto i:s)

            cnt1[i-'a'+1]++;

        for(auto i:t)

            cnt2[i-'a'+1]++;

        int flag=0;

        for(int i=1;i<=26;++i)

            if(cnt1[i]!=cnt2[i]) flag=1;

        if(flag) {cout<<"NO"<<"\n";continue;}

        for(int i=1;i<=26;++i)

            if(cnt1[i]>1) flag=1;

        if(flag) {cout<<"YES\n";continue;}

        int cnt=0;

        for(int i=0;i<n;++i)

            if(s[i]!=t[i])

            {

                int x;

                for(int j=i+1;j<n;++j)

                    if(s[j]==t[i])

                    {

                        x=j;

                        break;

                    }

                for(int j=x;j>i;--j)

                    swap(s[j],s[j-1]),cnt++;

            }

        if(cnt%2==0) cout<<"YES\n";

        else cout<<"NO\n";

    }

    return 0;

}

巴特西

Equalizing Two Strings

最新文章

热门文章