题解：CF2254F Whiplash

· · 题解

关键结论：进行有限次题目所说的操作，等价于先对 a 进行至多一次操作，再将 a 任意顺序打乱。理由如下：

我们可以通过以下三次操作实现对 a_1 和任意 a_i 的交换：

  1. 选择 1 处的 a_1 操作，得到 a_1, a_2 \oplus a_1, \dots, a_{i} \oplus a_1, \dots, a_n \oplus a_1

  2. 选择 i 处的 a_i \oplus a_1 操作，得到 a_i, a_2 \oplus a_i, \dots, a_i \oplus a_1, \dots a_n \oplus a_i。

  3. 选择 1 处的 a_i 操作，得到 a_i, a_2, \dots, a_1, \dots, a_n。

至此我们交换了 a_1, a_i。进一步的，我们显然可以任意打乱 a 的顺序。得证。

所以问题转化为判断能否通过至多一次操作，使得 a, b 的可重集相同。若已经相同则无需操作；否则：

记 A = \bigoplus_{i = 1}^n a_i, B = \bigoplus_{i = 1}^n b_i。操作一次后 a 变为 a_1 \oplus a_i, a_2 \oplus a_i, \dots, a_i, \dots, a_n \oplus a_i，由于 n 是偶数，这些新的 a_i 的异或和就是 A \oplus a_i。若 b 与操作后的 a 可重集相同，必然有 A \oplus a_i = B，即 a_i = A \oplus B。

所以在 a 中寻找 A \oplus B，若找不到则无解，否则操作一次后判断是否相同即可。

:::info[code]

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int ttt, n, a[N], b[N];

int main(){

    ios :: sync_with_stdio(false);
    cin >> ttt;
    while(ttt--){
        cin >> n;
        int s1 = 0, s2 = 0;
        for(int i = 1; i <= n; i++) cin >> a[i], s1 ^= a[i];
        for(int i = 1; i <= n; i++) cin >> b[i], s2 ^= b[i];
        sort(a + 1, a + n + 1);
        sort(b + 1, b + n + 1);
        bool flag = 1;
        for(int i = 1; i <= n; i++){
            if(a[i] != b[i]){
                flag = 0;
                break;
            }
        }
        if(flag){
            cout << "YES\n";
            continue;
        }
        int tmp = -1;
        for(int i = 1; i <= n; i++)
            if((s2 ^ b[i]) == s1) tmp = i;
        if(tmp == -1){
            cout << "NO\n";
            continue;
        }
        for(int i = 1; i <= n; i++)
            if(i != tmp) b[i] ^= b[tmp];
        sort(b + 1, b + n + 1);
        flag = 1;
        for(int i = 1; i <= n; i++){
            if(a[i] != b[i]){
                flag = 0;
                break;
            }
        }
        if(flag) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

:::