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

C1. Renako Amaori and XOR Game (easy version)

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

问题描述

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

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

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

Ajisai和Mai被给定长度为 $n$ 的数组 $a$ 和 $b$ ($0 \leq a_i,b_i \leq 1$)。她们将玩一个持续 $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 1$)。

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

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

输出格式

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

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

样例输入

6
4
1 0 0 1
1 0 1 1
6
0 1 1 1 1 0
0 0 1 0 1 1
4
0 0 1 0
1 0 1 1
5
1 0 1 1 1
0 1 1 1 0
6
1 1 1 1 1 1
1 1 1 1 1 1
5
0 1 0 0 1
1 0 0 1 1

样例输出

Ajisai
Mai
Tie
Ajisai
Tie
Mai

样例说明

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

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

在第2回合，Mai选择不操作。

在第3回合，Ajisai选择交换 $a_3$ 和 $b_3$。现在数组变为 $a=[1,0,1,1]$ 和 $b=[1,0,0,1]$。

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

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

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

第一次的想法

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

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1e6+7;
const int mod=1e9+7;



void solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    vector<int> b(n);
    int x=0,y=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        x^=a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
        y^=b[i];
    }
    int cnto=0,cnte=0;

    for(int i=0;i<n;i++){
        if(i&1){
            if(a[i]^b[i]) cnte++;
        }else{
            if(a[i]^b[i]) cnto++;
        }
    }
    if(cnte==cnto){
        if(n&1&&x>y) printf("Ajisai\n");
        else if(n%2==0&&y>x) printf("Mai\n");
        else printf("Tie\n");
    }
    else if(cnte>cnto) printf("Mai\n");
    else printf("Ajisai\n");

    return ;
}


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

你的思路主要存在两个问题：判断平局的条件 和 判断胜负的逻辑。

这道题本质上是一个博弈论问题，但因为涉及到异或和（XOR sum），它有一个非常关键的性质：奇偶性不变性和最后操作者优势。

1. 为什么你的“计数法”是错的？

你的代码逻辑是：统计 Ajisai 能操作的差异位数量 (cnto) 和 Mai 能操作的差异位数量 (cnte)，然后觉得谁能操作的次数多谁就赢。

反例：

假设 $n=4$，只有下标 0（Ajisai）和 2（Ajisai）的位置 $a_i \neq b_i$，其他位置都相等。

• 此时 cnto = 2, cnte = 0。

• 总共有偶数个不同位，意味着 $S_a \oplus S_b = 0$（即 $S_a$ 和 $S_b$ 奇偶性相同）。

• 无论怎么交换，$a_i$ 和 $b_i$ 同时翻转，它们的异或和永远保持相等。

• 结果应该是 Tie，但你的代码会因为 cnto > cnte 输出 Ajisai。

核心错误点：

这道题的胜负不是由“谁能操作的次数多”决定的，而是由“最后一个能改变局面的操作者”决定的。

---

2. 正确的解题逻辑

第一步：判断是否平局 (Tie)

我们记 $S_a$ 为数组 A 的异或和，$S_b$ 为数组 B 的异或和。

• 如果在游戏开始前 $S_a = S_b$（即 $S_a \oplus S_b = 0$），那么无论双方怎么操作，结果永远是平局。

  • 原因： 每次交换操作会同时改变 $a_i$ 和 $b_i$。如果 $a_i$ 变了，$S_a$ 的奇偶性翻转；同时 $b_i$ 变了，$S_b$ 的奇偶性也翻转。所以 $S_a$ 和 $S_b$ 的相对关系（是否相等）永远不会变。

• 结论： 只要初始 $S_a = S_b$，直接输出 Tie。

第二步：判断胜负 (Ajisai vs Mai)

如果初始 $S_a \neq S_b$（即一个为 0 一个为 1），平局就不可能了，必然有一方获胜。

• 只有 $a_i \neq b_i$ 的位置（差异位）才是有意义的。如果 $a_i = b_i$，交换后 $S_a$ 和 $S_b$ 都不变，相当于没操作。

• 谁掌握了最后一个差异位，谁就必胜。

  • 想象一下，游戏进行到最后一个差异位的时候，轮到某位玩家操作。她可以看到当前的局面是“自己赢”还是“对方赢”。

  • 如果当前局面自己赢，她就选择“跳过”（Pass）。

  • 如果当前局面对方赢，她就选择“交换”（Swap），这样双方的得分都会翻转（0变1，1变0），局势瞬间逆转，变成自己赢。

  • 因为她是最后一个能改变局势的人，之后没有人能反转她的决定。

• 结论： 找到下标最大的那个 $i$，使得 $a_i \neq b_i$。

  • 如果 $i$ 是偶数（0, 2, 4...），说明最后一手在 Ajisai 手里 $\to$ Ajisai 胜。

  • 如果 $i$ 是奇数（1, 3, 5...），说明最后一手在 Mai 手里 $\to$ Mai 胜。

---

3. 修正后的代码

C++

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

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

    int x = 0, y = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        x ^= a[i]; // 计算 A 的初始异或和
    }
    for(int i = 0; i < n; i++){
        cin >> b[i];
        y ^= b[i]; // 计算 B 的初始异或和
    }

    // 1. 如果初始异或和相等，无论怎么操作，最终肯定还是相等
    if(x == y) {
        cout << "Tie" << endl;
        return;
    }

    // 2. 如果不相等，找到最后一个差异位的下标
    int last_diff_index = -1;
    for(int i = n - 1; i >= 0; i--){
        if(a[i] != b[i]){
            last_diff_index = i;
            break;
        }
    }

    // 3. 判断这个下标是谁的回合
    // 题目中 Ajisai 是第 1, 3, 5... 回合（下标 0, 2, 4...）
    // Mai 是第 2, 4, 6... 回合（下标 1, 3, 5...）
    if(last_diff_index % 2 == 0) {
        cout << "Ajisai" << endl;
    } else {
        cout << "Mai" << endl;
    }
}

int main(){
    // 加速 IO，虽然本题数据量不算特别大，但习惯养成很重要
    ios::sync_with_stdio(false);
    cin.tie(0);

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

总结

你的代码主要输在逻辑过于复杂且方向偏了。博弈题（特别是涉及位运算的）通常有两个特征：

1. 不变量：$S_a \oplus S_b$ 在整个游戏中是不变的。

2. 倒推法：决定胜负的往往是最后一个能有效操作的人。

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

后手优势是无可撼动的

🚫 我的误区 (Fail Log)

• 思路错误: 错误统计1的次数，基本第一版思路是完全跑偏，平局思路也并不是正确的
• 实现错误:
• 数据范围:

✅ 正解思路

🧠 举一反三 (Pattern)

• 下次看到 "先后操作" -> 想到 后手的决定性优势

---

💻 代码

```cpp // Problem: CF 2171 C1 // Contest: Codeforces - Codeforces Round 1065 (Div. 3) // URL: https://codeforces.com/contest/2171/problem/C1 // 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;

void solve(){ int n; cin>>n; vector a(n); vector b(n); int x=0,y=0; for(int i=0;i>a[i]; x^=a[i]; } for(int i=0;i>b[i]; y^=b[i]; }

int pos;
for(int i=n-1;i>=0;i--){
    if(a[i]^b[i]){
        pos=i+1;
        break;
    }
}

if(x==y) 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; } ````