首页 > 代码库 > HDU 1907 John(博弈)

HDU 1907 John(博弈)

题目

 

参考了博客:http://blog.csdn.net/akof1314/article/details/4447709

 

 

//0 1 -2//1 1 -1//0 2 -1//1 2 -1//2 2 -2//0 3 -1//1 3 -1 //2 3 -1//3 3 -2//0 4 -1//1 4 -1//2 4 -1//3 4 -1//4 4 -2//0 5 -1//1 5 -1//2 5 -1//3 5 -1/*  尼姆博弈。对于N堆的糖,一种情况下是每堆都是1,那么谁输谁赢看堆数就知道;对于不都是1的话,若这些堆是奇异局势,或说他们是非奇异局势,但非奇异局势皆可以转换到奇异局势(具体转变看上一篇介绍)。       经典的尼姆问题是谁哪拿到最后一个则谁赢,本题是拿最后一个的输。下面分析第二种情况:1.初始给的是奇异局势的话,则先取者为输。2.初始给的是非奇异局势的话,则先取者为赢。辗转转换非奇异、奇异的次数是相对的。*/#include<stdio.h>#include<string.h>int main(){    int t;    scanf("%d",&t);    while(t--) {        int n;        int a[100];        scanf("%d",&n);        int sum=0,k=0;        for(int i=0;i<n;i++) {            scanf("%d",&a[i]);            sum^=a[i];//这样子判断奇异局势吗?用 ^ ?            if(a[i]!=1)k=1;        }        if(k==0) {            if(n%2)printf("Brother\n");            else printf("John\n");        }        else {            if(sum==0)printf("Brother\n");////这样子判断奇异局势,为0奇异            else printf("John\n");//否则非奇异        }    }    return 0;}
View Code

 

HDU 1907 John(博弈)