Equalizing Two Strings

Created by LXC on Wed Apr 10 14:00:20 2024

https://codeforces.com/problemset/problem/1256/F

ranting: 2000

tag: constructive algorithms, sortings, strings

problem

给你两长度都为 $n$ 的小写字符串 $S, T$。

每次操作中你可以任选一个 $L (1\le L\le n)$，同时翻转 $S$ 中的任意一个长度为 $L$ 的子串和 $T$ 中任意一个长度为 $L$ 的子串。

请回答你是否能在若干次操作后使两字符串一样？

输入格式

第一行一个正整数 $q(1\le q\le 10^4)$ 表示询问次数

接下来 $q$ 组数据，每组数据三行，第一行一个正整数 $n(1\le n\le 2\times 10^5)$，第二行一个字符串 $S$，第三行一个字符串 $T$。

保证 $\sum n\le 2\times 10^5$

输出格式

$q$ 行，每行一个字符串 YES 或 NO。

solution

首先两个串中各个字符出现的次数都相同，否则一定不能相等。

我们知道基于相邻交换可以排序，基于相邻交换可以生成任意排列。

如果存在一个字符出现多次，我们可以将他们移动到相邻位置，然后对于一个字符可以任意使用长度为2的区间操作，另一个数组始终操作长度为2的由相同的两个字符的区间。势必能相等。

如果不存在相同字符。那么只要两个数组逆序对之和是偶数也能相等。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

random_device seed;
ranlux48 engine(seed());
int random(int l, int r) {
    uniform_int_distribution<> distrib(l, r);
    return distrib(engine);
}
template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    vector<int> cs(26), ct(26);
    for (char i:s) cs[i-'a']++;
    for (char i:t) ct[i-'a']++;
    if (cs != ct) {
        cout << "NO\n";
        return ;
    }
    if (count_if(cs.begin(), cs.end(), [](auto x)->bool {return x > 1;}) > 0) {
        cout << "YES\n";
        return ;
    }
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int x, int y) {
        return tie(t[x], s[x]) < tie(t[y], s[y]);
    });
    string ss, st;
    for (int i:idx) {
        ss.push_back(s[i]);
        st.push_back(t[i]);
    }
    // cout << s << " " << t << endl;
    // cout << ss << " " << st << endl;
    vector<int> cnt(256);
    int rs = 0;
    for (char i:ss) {
        for (char j=i+1; j<='z'; j++) {
            rs += cnt[j];
        }
        cnt[i]++;
    }
    cout << (rs%2?"NO\n":"YES\n");
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}