HDU 1907 John (Nim博弈)

时间:2022-08-31 13:58:08

John

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2034    Accepted Submission(s): 1096

Problem Description
Little John is playing very funny game with his younger brother. There is one big box filled with M&Ms of different colors. At first John has to eat several M&Ms of the same color. Then his opponent has to make a turn. And so on. Please note that each player has to eat at least one M&M during his turn. If John (or his brother) will eat the last M&M from the box he will be considered as a looser and he will have to buy a new candy box.

Both of players are using optimal game strategy. John starts first always. You will be given information about M&Ms and your task is to determine a winner of such a beautiful game.

 
Input
The first line of input will contain a single integer T – the number of test cases. Next T pairs of lines will describe tests in a following format. The first line of each test will contain an integer N – the amount of different M&M colors in a box. Next line will contain N integers Ai, separated by spaces – amount of M&Ms of i-th color.

Constraints:
1 <= T <= 474,
1 <= N <= 47,
1 <= Ai <= 4747

 
Output
Output T lines each of them containing information about game winner. Print “John” if John will win the game or “Brother” in other case.
 
Sample Input
2
3
3 5 1
1
1
 
Sample Output
John
Brother
 
Source
 
Recommend
lcy
 

尼姆博奕(Nimm Game):有三堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,多者不限,最后取光者得胜。

这种情况最有意思,它与二进制有密切关系,我们用(a,b,c)表示某种局势,首先(0,0,0)显然是奇异局势,无论谁面对奇异局势,都必然失败。第二种奇异局势是
(0,n,n),只要与对手拿走一样多的物品,最后都将导致(0,0,0)。仔细分析一下,(1,2,3)也是奇异局势,无论对手如何拿,接下来都可以变为(0,n,n)的情
形。

计算机算法里面有一种叫做按位模2加,也叫做异或的运算,我们用符号(^)表示这种运算。这种运算和一般加法不同的一点是1^1=0。先看(1,2,3)的按位模2加的结
果:

1 =二进制01
2 =二进制10
3 =二进制11 (^)
———————
0 =二进制00 (注意不进位)

对于奇异局势(0,n,n)也一样,结果也是0。任何奇异局势(a,b,c)都有 a ^ b ^ c =0。如果我们面对的是一个非奇异局势(a,b,c),

要如何变为奇异局势呢?假设 a < b< c,我们只要将 c 变为  a ^ b,即可,因为有如下的运算结果:  a ^ b ^( a ^ b)=(a ^ a) ^ ( b ^ b ) = 0 ^ 0 = 0。

要将c 变为a ^ b,只要从 c中减去 c -(a ^ b)即可。

#include<iostream>
#include<cstdio>
#include<cstring> using namespace std; int main(){ //freopen("input.txt","r",stdin); int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int ans=,flag=,x;
for(int i=;i<n;i++){
scanf("%d",&x);
ans^=x;
if(x>) //当所有数据都为1时的特判
flag=;
}
if(flag){
if(ans==)
puts("Brother");
else
puts("John");
}else{
if(n&)
puts("Brother");
else
puts("John");
}
}
return ;
}

HDU 1907 John (Nim博弈)的更多相关文章

  1. HDU 1907 John nim博弈变形

    John Problem Description   Little John is playing very funny game with his younger brother. There is ...

  2. HDU 1907 John(博弈)

    题目 参考了博客:http://blog.csdn.net/akof1314/article/details/4447709 //0 1 -2 //1 1 -1 //0 2 -1 //1 2 -1 / ...

  3. hdu 1907 John&amp&semi;&amp&semi; hdu 2509 Be the Winner(基础nim博弈)

    Problem Description Little John is playing very funny game with his younger brother. There is one bi ...

  4. hdu 1907 John (anti—Nim)

    John Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)http://acm.h ...

  5. POJ 3480 &amp&semi;amp&semi; HDU 1907 John(尼姆博弈变形)

    题目链接: PKU:http://poj.org/problem? id=3480 HDU:http://acm.hdu.edu.cn/showproblem.php? pid=1907 Descri ...

  6. HDU - 1907 John 反Nimm博弈

    思路: 注意与Nimm博弈的区别,谁拿完谁输! 先手必胜的条件: 1.  每一个小游戏都只剩一个石子了,且SG = 0. 2. 至少有一堆石子数大于1,且SG不等于0 证明:1. 你和对手都只有一种选 ...

  7. HDU 1907 John(取火柴博弈2)

    传送门 #include<iostream> #include<cstdio> #include<cstring> using namespace std; int ...

  8. hdu 1907 John(anti nim)

    John Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submis ...

  9. hdu 1907 John &lpar;尼姆博弈&rpar;

    John Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Total Submis ...

随机推荐

  1. Android线程处理

    对JAVA的线程相信大家都有一定的认识,本篇就让我们一起探讨一下Android中的线程问题,对于线程和进程的区别我就不再赘述,有兴趣的小童鞋可以百度一下,讲解的非常详细,相信大家经常可以听到关于线程的 ...

  2. Python学习笔记12—类

    典型的类和调用方法: #!/usr/bin/env Python # coding=utf-8 __metaclass__ = type #新式类 class Person: #创建类 def __i ...

  3. CentOS终端界面登入Linux

    上述图片中,前两行为CentOS的版本信息,其内容来自于/etc/issue这个档案中. 后三行:www login:其中www表示主机名(设主机名为www.vbird.tsal),主机名显示通常只取 ...

  4. 【python】 web开发入门

    进入Web开发 现在你完成了Python忍者训练,准备深入Ptyhon的Web开发,但现在的问题是有很多的框架,从中选择最好的框架非常困难,但从初学者的角度出发,Flask基本Web框架将非常适合We ...

  5. iframe 加form提交数据

    <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8&quo ...

  6. 尚硅谷redis学习1-NOSQL简介2

    NoSql数据模型简介 聚合模型:KV键值,BSON 列族: 图形,这里的图形不是指真正的图形,而是关系图 NoSql数据库的四大分类 KV键值:BerkeleyDB,Redis,tair,memca ...

  7. eclipse properties文件插件

      eclipse properties插件 CreateTime--2018年4月22日22:51:34 Author:Marydon 下载地址:properties文件插件.rar 1.将plug ...

  8. 计算机网络【六】:传输层-TCP概述 【转】

    转自:http://blog.chinaunix.net/uid-26275986-id-4109209.html 根据TCP/IP协议的分层结构,网络层之上是传输层,从层次结构上来看,传输层位于网络 ...

  9. error C2011&colon; &OpenCurlyDoubleQuote;Picture”&colon;&OpenCurlyDoubleQuote;struct”类型重定义

    今天引用外来库时出现问题,也许是版本问题. 错误如下: .....\oursun\cincludes\quickdraw.h(309): error C2011: “Picture”:“struct” ...

  10. &ast;&ast;&ast;jQuery使用总结(原创)

    Q: jquery选择器为变量时是怎么办 A: 一个变量我知道可以这样写:$("#"+id) Q: 如何清除单选框的checked属性 A: $("input[type= ...