[Problem Discription] \color{blue}{\texttt{[Problem Discription]}} [Problem Discription]
[Analysis] \color{blue}{\texttt{[Analysis]}} [Analysis]
这是一道很好的博弈论的题目。
首先，不难发现这题最极端的必败情况是所有的石子都两两相邻。因为两两相邻的话先手无论对哪一堆石子进行多少距离的移动，后手都可以对开始时在它后面和它相邻（可以发现一定有，因为两堆相邻的石子必然只能移动前面的那一堆）的那一堆石子移动相同的距离，这样，两堆石子仍然相邻，且先手一定更先无路可走。
那就都往这个方向靠。既然石子被移动到两两相邻的状态后的最终输赢已经和移动方案无关，那么胜负就取决于谁最后一次移动把石子移动到这个状态。把石子两两相邻的状态成为决定状态。设 p i p_{i} pi 表示第 i i i 堆石子的位置。
-
如果 n n n 为偶数，那么决定状态一定是第 1 , 2 1,2 1,2 两堆石子相邻，第 3 , 4 3,4 3,4 两堆石子相邻，……，第 ( n − 1 ) , n (n-1),n (n−1),n 两堆石子相邻。问题进一步抽象后，相当于有 p 2 − p 1 − 1 , p 4 − p 3 − 1 , … , p n − p n − 1 − 1 p_{2}-p_{1}-1,p_{4}-p_{3}-1,\dots,p_{n}-p_{n-1}-1 p2−p1−1,p4−p3−1,…,pn−pn−1−1 共 n 2 \dfrac{n}{2} 2n 堆“石子”，两人轮流操作，可以在任意一堆取任意多，谁最后一个操作谁赢。这就是典型的 Nim 游戏。
-
如果 n n n 为奇数。最终第 1 1 1 堆石子一定被移动到第 1 1 1 号格子，可以理解成在第 0 0 0 号格子还有一堆“石子”。决定状态是第 0 , 1 0,1 0,1 两堆石子相邻，第 2 , 3 2,3 2,3 两堆石子相邻，……，第 ( n − 1 ) , n (n-1),n (n−1),n 两堆石子相邻。相当于有 p 1 − 1 , p 3 − p 2 − 1 , … , p n − p n − 1 − 1 p_1-1,p_{3}-p_{2}-1,\dots,p_{n}-p_{n-1}-1 p1−1,p3−p2−1,…,pn−pn−1−1 共 n + 1 2 \dfrac{n+1}{2} 2n+1 堆石子，依然是一个 Nim 游戏。
很巧妙的转化，很不错的题目。
Code \color{blue}{\text{Code}} Code
const int N=1010;int n,Nim,pos[N],T;int main(){for(int Case=1,T=read();Case<=T;Case++){Nim=0;n=read(); for(int i=1;i<=n;i++)pos[i]=read();sort(pos+1,pos+n+1);for(int i=n;i>=1;i-=2)Nim^=(pos[i]-pos[i-1]-1);if (Nim==0) puts("Bob will win");else puts("Georgia will win");}return 0;
}