题目链接: 核心考点: [[博弈论]]

C2. Renako Amaori and XOR Game (hard version)

时间限制：每测试点2秒
内存限制：每测试点256 MB

问题描述

是啊。我不能再这样下去了。不。该死的。路。
— Renako Amaori

这是问题的困难版本。简单版本和困难版本之间的唯一区别是，在困难版本中，$a_i,b_i \leq 10^6$。

Renako陷入了进退两难的境地……当然，我是指Ajisai和Mai！她们两个都想和她出去玩，而她就是无法决定！所以Ajisai和Mai决定玩XOR游戏。

Ajisai和Mai被给定长度为 $n$ 的数组 $a$ 和 $b$ ($0 \leq a_i,b_i \leq 10^6$)。她们将玩一个持续 $n$ 回合的游戏，其中Ajisai在奇数回合行动，Mai在偶数回合行动。在第 $i$ 回合，行动的玩家可以选择交换 $a_i$ 和 $b_i$，或者不操作。

请注意，如果发生交换，被交换的索引必须与回合号匹配。例如，在第一个回合，Ajisai可以选择交换 $a_1$ 和 $b_1$，或者不操作。在第二个回合，Mai可以选择交换 $a_2$ 和 $b_2$，或者不操作。这样持续 $n$ 回合。因此，只有Ajisai可以交换奇数索引，只有Mai可以交换偶数索引。

游戏结束时，Ajisai的得分为 $a_1 \oplus a_2 \oplus \cdots \oplus a_n$，Mai的得分为 $b_1 \oplus b_2 \oplus \cdots \oplus b_n^*$。得分较高的玩家获胜。如果玩家得分相同，游戏以平局结束。

确定在最优策略下游戏的结果。更正式地说，如果存在一个策略使得某个玩家无论对手如何选择都能获胜，则认为该玩家在最优策略下获胜。如果两个玩家都没有这样的策略，则认为游戏在最优策略下是平局。

$^*\oplus$ 表示按位异或操作。

输入格式

第一行包含一个整数 $t$ ($1 \leq t \leq 10^4$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 2 \cdot 10^5$)。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^6$)。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ ($0 \leq b_i \leq 10^6$)。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果Ajisai在最优策略下获胜，输出一行"Ajisai"；如果Mai在最优策略下获胜，输出一行"Mai"；如果游戏在最优策略下以平局结束，输出一行"Tie"。

答案可以以任何大小写形式输出。例如，字符串"mAi"、"mai"、"MAI"和"maI"都会被识别为"Mai"。

样例输入

6
4
1 4 6 1
3 2 3 7
6
20 11 1 7 7 0
14 8 3 6 17 6
4
2 6 3 6
3 4 7 1
5
1 4 5 5 3
6 7 1 2 13
6
9 5 9 17 17 6
1 13 6 13 1 15
5
2 3 8 1 5
3 1 6 14 7

样例输出

Mai
Ajisai
Tie
Ajisai
Mai
Tie

样例说明

在第一个样例中，游戏可能的一种进行方式如下：

在第1回合，Ajisai选择交换 $a_1$ 和 $b_1$。现在数组变为 $a=[3,4,6,1]$ 和 $b=[1,2,3,7]$。

在第2回合，Mai选择交换 $a_2$ 和 $b_2$。现在数组变为 $a=[3,2,6,1]$ 和 $b=[1,4,3,7]$。

在第3回合，Ajisai选择不操作。

在第4回合，Mai选择交换 $a_4$ 和 $b_4$。现在数组变为 $a=[3,2,6,7]$ 和 $b=[1,4,3,1]$。

现在，Ajisai的最终得分是 $3 \oplus 2 \oplus 6 \oplus 7 = 0$，Mai的最终得分是 $1 \oplus 4 \oplus 3 \oplus 1 = 7$。因此，Mai赢得了游戏。

上述描述并不保证代表最优策略。

关于更多样例，请参阅简单版本的样例。

我思路的错误

这是一个非常典型的博弈论思维陷阱。你的代码逻辑试图计算每一步交换带来的数值变化，但这在“比大小”的异或游戏中是行不通的。

结论：你的思路方向错了，无法通过此题。 必须从位运算的性质和博弈论的角度重新思考。

我来帮你梳理正确的逻辑（这也是 Hard Version 和 Easy Version 通用的正解）：

1. 核心性质：异或差不变 (Invariant)

这道题最关键的性质是：无论怎么操作，两个数组的总异或和的异或值是永远不变的。

设 $S_A$ 是 Ajisai 的异或和，$S_B$ 是 Mai 的异或和。

总异或差 $D = S_A \oplus S_B = (\bigoplus a_i) \oplus (\bigoplus b_i)$。

• 如果你交换 $a_i$ 和 $b_i$，那么 $S_A$ 变成了 $S_A \oplus a_i \oplus b_i$，$S_B$ 变成了 $S_B \oplus b_i \oplus a_i$。

• 新的差值 $D' = (S_A \oplus a_i \oplus b_i) \oplus (S_B \oplus b_i \oplus a_i)$。

• 因为 $x \oplus x = 0$，所以 $D' = S_A \oplus S_B = D$。

这意味着：无论怎么交换，最终 $S_A$ 和 $S_B$ 的异或差，永远等于初始状态的异或差。

2. 胜负判断逻辑

根据上面的性质，我们可以分情况讨论：

