当前位置: 代码迷 >> 综合 >> POJ - 1704 (Georgia and Bob)
  详细解决方案

POJ - 1704 (Georgia and Bob)

热度:82   发布时间:2024-01-27 04:23:53.0

题意:有一行格子(<=10000),有 n 颗棋子分布在这些格子,每个格子至多有一个棋子,现在每回合可以选择一个棋子往左移动,移动步数任意,但是不能越过边界(即0)或者它左边的棋子,问先手必胜还是后手必胜;

 

分析:

①考虑每相邻的两颗棋子构成一个组合,若棋子数为奇数则加一个 0 的虚拟棋子,(a1,a2),(a3,a4) ... ,那么每组棋子之间的空格数就相当于一堆石子的数量,任意取,取完为止,就转化为了 n/2 堆石子选取的 Nim 博弈问题,不考虑组间的空格,我们可以容易的找出必胜方;

②再考虑每组间的空格,对于①中的必胜方,开始考虑组间空格之后,相当于对手方先手(为什么,因为必胜方在①中已经走完了不考虑组间空格的最后一步),若先手能且只能选择一组(ai,ai+1),把 ai 左移 x 步 ,则必胜方可以跟着先手把 ai+1 左移同样的位置 x 步,这样下来整个局势还是没有改变,所以考不考虑组间的空格不影响胜败;

(PASS:只是推理的时候假设先走完所有组内空格再走组间空格,实际操作的时候不会这么规矩,但不影响必胜方)

 

代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#define read(n) scanf("%d",&n)
using namespace std;int num[1000+10];
int n;int main()
{int q;read(q);while(q--){read(n);for(int i=0;i<n;i++) read(num[i]);if(n%2==1) num[n++]=0;sort(num,num+n);int x=0;for(int i=0;i<n;i+=2){x^=num[i+1]-num[i]-1;}if(x) puts("Georgia will win");else puts("Bob will win");}
}