题解：CF2171C2 Renako Amaori and XOR Game (hard version)

· · 题解

思路：

先解析操作，每次操作后把两个数互换，其对应的异或和也会重新计算。设第 i 次操作时统计数组 a 的异或和为 ans，交换的两个数为 a_i 和 b_i，那么进行交换操作后相当于是：ans \oplus a_i \oplus b_i。

贪心获取最大异或和。首先考虑输赢规则，是根据谁的异或和大决定输赢，那么可以有两种竞争方案：

  1. 通过增大自己的和达到比对手的和大的目的
  2. 通过减少对手的和达到比对手的和大的目的

那么把自己带入玩家，每次轮到我操作时：

  1. 若这次操作能使我的和增大我就换，显然过于片面，因此交换后可能我的和增大了对手的和也会增大且增大的值比我多，因此需要考虑这一点，设自己的数组为 a，和为 ans_1，对手的数组为 b，和为 ans_2。那么当 ans_1 \oplus a_i \oplus b_i - ans_1 > ans_2 \oplus b_i \oplus a_i - ans_2 时才会进行交换。
  2. 若这次操作能使对手的和减少，同样需要考虑对自己的和的影响情况：若交换后对手减少的和比我减少的多，就交换。设自己的数组为 a，和为 ans_1，对手的数组为 b，和为 ans_2。那么当 ans_1 - ans_1 \oplus a_i \oplus b_i < ans_2 - ans_2 \oplus b_i \oplus a_i 时才进行交换，判断两种情况容易报错，考虑简化公式。我们在小学数学中学过，不等式两边同乘 -1 不等号要变号，那么可以得到：ans_1 \oplus a_i \oplus b_i - ans_1 > ans_2 \oplus b_i \oplus a_i - ans_2。可以发现和上面推导出的公式相同。因此每次只需要判断是否满足 ans_1 \oplus a_i \oplus b_i - ans_1 > ans_2 \oplus b_i \oplus a_i - ans_2，再决定是否进行交换。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define q1 a[i] ^ b[i]//宏定义一下 方便使用
#define q2 b[i] ^ a[i]
const int N = 2e5 + 10;
int a[N],b[N];
void solve(){
    int n;
    int ans1 = 0;
    int ans2 = 0;
    cin >> n;
    for(int i = 1;i <= n;i ++){cin >> a[i];ans1 ^= a[i];}
    for(int i = 1;i <= n;i ++){cin >> b[i];ans2 ^= b[i];}
    for(int i = 1;i <= n;i ++){
        if(a[i] == b[i])continue;//若两个数相同 那么交不交换没区别
        if(i % 2){//判断轮到谁操作了
            int p1 = ans1,p2 = ans2;
            if((ans1 ^ q1) - p1 > (ans2 ^ q2) - p2){
                ans1 ^= q1;
                ans2 ^= q2;
            }
        }else{
            int p1 = ans1,p2 = ans2;
            if((ans2 ^ q2) - p2 > (ans1 ^ q1) - p1){
                ans1 ^= q1;
                ans2 ^= q2;
            }
        }
    }
    if(ans1 == ans2)puts("Tie");
    if(ans1 > ans2)puts("Ajisai");
    if(ans1 < ans2)puts("Mai");
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}