E. Mimo & Yuyu

题目描述

Mimo 和 Yuyu 刚刚完成了他们美丽的贝拉斯艺术宫的1000块拼图！现在他们正在寻找其他娱乐方式。

有一个 $n \times m$ 的单元格网格，列从左到右标记为 $1, 2, \dots, m$，行从上到下标记为 $1, 2, \dots, n$。令 $(u, v)$ ($1 \le u \le n, 1 \le v \le m$) 表示第 $u$ 行和第 $v$ 列的单元格。每个单元格可以包含任意数量的棋子，这些棋子之间没有区别。最初，有 $k$ 个棋子，第 $i$ 个位于 $(x_i, y_i)$。

Mimo 和 Yuyu 现在轮流玩一个游戏。轮到他/她时，玩家选择一个当前在网格中的棋子 $c$ 以及一个由不同单元格组成的序列 $(a_1, b_1), (a_2, b_2), \dots, (a_p, b_p)$ ($p \ge 2$)，使得以下条件成立：

• $c$ 位于 $(a_1, b_1)$。
• 对于所有的 $i$ ($1 \le i < p$)，满足 $|a_{i+1} - a_i| + |b_{i+1} - b_i| = 1$。也就是说，序列中的相邻单元格在网格中必须是相邻的。
• $b_1 \ge b_2 \ge \dots \ge b_p$。也就是说，序列单元格的列必须形成一个非递增序列（从不远离第1列）。
• $b_p = 1$。也就是说，序列的最后一个单元格必须位于第1列。
• $b_1 > b_2$。特别地，$b_2 = b_1 - 1$。也就是说，$(a_1, b_1)$ 必须是序列中位于第 $b_1$ 列的唯一单元格。

然后，他/她从网格中移除 $c$，并向 $(a_2, b_2), (a_3, b_3), \dots, (a_p, b_p)$ 各添加1个棋子。这样就结束了他/她的回合。

无法进行操作的玩家输掉游戏。Mimo 先手。如果两个玩家都以最佳方式进行游戏，请确定谁将获胜。

解题思路

这是一个公平组合游戏，通常可以通过分析游戏状态来找到必胜策略。关键在于理解一步操作如何影响游戏状态，以及玩家是否能通过维持某种特定条件来强制获胜。分析根据网格维度 n 的不同而有所区别。

情况一：n > 1 (一般情况)

当 n > 1 时，玩家在选择移动路径方面有很大的自由度。一步操作包括选择一个位于 $(a_1, b_1)$ 的棋子，并选择一条由相邻单元格组成的路径 $(a_2, b_2), \dots, (a_p, b_p)$，使得 $b_1 > b_2 \ge \dots \ge b_p = 1$。位于 $(a_1, b_1)$ 的棋子被移除，新的棋子被放置在路径上的其他单元格中。

关键的观察是，通过恰当地选择路径，玩家可以决定向任何列 $j$（其中 $j < b_1$）添加奇数或偶数个棋子。对于任何这样的列 $j$，玩家可以使路径访问它奇数次或偶数次，从而翻转该列中棋子数量的奇偶性或保持不变。

这将游戏转化为 Nim 游戏的一个变体。我们用包含奇数个棋子的列（索引 > 1）的集合来定义游戏状态。设这个集合为 $S_{odd}$。

一步操作包括从列 $b_1$ 中取出一个棋子。这个动作会翻转列 $b_1$ 中棋子数量的奇偶性，实际上是从 $S_{odd}$ 中添加或移除 $b_1$。然后，玩家可以有选择地翻转任何索引小于 $b_1$ 的列的奇偶性。

这等价于一个 Nim 游戏，其中的“石子堆”就是列的索引本身。在一个位于 $b_1$ 列的棋子上进行操作，就像取走石子堆 $b_1$，并能产生任何小于 $b_1$ 的石子堆组合。Nim 游戏的必胜策略是总是移动到一个 Nim 和（异或和）为零的状态。

在我们的问题中，策略可以更简单地陈述：

