UVa 12409 Kisu Pari Na 1

题目描述本题来源于一个有趣的游戏。给定一个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,j1)(i, j1)(i,j1)向右新的dd(i,j)−1d d(i, j) - 1dd(i,j)−1如果从(i,j)(i, j)(i,j)移动到(i1,j)(i1, j)(i1,j)向下新的dd(i,j)−1d d(i, j) - 1dd(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−1jjj从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//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){intT;scanf(%d,T);for(intcaseNum1;caseNumT;caseNum){intR,C;scanf(%d %d,R,C);longlongxorSum0;for(inti0;iR;i){for(intj0;jC;j){longlongcoins;scanf(%lld,coins);// 计算到右下角的曼哈顿距离intdistToEnd(R-1-i)(C-1-j);// 只考虑距离为奇数的单元格if(distToEnd%21){xorSum^coins;}}}if(xorSum!0)printf(Case %d: win\n,caseNum);elseprintf(Case %d: lose\n,caseNum);}return0;}