【Codeforces 1256F】Equalizing Two Strings | Mrsrz's blog

分类讨论

题目大意：

给定两个字符串，每次可以任选一个长度 $L$，并翻转两个字符串中一个长度为 $L$ 的子串。问是否能通过有限次操作，使得两个字符串相等。

题解：

首先先判断每个字符的出现次数相等，不相等显然不可能。

然后，翻转长度为 $L$ 的串，可以通过有限次交换相邻两个字符来做到相同的效果。

于是就相当于每次交换相邻两个字符。

我们可以考虑对字符串进行排序。

如果一个字符串中有两个字符相等，那么两个字符串中，一个已经排好序，可以通过不断交换两个相同的字符来“浪费”步数，同时把另外一个排好序即可。这样一定可以使两个串相等。

否则，交换相邻两个字符，必然使得逆序对个数的奇偶性发生改变。那么判一下两个字符串的逆序对奇偶性是否相等即可。

Code：

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int N=2e5+6;
char s[N],t[N];
int buc1[128],buc2[128];
int T;
int chk(){
    string a(s),b(t);
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    if(a!=b)return 0;
    for(int i=0;i+1<a.length();++i)
        if(a[i]==a[i+1])return 2;
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        int n;
        cin>>n>>s>>t;
        int x=chk();
        if(x==0){
            cout<<"NO\n";
            continue;
        }
        memset(buc1,0,sizeof buc1);
        memset(buc2,0,sizeof buc2);
        int f1=0,f2=0;
        for(int i=0;i<n;++i){
            for(int j=s[i]+1;j<='z';++j)f1+=buc1[j];
            for(int j=t[i]+1;j<='z';++j)f2+=buc2[j];
            ++buc1[s[i]],++buc2[t[i]];
        }
        x+=(f1&1)==(f2&1);
        if(x>1)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}