当前位置：首页 > news >正文

UVa 12409 Kisu Pari Na 1

news 2026/5/2 3:19:27

题目描述

本题来源于一个有趣的游戏。给定一个R×CR \times CR×C的网格，每个格子中放有若干硬币（数量范围为[0,109][0, 10^9][0,109]）。两名玩家轮流操作，每次操作选择一个非空的格子，从中取出一枚或多枚硬币，将这些硬币全部移动到该格子正右方或正下方的相邻格子中（不能拆分移动）。最右边一列的格子不能向右移动，最下面一行的格子不能向下移动，右下角的格子无法进行任何操作。无法进行任何操作的玩家输掉游戏。Pinky\texttt{Pinky}Pinky先手，双方都采取最优策略，判断Pinky\texttt{Pinky}Pinky是否能获胜。

题目分析

游戏性质

首先需要理解这个游戏的基本结构。游戏进行的过程中，硬币只能向右或向下移动，这意味着硬币的移动方向是单向的——它们只会越来越靠近右下角。最终，所有硬币都会聚集到右下角格子，因为只有那里无法再移动。

这是一个典型的公平组合博弈问题，我们可以尝试将其转化为已知的博弈模型。注意每次操作只能从一个格子移动若干硬币到一个相邻格子（右或下），这种“从一个堆中取走若干物品放到另一个堆”的模型，往往与Nim\texttt{Nim}Nim游戏或其变种有关。

关键观察

考虑从某个格子(i,j)(i, j)(i,j)到达终点(R−1,C−1)(R-1, C-1)(R−1,C−1)（下标从000开始）所需要的最小步数。由于只能向右或向下移动，这个最小步数就是曼哈顿距离：

d(i,j)=(R−1−i)+(C−1−j) d(i, j) = (R - 1 - i) + (C - 1 - j)d(i,j)=(R−1−i)+(C−1−j)

这个距离d(i,j)d(i, j)d(i,j)的奇偶性是解决问题的核心。

为什么奇偶性如此重要？因为每一次移动都会改变硬币所在格子的ddd值：

如果从(i,j)(i, j)(i,j)移动到(i,j+1)(i, j+1)(i,j+1)（向右），新的d=d(i,j)−1d = d(i, j) - 1d=d(i,j)−1
如果从(i,j)(i, j)(i,j)移动到(i+1,j)(i+1, j)(i+1,j)（向下），新的d=d(i,j)−1d = d(i, j) - 1d=d(i,j)−1

也就是说，每次操作都会使被移动硬币的ddd值减少恰好111。因此，一枚硬币从起点到终点的过程中，ddd值会从初始值逐渐递减到000。每移动一次，ddd的奇偶性就会改变一次。

博弈转化

设SoddS_{\text{odd}}Sodd为所有d(i,j)d(i, j)d(i,j)为奇数的格子集合，SevenS_{\text{even}}Seven为所有d(i,j)d(i, j)d(i,j)为偶数的格子集合。

观察一次操作的影响：

如果从SoddS_{\text{odd}}Sodd中的一个格子移动硬币到SevenS_{\text{even}}Seven中的一个格子（因为减少111改变奇偶性），那么这些硬币离开了SoddS_{\text{odd}}Sodd，进入了SevenS_{\text{even}}Seven。
如果从SevenS_{\text{even}}Seven中的一个格子移动硬币，它们会进入SoddS_{\text{odd}}Sodd。

但这还不是Nim\texttt{Nim}Nim游戏。我们需要一个更巧妙的观点：

实际上，我们可以将每个SoddS_{\text{odd}}Sodd格子中的硬币数量视为一个独立的Nim\texttt{Nim}Nim堆。理由如下：

