1022: [SHOI2008]小约翰的游戏John【Nim博弈,新生必做的水题】

1022: [SHOI2008]小约翰的游戏John

Time Limit: 1 Sec  Memory Limit: 162 MB

Submit: 2709  Solved: 1726

[Submit][Status][Discuss]

Description

  小约翰经常和他的哥哥玩一个非常有趣的游戏:桌子上有n堆石子,小约翰和他的哥哥轮流取石子,每个人取 的时候,可以随意选择一堆石子,在这堆石子中取走任意多的石子,但不能一粒石子也不取,我们规定取到最后一 粒石子的人算输。小约翰相当固执,他坚持认为先取的人有很大的优势,所以他总是先取石子,而他的哥哥就聪明 多了,他从来没有在游戏中犯过错误。小约翰一怒之前请你来做他的参谋。自然,你应该先写一个程序,预测一下 谁将获得游戏的胜利。

Input

  本题的输入由多组数据组成第一行包括一个整数T,表示输入总共有T组数据(T≤500)。每组数据的第一行包 括一个整数N(N≤50),表示共有N堆石子,接下来有N个不超过5000的整数,分别表示每堆石子的数目。

Output

  每组数据的输出占一行,每行输出一个单词。如果约翰能赢得比赛,则输出“John”,否则输出“Brother” ,请注意单词的大小写。

Sample Input

2 3 3 5 1 1 1

Sample Output

John Brother

HINT

Source

Seerc2007

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1022

分析:

题目大意:反Nim游戏,即取走最后一个的人输

首先状态1:如果所有的堆都是1,那么堆数为偶先手必胜,否则先手必败

然后状态2:如果有两个堆数量相同且不为1,那么后手拥有控场能力,即:

若先手拿走一堆,那么后手可以选择将另一堆留下1个或者全拿走,使这两堆最终只剩1个或0个;

若先手将一堆拿剩一个,那么后手可以选择将另一堆留下一个让先手拿或全拿走,使这两堆最终只剩1个或0个;

若先手将一堆拿走一部分,那么后手可以将另一堆同样拿走一部分,然后同上

状态3:若Xor!=0 那么先手可以先拿走一部分让Xor=0 然后同状态2先手必胜 否则先手必败

于是若所有堆全是1 Xor==0先手必胜 否则后手必胜

若有堆不是1 Xor==0后手必胜 否则先手必胜

下面给出AC代码:

 1 #include <stdio.h>
 2 int T,n,x;
 3 int main()
 4 {
 5     while(scanf("%d",&T)!=EOF)
 6     {
 7         while(T--)
 8         {
 9             int flag=0,sum=0;
10             scanf("%d",&n);
11             for(int i=1;i<=n;i++)
12             {
13                 scanf("%d",&x);
14                 sum^=x;
15                 if(x!=1)
16                     flag=1;
17             }
18             if((sum==0&&flag==0)||(sum!=0&&flag==1))
19                 printf("John\n");
20             else 
21                 printf("Brother\n");
22         }
23     }
24     return 0;
25 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Aloys的开发之路

OOAD与UML笔记

UML基础介绍 1.UML的定义 统一建模语言(UML)是一种图形化的语言,它可以帮助我们在OOAD过程中标识元素、构建模块、分析过程并可通过文档说明系统中的重...

1978
来自专栏飞总聊IT

大数据那些事(10):李逵麻子,李鬼坑人--BigTable的数据模型

今天我们回归技术路线,讲讲Google三驾马车里的BigTable。以前有个说法叫做麻子不叫麻子,叫坑人。取其原意是满脸是坑的人,谐音表示人被坑了。我们知道水浒...

4127
来自专栏ACM算法日常

为什么vjudge上他人公开的代码要以图片形式显示?

vjudge用图片来显示代码,应该是为了避免抄袭。在较低水平的oier中,已经有交别人的代码来通过题目的风气。举个例子,洛谷上抄袭代码情况极其严重,而u...

1052
来自专栏Crossin的编程教室

用 Python 跟自己下棋

今天,李世乭终于在与 AlphaGo 的人机大战中扳回一局。但计算机 AI 可以在围棋上战胜人类顶尖棋手的时代已经到来。可以预见,人工智能和机器人将会在更多领域...

5799
来自专栏大数据挖掘DT机器学习

Python NLTK自然语言处理:词干、词形与MaxMatch算法

CSDN:白马负金羁 自然语言处理是计算机科学领域与人工智能领域中的一个重要方向。自然语言工具箱(NLTK,Natural Language Toolkit)...

5105
来自专栏斑斓

MongoDB的数据建模

MongoDB是一种面向Document的NoSQL数据库,如果我们还是按照RDB的方式来思考MongoDB的数据建模,则不能有效地利用MongoDB的优势;然...

3406
来自专栏点滴积累

ANSJ中文分词使用方法

一、前言 之前做solr索引的时候就使用了ANSJ进行中文分词,用着挺好,然而当时没有写博客记录的习惯。最近又尝试了好几种JAVA下的中文分词库,个人感觉还是A...

4429
来自专栏程序人生

谈谈状态机

题记:上周做 BBL 里讲了我们 Tubi TV 内部做 DSL 的一些简单实践,大家反馈不错。有同事建议我给大家先补补 FSM,之后再进阶 CFG,可能会更顺...

3537
来自专栏程序猿

【学生管理系统C语言】没有用数据库,正在学习C语言的看看吧

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> # defin...

49411
来自专栏逸鹏说道

借网站日记分析~普及一下Pandas基础

对网站日记分析其实比较常见,今天模拟演示一下一些应用场景,也顺便说说Pandas,图示部分也简单分析了下

613

扫码关注云+社区

领取腾讯云代金券