BZOJ1022:[SHOI2008]小约翰的游戏John(博弈论)
2024-08-24 09:24:07
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
3
3 5 1
1
1
Sample Output
John
Brother
Brother
Solution
$Anti-SG$游戏先手必胜条件:
(1)所有堆的石子数都为1且游戏的$SG$值为$0$。
(2)有些堆的石子数大于$1$且游戏的$SG$值不为$0$。
Code
#include<iostream>
#include<cstdio>
using namespace std; int T,n,x,ans,flag; int main()
{
scanf("%d",&T);
while (T--)
{
ans=,flag=;
scanf("%d",&n);
for (int i=; i<=n; ++i)
scanf("%d",&x), ans^=x, flag|=(x>);
if((bool)ans^flag) puts("Brother");
else puts("John");
}
}
最新文章
- AC自动机专题
- 40多个纯CSS绘制的图形
- 【javascript激增的思考01】模块化编程
- hdu3437 划分树 区间内小于第K大的值得和
- Java 中常用缓存Cache机制的实现《二》
- SCN试验之二 checkpoin scn 与数据库scn的关系
- JDBC学习总结(五)
- 转:更新Android SDK之后Eclipse提示ADT版本过低的一个简易解决办法
- Avoid The Lakes--poj3620
- SpringCache与redis集成,优雅的缓存解决方案
- C语言---字符数组
- SQL Server Agent Job 多服务器管理
- ASP.NET中直接用C# 动态修改CSS样式
- 【easy】695. Max Area of Island
- httping使用
- Python 实现红绿灯
- 【PHP】解析PHP中的错误和异常处理
- SRP周记_20190418
- (一)什么是webservice?
- TCP/IP协议(2):各层网络设备
热门文章
- Node.js学习笔记(八) --- Node.js的路由模块封装
- 招新系统(jsp+servlet,实现简略前端网页注册登录+后台增删改查,分学生和管理员,Java语言,mysql数据库连接,tomcat服务器)
- 【原】使用Builder模式替代构造参数传参
- Form表单和里边的小部件
- O(∩_∩)O~~
- java网络编程(TCP详解)
- Collection FrameWork
- overload与override的区别
- ios虚拟机安装(一)
- Pwn Heap With Tcache