#P18342. [OMI 2025]Mimo and Yuyu
[OMI 2025]Mimo and Yuyu
题目描述
米莫(Mimo)和悠悠(Yuyu)刚拼完一幅 1000 块的拼图,便发明了一个新游戏。
游戏在一个 的矩形棋盘上进行,有无限供应的 María 饼干。棋盘的行从上到下编号为 ,列从左到右编号为 。格子 表示第 行、第 列。同一个格子可以同时放置任意多块饼干。
初始共有 块饼干,第 块放在 。
两人轮流操作,米莫先手。每次操作,当前玩家需要选择一块饼干 ,同时指定一条由互不相同的格子构成的路径
其中必须满足:
- ;
- 选中的饼干 位于起点 ;
- 相邻路径格子在棋盘上具有公共边,即对所有 ,
- 途经格子的列编号不增加:
- 路径终点位于第一列:;
- 第一步必须向左移动一格:。因此路径中只有起点属于第 列。
执行操作时,玩家吃掉起点的那块饼干 ,然后在路径经过的每一个其他格子
各放置一块新饼干,结束本回合。路径格子在本次操作中不得重复,但已经存在的饼干不会妨碍路径经过,新饼干可以与已有饼干重叠。
轮到某玩家时,如果不存在合法操作,则该玩家失败。双方都采用最优策略,请判断先手米莫是否能够获胜。
输入格式
第一行一个整数 ,表示测试用例数量。
对于每组测试用例:
- 第一行三个整数 ,依次表示棋盘行数、列数、初始饼干数量。
- 接下来 行,每行两个整数 ,表示第 块饼干的位置。
同一组内允许多个饼干的位置完全相同。
输出格式
每组测试用例输出一行:
- 若米莫(先手)必胜,输出
Mimo; - 若悠悠(后手)必胜,输出
Yuyu。
大小写必须完全一致。
样例 1
输入:
1
2 3 2
2 2
1 3
输出:
Mimo
样例 2
输入:
2
6 4 3
2 3
4 2
6 4
6 4 11
6 3
5 3
4 3
3 3
2 3
2 3
2 2
3 2
4 2
4 2
4 1
输出:
Mimo
Yuyu
数据范围
令 为同一个输入文件内所有测试用例的 之和。
$$\begin{aligned} 1 &\le t\le 10^4,\\ 1 &\le n,m,k\le 2\times10^5,\\ S_k &\le 2\times10^5,\\ 1 &\le x_i\le n,\\ 1 &\le y_i\le m. \end{aligned}$$子任务
| 子任务 | 分值 | 额外条件 |
|---|---|---|
| 1 | 12 | |
| 2 | ,所有 | |
| 3 | ||
| 4 | ||
| 5 | ,所有饼干在同一列 | |
| 6 | 25 | |
| 7 | 15 |