首页 > 代码库 > poj 1704 Georgia and Bob 博弈
poj 1704 Georgia and Bob 博弈
排成一条直线的格子上有n个棋子，两个人每个人每次可以选择一枚棋子向左移动任意步数，但是不可以越过棋子，无法进行操作的一方失败，问谁会失败。
先考虑偶数个棋子时的情况，将棋子从左到右两两配对，转化成n/2堆石子，每堆石子的个数为中间的空格数，这样每次向左移动可以看做在一堆石子中取了任意个，转换成了nim博弈，两两配对的石子中的左面的石子如果向左移动，那么相当于石子的数目会增加，但不会改变胜负状态，因为下一个人可以移动右面的石子来抵消。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int a[1010];int main(){ int n,cas; scanf("%d",&cas); while(cas--) { int i; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&a[i]); if(n%2==1) a[n++]=0; sort(a,a+n); int ans=0; for(i=1;i<n;i+=2) ans^=(a[i]-a[i-1]-1); if(ans==0) printf("Bob will win\n"); else printf("Georgia will win\n"); } return 0;}
poj 1704 Georgia and Bob 博弈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。