BZOJ 1022 SHOI2008 小约翰的游戏John 博弈论

BZOJ 1022 SHOI2008 小约翰的游戏John 博弈论

大家好,又见面了,我是全栈君。

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

首先状态1:假设全部的堆都是1,那么堆数为偶先手必胜,否则先手必败

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

若先手拿走一堆,那么后手能够选择将还有一堆留下1个或者全拿走,使这两堆终于仅仅剩1个或0个;

若先手将一堆拿剩一个,那么后手能够选择将还有一堆留下一个让先手拿或全拿走,使这两堆终于仅仅剩1个或0个;

若先手将一堆拿走一部分。那么后手能够将还有一堆相同拿走一部分,然后同上

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

※鉴于本人过于沙茶,以上内容仅存在參考价值。无法证明正确性,欢迎指正

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

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

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
bool Calculate()
{
	int i,x,xor_sum=0;
	bool flag=1;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(x^1) flag=0;
		xor_sum^=x;
	}
	if(flag)
		return !xor_sum;
	else
		return xor_sum;
}
int main()
{
	int T,i;
	for(cin>>T;T;T--)
	{
		if( Calculate() )
			puts("John");
		else
			puts("Brother");
	}
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115489.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • BigDecimal.setScale用法总结(固定精度)

    BigDecimal.setScale用法总结(固定精度)BigDecimal.setScale(intnewScale,introundingMode)newScale:保留newScale位小数roundingMode:舍去规则(0<=roundingMode<=7)一、BigDecimal.ROUND_DOWNBigDecimalnum=newBigDecimal(“3.16159”);//…

    2022年10月20日
  • 股票历史数据库(腾讯股票历史数据接口)

    歪枣网财经数据下载接口集合,百度搜索歪枣网官网序号 名称 接口描述 数据字段 更新日期 操作0 A股列表 沪深京A股基本信息 code股票代码name股票名称stype股票类型,1:深证股票,2:上证股票,3:北证股票,4:港股hsgt沪深港通,1:沪股通:2:深股通、3:港股通(沪)、4:港股通(深)、5:港股通(沪+深)bk所属板块,个股包括主板、创业板、科创板cfg成分股,该板块的成分股roeROEzgb总股本(股)ltgb流通股本(股)ltsz流通市值(元)

  • phpfpm配置 php中的坑

    phpfpm配置 php中的坑

    2021年10月10日
  • oracle截取字符添加数据库,oracle截取字符串前几位的方法_数据库[通俗易懂]

    oracle截取字符添加数据库,oracle截取字符串前几位的方法_数据库[通俗易懂]数据库关系的6个性质_数据库数据库关系的6个性质:1、每一列中的分量为同一类型的数据,来自同一个域;2、不同的列可出自同一个域;3、列的次序可以任意交换;4、任意两个元组不能完全相同;5、行的次序可以任意交换;6、每一个分量都必须是不可分的数据库。oracle截取字符串前几位的方法Oracle提前某数据的前几位用substr函数。如test表中数据如下:现要提取dept字段中的前两位,可用如下…

    2022年10月22日
  • tcp rst报文_TCP报文格式

    tcp rst报文_TCP报文格式RESET报文的接收和检查处理。客户端握手阶段对于TCP客户端,在发送完SYN报文之后,如果接收到的回复报文同时设置了ACK和RST标志,在检查完ACK的合法性之后,处理RST标志,关闭套接口。对于ACK确认序号,其应当大于第一个未确认序号(snd_una),并且,确认序号不应大于未发送数据的序号(snd_nxt)。通常情况下ACK确认序号应当等于snd_una加一(SYN占用一个序号),但是,如果SYN报文中带有数据(例如:TFO),ACK确认序号会更大。以上情况向对端发送reset报文,但是,如果

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号