当玩家从SoddS_{\text{odd}}Sodd格子移动硬币时，这些硬币离开了SoddS_{\text{odd}}Sodd（进入SevenS_{\text{even}}Seven），相当于从对应的Nim\texttt{Nim}Nim堆中取出任意正数量的物品（这些物品被“丢弃”出Nim\texttt{Nim}Nim游戏）。
当玩家从SevenS_{\text{even}}Seven格子移动硬币时，这些硬币进入了SoddS_{\text{odd}}Sodd，相当于向对应的Nim\texttt{Nim}Nim堆中添加物品。但在公平博弈中，允许“增加”操作会破坏Nim\texttt{Nim}Nim模型。然而，这里有一个关键：如果一个玩家从SevenS_{\text{even}}Seven向SoddS_{\text{odd}}Sodd添加硬币，对方在下一次回合一定可以将这些新添加的硬币再次移回SevenS_{\text{even}}Seven（因为从SoddS_{\text{odd}}Sodd移动一步必然进入SevenS_{\text{even}}Seven）。这种对称性使得SevenS_{\text{even}}Seven中的硬币可以被视作“安全的”——它们不会真正影响胜负，因为任何增加都可以被对方立即撤销。
更严格的分析（Sprague–Grundy\texttt{Sprague–Grundy}Sprague–Grundy定理）可以证明：每个格子的Grundy\texttt{Grundy}Grundy数等于其到终点的曼哈顿距离的奇偶性决定的值。对于ddd为偶数的格子，Grundy\texttt{Grundy}Grundy数为000；对于ddd为奇数的格子，Grundy\texttt{Grundy}Grundy数等于该格子中的硬币数量。因此，整个游戏的Grundy\texttt{Grundy}Grundy数就是所有ddd为奇数的格子中硬币数量的异或和。

结论

游戏胜负由以下规则判定：

胜负=⨁(i,j)∈Soddcoins[i][j]≠0 \text{胜负} = \bigoplus_{(i,j) \in S_{\text{odd}}} coins[i][j] \neq 0胜负=(i,j)∈Sodd⨁coins[i][j]=0

即：对所有曼哈顿距离d(i,j)d(i, j)d(i,j)为奇数的格子中的硬币数量进行异或运算，如果结果不为000，则先手（Pinky\texttt{Pinky}Pinky）获胜；否则先手失败。

解题思路

根据上述结论，解题步骤非常简单：

对于每个测试用例，读取网格的行数RRR和列数CCC。
遍历所有格子(i,j)(i, j)(i,j)，iii从000到R−1R-1R−1，jjj从000到C−1C-1C−1。
对于每个格子，计算到右下角的曼哈顿距离：
d=(R−1−i)+(C−1−j) d = (R - 1 - i) + (C - 1 - j)d=(R−1−i)+(C−1−j)
如果ddd是奇数，将该格子中的硬币数量与当前的异或和进行异或运算。
遍历结束后，若异或和不为000，则输出win\texttt{win}win，否则输出lose\texttt{lose}lose。

复杂度分析

时间复杂度：O(R×C)O(R \times C)O(R×C)，每个格子仅处理一次。
空间复杂度：O(1)O(1)O(1)额外空间（输入可以边读边处理，无需存储整个网格）。

由于题目保证R×C≤50000R \times C \leq 50000R×C≤50000，这个复杂度是完全可行的。

注意事项

硬币数量最大可达10910^9109，需要使用long long\texttt{long long}long long类型存储。
异或运算可以直接应用在long long\texttt{long long}long long类型上。
输入量较大，建议使用scanf\texttt{scanf}scanf提高读取效率。

参考代码

// Kisu Pari Na 1// UVa ID: 12409// Verdict: Accepted// Submission Date: 2026-04-26// UVa Run Time: 0.030s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){intT;scanf("%d",&T);for(intcaseNum=1;caseNum<=T;++caseNum){intR,C;scanf("%d %d",&R,&C);longlongxorSum=0;for(inti=0;i<R;++i){for(intj=0;j<C;++j){longlongcoins;scanf("%lld",&coins);// 计算到右下角的曼哈顿距离intdistToEnd=(R-1-i)+(C-1-j);// 只考虑距离为奇数的单元格if(distToEnd%2==1){xorSum^=coins;}}}if(xorSum!=0)printf("Case %d: win\n",caseNum);elseprintf("Case %d: lose\n",caseNum);}return0;}