A16552. Renako Amaori and XOR Game (easy version)
编程题
普及-
知识点
题目描述
没错。我再也受不了了。绝对不行。
—— 天织恋
这是该问题的简单版本。简单版本与困难版本的唯一区别是本题中 $a_i, b_i \leq 1$。
天织恋陷入了进退两难的境地……当然，这指的是紫阳和舞！她们都想和她一起玩，而她实在难以抉择！所以紫阳和舞决定玩异或游戏。
紫阳和舞分别得到长度为 $n$ 的数组 $a$ 和 $b$（$0 \leq a_i, b_i \leq {\color{red}{1}}$）。她们将进行一个持续 $n$ 回合的游戏，紫阳在奇数回合操作，舞在偶数回合操作。在第 $i$ 回合，当前轮到操作的玩家可以选择交换 $a_i$ 和 $b_i$，也可以选择跳过。
注意，如果选择交换，则交换的位置必须和当前回合数相同。例如，在第 $1$ 回合时，紫阳可以选择交换 $a_1$ 和 $b_1$，或者选择不操作。在第 $2$ 回合时，舞可以选择交换 $a_2$ 和 $b_2$，或者不操作。以此类推，共进行 $n$ 回合。因此，只有紫阳可以交换奇数下标位置，只有舞可以交换偶数下标位置。
游戏结束后，紫阳的得分为 $a_1 \oplus a_2 \oplus \dots \oplus a_n$，舞的得分为 $b_1 \oplus b_2 \oplus \dots \oplus b_n$。分数更高的玩家获胜。如果二人分数相同，则为平局。
请你判断在最优策略下，这场游戏的结果。如果某位玩家存在一种策略，无论对方如何操作，都必胜，则她在最优博弈下胜出。如果双方都无法必胜，则为平局。
$^\text{∗}$ 这里 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。
—— 天织恋
这是该问题的简单版本。简单版本与困难版本的唯一区别是本题中 $a_i, b_i \leq 1$。
天织恋陷入了进退两难的境地……当然，这指的是紫阳和舞！她们都想和她一起玩，而她实在难以抉择！所以紫阳和舞决定玩异或游戏。
紫阳和舞分别得到长度为 $n$ 的数组 $a$ 和 $b$（$0 \leq a_i, b_i \leq {\color{red}{1}}$）。她们将进行一个持续 $n$ 回合的游戏，紫阳在奇数回合操作，舞在偶数回合操作。在第 $i$ 回合，当前轮到操作的玩家可以选择交换 $a_i$ 和 $b_i$，也可以选择跳过。
注意，如果选择交换，则交换的位置必须和当前回合数相同。例如，在第 $1$ 回合时，紫阳可以选择交换 $a_1$ 和 $b_1$，或者选择不操作。在第 $2$ 回合时，舞可以选择交换 $a_2$ 和 $b_2$，或者不操作。以此类推，共进行 $n$ 回合。因此，只有紫阳可以交换奇数下标位置，只有舞可以交换偶数下标位置。
游戏结束后，紫阳的得分为 $a_1 \oplus a_2 \oplus \dots \oplus a_n$，舞的得分为 $b_1 \oplus b_2 \oplus \dots \oplus b_n$。分数更高的玩家获胜。如果二人分数相同，则为平局。
请你判断在最优策略下，这场游戏的结果。如果某位玩家存在一种策略，无论对方如何操作，都必胜，则她在最优博弈下胜出。如果双方都无法必胜，则为平局。
$^\text{∗}$ 这里 $\oplus$ 表示[按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。
输入格式
第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例数量。
每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 1$）。
每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \leq b_i \leq 1$）。
保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$）。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 1$）。
每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \leq b_i \leq 1$）。
保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。
输出格式
对于每个测试用例，输出一行，内容可为 "Ajisai"（若紫阳最优策略必胜）、"Mai"（若舞最优策略必胜）、"Tie"（若双方最优策略下为平局）。
输出时不区分大小写，例如 "mAi"、"mai"、"MAI"、"maI" 都将被视为 "Mai"。
输出时不区分大小写，例如 "mAi"、"mai"、"MAI"、"maI" 都将被视为 "Mai"。
输入输出样例
输入 #1
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
输出 #1
Ajisai Mai Tie Ajisai Tie Mai
说明/提示
在第一个样例中，可能的一轮操作如下：
第 $1$ 回合，紫阳选择交换 $a_1$ 和 $b_1$。此时数组 $a = [1, 0, 0, 1]$，$b = [1, 0, 1, 1]$。
第 $2$ 回合，舞选择跳过操作。
第 $3$ 回合，紫阳选择交换 $a_3$ 和 $b_3$。此时数组 $a = [1, 0, 1, 1]$，$b = [1, 0, 0, 1]$。
第 $4$ 回合，舞选择交换 $a_4$ 和 $b_4$。此时数组 $a = [1, 0, 1, 1]$，$b = [1, 0, 0, 1]$。
最终，紫阳的得分为 $1 \oplus 0 \oplus 1 \oplus 1 = 1$，舞的得分为 $1 \oplus 0 \oplus 0 \oplus 1 = 0$，因此紫阳获胜。
注意，上述操作不是一定符合最优策略。
第 $1$ 回合，紫阳选择交换 $a_1$ 和 $b_1$。此时数组 $a = [1, 0, 0, 1]$，$b = [1, 0, 1, 1]$。
第 $2$ 回合，舞选择跳过操作。
第 $3$ 回合，紫阳选择交换 $a_3$ 和 $b_3$。此时数组 $a = [1, 0, 1, 1]$，$b = [1, 0, 0, 1]$。
第 $4$ 回合，舞选择交换 $a_4$ 和 $b_4$。此时数组 $a = [1, 0, 1, 1]$，$b = [1, 0, 0, 1]$。
最终，紫阳的得分为 $1 \oplus 0 \oplus 1 \oplus 1 = 1$，舞的得分为 $1 \oplus 0 \oplus 0 \oplus 1 = 0$，因此紫阳获胜。
注意，上述操作不是一定符合最优策略。