• 如果 $S_{odd}$ 为空，当前局面是必败态（P-position）。任何移动都会使 $S_{odd}$ 非空。
• 如果 $S_{odd}$ 非空，当前局面是必胜态（N-position）。令 $y_{max}$ 为 $S_{odd}$ 中的最大列索引。当前玩家可以选择 $y_{max}$ 列中的任意一个棋子。这会翻转 $y_{max}$ 的奇偶性，将其从 $S_{odd}$ 中移除。然后，对于 $S_{odd}$ 中所有其他的列 $j$（注意它们必须小于 $y_{max}$），玩家选择路径来同样翻转它们的奇偶性。结果是一个新的状态，其中 $S_{odd}$ 为空。

因此，Mimo（先手玩家）获胜，当且仅当初始集合 $S_{odd}$ 非空。

情况二：n = 1 (特殊情况)

当 n = 1 时，只有一行。棋子可以走的路径是固定的。一个位于 $(1, y)$ 的棋子必须沿着路径 $(1, y-1), (1, y-2), \dots, (1, 1)$ 移动。这意味着从列 $y$ 移除一个棋子会向每个列 $j$（其中 $1 \le j < y$）添加一个新棋子。

这改变了游戏的动态。让我们分析棋子数量的奇偶性。对一个位于列 $y > 1$ 的棋子进行操作，会翻转从第2列到第 $y$ 列的每一列中棋子数量的奇偶性。

考虑一种配对策略。让我们关注第2列中棋子的奇偶性。

• 如果一个玩家移动一个来自列 $y > 2$ 的棋子，第2列中的棋子数量增加一，其奇偶性被翻转。
• 如果一个玩家移动一个来自第2列的棋子，第2列中的棋子数量减少一，其奇偶性也被翻转。

假设轮到 Mimo，并且第2列中的棋子数 $C_2$ 是偶数。

• 如果 Mimo 移动一个来自列 $y > 2$ 的棋子，$C_2$ 变为奇数。Yuyu 可以通过移动一个刚出现在第2列的新棋子来回应，使 $C_2$ 再次变为偶数。最终结果是，一个来自列 $y$ 的棋子被消耗掉了，而 $C_2$ 的奇偶性在 Mimo 下一轮开始时恢复了。
• 如果 Mimo 移动一个来自第2列的棋子，$C_2$ 变为奇数。Yuyu 现在面临第2列有奇数个棋子的情况。

这表明，一个位于列 $y > 2$ 的棋子不是直接的威胁；它是一个可以被抵消的潜在移动。决定性的移动涉及第2列的棋子。一个在其回合开始时第2列有奇数个棋子的玩家，可以从第2列进行移动，给对手留下偶数个。对手随后被迫要么从第2列移动（再次给先手玩家优势），要么从 $y > 2$ 移动，而这种移动可以被配对并有效中和。

游戏归结为第2列中棋子数量的奇偶性。Mimo 获胜，当且仅当第2列中最初的棋子数量是奇数。大于2的列中的棋子不影响结果。

总结

• 对于 n > 1，如果至少有一个列 y > 1 含有奇数个棋子，Mimo 获胜。否则，Yuyu 获胜。
• 对于 n = 1，如果第2列中的棋子数量是奇数，Mimo 获胜。否则，Yuyu 获胜。

所提供的 C++ 代码正确地实现了这一逻辑，它维护一个集合 s 来存储含有奇数个棋子的列。对于 n=1，它特殊处理，只认为第2列的棋子是相关的。对于 n>1，它考虑所有列 y>1。如果在处理完所有初始棋子后集合 s 为空，Yuyu 获胜；否则，Mimo 获胜。

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <tuple>
#include <vector>
using namespace std;
#define int long long
// #define mod 1000000007

#define N 500005
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    set<int> s;
    int sum = 0;
    while (k--) {
        int x, y;
        cin >> x >> y;
        if (n == 1) {
            y = (y == 2? 2 : 1);
        }
        if (y <= 1) continue;
        if (s.find(y) != s.end()) {
            s.erase(y);
        } else {
            s.insert(y);
        }
    }
    if (!s.empty()) {
        cout << "Mimo" << endl;
    } else {
        cout << "Yuyu" << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef DEBUG
    freopen("./input.txt", "r", stdin);
#endif
    int t;
    cin >> t;
    while (t--) {
#ifdef DEBUG
        static int test_num = 1;
        cout << "test case: " << test_num++ << endl;
#endif
        solve();
    }
}