题解：CF2171C1 Renako Amaori and XOR Game (easy version)

LaplaceOrange · 2025-12-15 23:11:55 · 题解

CF2171C1 Renako Amaori and XOR Game (easy version) 题解

题意描述

给定两个长度为 n 的 0/1 序列 a 与 b。两人轮流操作第 i 对 (a_i, b_i)（i 从 1 开始）：

若 i 为奇数，先手（子洋 Ajisai） 可选择是否交换 a_i 与 b_i；
若 i 为偶数，后手（舞 Mai） 可选择是否交换。

操作结束后计算：

A = \bigoplus_{i=1}^{n} a_i, \quad B = \bigoplus_{i=1}^{n} b_i.

胜负判定：

若 A > B，则子洋胜；
若 A < B，则舞胜；
若 A = B，则平局。

思路分析

定义不变量：
d = A \oplus B = \bigoplus_{i=1}^{n} (a_i \oplus b_i).
交换 a_i 与 b_i 相当于同时对 A 和 B 异或 a_i \oplus b_i，因此 d 全程不变。
情况一：d = 0
此时 A = B 恒成立，结果必为 Tie。
情况二：d = 1
此时 B = A \oplus 1，故：
- 因此胜负完全取决于最终 $A$ 的值。
交换一对满足 a_i \ne b_i 的位置会翻转 A（因仅 a_i 影响 A）；记：
- 由 $d = (x + y) \bmod 2 = 1$，知 $x$ 与 $y$ 奇偶性不同。
决策分析（舞后动）：
- 若 y = 0，则 x 为奇数，子洋可确保最终 A = 1 ⇒ 子洋胜；
- 若 y \ge 1，舞可在最后一轮根据当前 A 值决定是否翻转，强制 A = 0 ⇒ 舞胜。

时间复杂度：O(n)；空间复杂度：O(n)。

代码实现

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

int t, n, a[200010], b[200010];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> t;
    while (t--) {
        cin >> n;
        int d = 0, y = 0;  // d = A ⊕ B（不变量）；y = 舞可控的「不同位」数量（即偶数位且 a_i ≠ b_i 的个数）
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) {
            cin >> b[i];
            int c = a[i] ^ b[i];   // c = 1 当且仅当 a_i ≠ b_i
            d ^= c;                // 累积 d = ⊕(a_i ⊕ b_i)，全程不变
            if (i % 2 == 0 && c) ++y;  // 偶数位且不同 → 属于舞的决策范围
        }
        if (d == 0) {
            cout << "Tie\n";       // A = B 恒成立
        } else {
            // d = 1：舞若至少有一个可控位（y ≥ 1），可强制 A = 0 ⇒ 舞胜
            cout << (y ? "Mai\n" : "Ajisai\n");
        }
    }
    return 0;
}