首页 > 代码库 > poj 1704 Georgia and Bob （nim）
poj 1704 Georgia and Bob （nim）
题意：
N个棋子，位置分别是p[1]...p[N]。
Georgia和Bob轮流，每人每次可选择其中一个棋子向左移动若干个位置（不能超过前一个棋子，不能超出最左边【位置1】且不能不移）
Georgia先手，问谁赢。
思路：
将棋子按位置从右到左两个两个作为一对。若棋子总个数是奇数，将第一个棋子和【位置0】作为一对。（可想象位置0放了一个棋子）。
情况一：先手若移动某对棋子中的第一个棋子K位，则后手可将该对棋子中的第二个棋子也移动K位。即这种情况不对结果产生影响。
情况二：先手若移动某对棋子中的第二个棋子。可将每对棋子两个棋子之间的距离看成一堆石头的个数。则此题和取石子一模一样！
OK,直接看代码..
代码：
int T,n;int p[1005], a[1005];int main(){ cin>>T; while(T--){ scanf("%d",&n); rep(i,1,n) scanf("%d",&p[i]); sort(p+1,p+1+n); p[0]=0; int num=0; for(int i=n;i>0;i-=2){ a[++num]=p[i]-p[i-1]-1; } int ans=a[1]; rep(i,2,num){ ans=ans^a[i]; } if(ans) puts("Georgia will win"); else puts("Bob will win"); }}
poj 1704 Georgia and Bob （nim）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。