题解 CF142D 【Help Shrek and Donkey 2】/ Nim - K 问题口胡证明

## 题意 - 给定一个 $n\times m$ 的棋盘。棋盘中 `-` 代表空格，`G` 代表绿色棋子，`R` 代表红色棋子。每行至多有两个士兵。 - 先手执绿棋。 - 每个回合玩家可以选择 $1$ 到 $k$ 个棋子在当前行内向左或向右任意移动一次，但不能越过另一个棋子，也不能在不同行之间移动。 - 若一方在移动后能使另一方无法移动，则获胜。 - 求最后谁获胜或平局。 - $1\leq n,m,k\leq 100$。 ~~抄袭了 xht 神仙的风格。~~  --- ## 解法 恶心的细节题。  首先考虑特殊情况。可以发现当某一行内只有同色棋子，则持有这枚棋子的玩家处于不败态，因为在任何情况下这枚棋子都是可以移动的（除非这些棋子将整行塞满了）。当两名玩家均处于不败态时则平局，否则处于不败态的那个玩家必胜。 然后考虑一般情况，对每行分别考虑，可以视作该行内有 **两棋子间空格数** 的棋子，共有 $n$ 堆石子，最终谁把石子取完谁获胜。 先来考虑这个模型的正确性，当 A 取完之后，B 只能将棋子朝一个方向移动，此时 A 只需要穷追不舍，将棋子怼到 B 移动的棋子的脸上，则最终必然是 B 不能移动。 然后就是怎么解决这个问题。这是一个经典的 $\textbf{Nim - K}$ 问题。结论是每一堆的同一位二进制加起来 $\bmod\ (k+1)$ **均**为 0，则先手必败，否则先手必胜。 下面给出~~口胡~~证明。 --- ### $\text{Proof}$ ※ 下以“条件”代指“每一堆的同一位二进制加起来 $\bmod\ (k+1)$ 均为 0”。 首先明确必败态。终态每堆都是 $0$，显然满足条件。 若此时为先手必败态，先手可以对至多 $k$ 堆进行操作，使若干个位置不满足条件，此时后手可以通过一次操作改变先手改变的若干二进制位使其再次满足条件，因为不论先后手最多都是操作 $k$ 堆石子，所以这显然是可以做到的。 若此时不是先手必败态，因为 $x \bmod\ (k+1)\leq k$，所以先手最多只需将 $k$ 个二进制位 $-1$ 就可以满足条件，最坏情况下这 $k$ 个位置分散于 $k$ 堆中，而先手最多操作 $k$ 堆，因此先手必然可以将当前状态操作为先手必败态，自己变为后手，因此不满足条件的必然是后手必败态。 确实有点口胡，感性理解吧各位。  ```cpp #include<bits/stdc++.h> #define N 100 #define reg register #define inl inline using namespace std; int n,m,k,a[N+5]; char ch[N+5][N+5]; inl string Solve() { for(reg int i=0;i<=8;i++) { reg int res=0; for(reg int j=1;j<=n;j++) res+=(a[j]>>i)&1; if(res%(k+1)) return "First"; } return "Second"; } int main() { reg int Fg=0,Fr=0; scanf("%d %d %d",&n,&m,&k); for(reg int i=1;i<=n;i++) { scanf("%s",ch[i]+1); reg int G=0,R=0,sG=0,sR=0; for(reg int j=1;j<=m;j++) { if(ch[i][j]=='G') G=j,sG++; if(ch[i][j]=='R') R=j,sR++; } if(G && R) a[i]=abs(G-R)-1; Fg+=((!sR)&&sG&&(sG<m)); Fr+=((!sG)&&sR&&(sR<m)); } if(Fg && !Fr) return puts("First"),0; if(!Fg && Fr) return puts("Second"),0; if(Fg && Fr) return puts("Draw"),0; puts(&Solve()[0]); return 0; } ```