情况 A：初始 $S_A \oplus S_B = 0$

这意味着 $S_A = S_B$。因为差值永远不变，无论怎么操作，最后两人的分数一定相等。

结果：Tie

情况 B：初始 $S_A \oplus S_B \neq 0$

既然不相等，肯定有输赢。谁赢呢？

比大小的时候，最高位（Most Significant Bit, MSB）决定一切。

1. 算出 $D = S_A \oplus S_B$。

2. 找到 $D$ 的最高为 1 的二进制位，假设是第 $k$ 位。

   • 这意味着最终 $S_A$ 和 $S_B$ 在第 $k$ 位上一定是一个 0 一个 1。

   • 谁拿到了第 $k$ 位的 1，谁就必胜（因为更高的位两人都一样，第 $k$ 位是 1 的那个数肯定比 0 的大）。

3. 谁能决定第 $k$ 位？

   • 我们需要找到那些能够改变第 $k$ 位状态的操作。

   • 也就是找到所有的下标 $i$，满足 $a_i$ 和 $b_i$ 在第 $k$ 位上不同（即 (a[i] ^ b[i]) 的第 $k$ 位是 1）。

   • 在这些下标中，下标最大（最晚操作）的那个人拥有最终决定权。

   • 为什么？因为前面的玩家无论怎么翻转第 $k$ 位，最后操作的那个人都可以选择“翻转”或者“不翻转”，从而强制让最终结果对自己有利（让自己在第 $k$ 位是 1）。

3. 正确算法流程

1. 计算所有 $a_i$ 和 $b_i$ 的总异或和 diff。

2. 如果 diff == 0，输出 Tie。

3. 如果 diff != 0：

   • 找到 diff 的最高有效位（High Bit），记为 hb。

   • 从后往前遍历（$i$ 从 $n$ 到 $1$）：

     • 检查 $a_i \oplus b_i$ 的第 hb 位是否为 1。

     • 找到的第一个满足条件的 $i$ 就是决定胜负的关键回合。

   • 如果这个 $i$ 是奇数（Ajisai 的回合），输出 Ajisai。

   • 如果这个 $i$ 是偶数（Mai 的回合），输出 Mai。

---

4. 正确代码 (AC Code)

C++

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

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> b(n + 1);

    // 1. 计算总异或差
    int diff = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        diff ^= a[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> b[i];
        diff ^= b[i];
    }

    // 2. 如果差为0，平局
    if(diff == 0) {
        cout << "Tie" << endl;
        return;
    }

    // 3. 找最高位 (Most Significant Bit)
    // __lg(x) 是 GCC 内置函数，返回最高位是第几位(0-indexed)
    // 例如 __lg(100) -> __lg(1100100) -> 6
    int high_bit = __lg(diff); 

    // 4. 找最后一个能影响最高位的下标
    int last_idx = -1;
    for(int i = n; i >= 1; i--) {
        // 检查 a[i] 和 b[i] 在 high_bit 这一位是否不同
        // ((a[i] ^ b[i]) >> high_bit) & 1 判断该位是否为1
        if((a[i] ^ b[i]) >> high_bit & 1) {
            last_idx = i;
            break; // 找到了最后的操作者，直接退出
        }
    }

    // 5. 判断是谁的回合
    // 题目中：Ajisai 是奇数回合(1,3,5...)，Mai 是偶数回合(2,4,6...)
    if(last_idx & 1) {
        cout << "Ajisai" << endl;
    } else {
        cout << "Mai" << endl;
    }
}

int main(){
    // 优化 I/O
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

总结你的误区

• 误区：试图算出具体的差值数组然后统计数量。

• 正解：这是一个位运算博弈。数值的大小由最高位决定，而最高位的状态由最后一个能操作该位的人决定。这是博弈论中“倒推法”的应用。

💡 核心直觉 (一句话总结)

后手优势还在，但是问题数据范围变了，我们也要贪心找影响最大的，也就是谁能影响最高的位置而且后手谁就能赢

🚫 我的误区 (Fail Log)

• 思路错误:
• 实现错误:
• 数据范围:

✅ 正解思路

🧠 举一反三 (Pattern)

• 下次看到 "先后操作" -> 想到 后手优势，发现不变量，除了平局就是非平局

---

💻 代码

```cpp // Problem: CF 2171 C2 // Contest: Codeforces - Codeforces Round 1065 (Div. 3) // URL: https://codeforces.com/contest/2171/problem/C2 // Memory Limit: 256 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)

include

using namespace std; typedef long long LL; typedef pair PII; const int N=1e6+7; const int mod=1e9+7;

int f(int x){ int ans=0; while(x){ x/=2; ans++; } return ans; }

void solve(){ int n; cin>>n; vector a(n+1); vector b(n+1); int ans=0; for(int i=1;i<=n;i++){ cin>>a[i]; ans^=a[i]; } for(int i=1;i<=n;i++){ cin>>b[i]; ans^=b[i]; }

int dig=f(ans)-1;
int pos;
for(int i=n;i>=1;i--){
    if((a[i]^b[i])>>dig&1){
        pos=i;
        break;
    }
}



if(ans==0) printf("Tie\n");
else{
    if(pos&1) printf("Ajisai\n");
    else printf("Mai\n");
}


return ;

}

int main(){ int t; cin>>t; while(t--){ solve(); } return 0; } ````