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)


相关推荐

  • Spring Cloud Alibaba基础教程:Nacos配置的加载规则详解[通俗易懂]

    Spring Cloud Alibaba基础教程:Nacos配置的加载规则详解[通俗易懂]Spring Cloud Alibaba基础教程:Nacos配置的加载规则详解

  • 在微型计算机中1mb等于多少字节,1mb等于多少字节「建议收藏」

    在微型计算机中1mb等于多少字节,1mb等于多少字节「建议收藏」1MB等于2^20字节。MB,全称“MByte”,计算机中的一种储存单位。字节是计算机信息技术用于计量存储容量的一种计量单位,作为一个单位来处理的一个二进制数字串,是构成信息的一个小单位。本教程操作环境:windows7系统、DellG3电脑。1MB等于2^20字节。1MB=1024KB=2^20B。1、字节(Byte)是计算机信息技术用于计量存储容量的一种计量单位,作为一个单位来处理的一…

  • 2022idea激活码【2021.10最新】

    (2022idea激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~3YVYA7ZZGQ-eyJsaWNlb…

  • C语言基础知识:函数指针&指针函数(定义格式、作用及用法说明)[通俗易懂]

    C语言基础知识:函数指针&指针函数(定义格式、作用及用法说明)[通俗易懂]版权声明:本文为博主原创文章,未经博主允许不得转载。https://mp.csdn.net/postedit/83150266一、函数指针的实质(还是指针变量)1、函数指针定义格式:类型名 (*函数名)(函数参数列表);int(*pfun)(int,int);2、函数指针的定义、赋值、调用voidfunc1(void)//定义一个函数,以方便下面定义函…

  • mpvue还在维护吗_laravel

    mpvue还在维护吗_laravelmain.js//main.js//将fly实例挂在vue原型上,在然而你和组件中通过this使用flyvarFly=require("flyio/dist/npm/wx")varfly=newFlyfly.config.baseURL=’http://xx.xx.xx.xx:xxxx/api/v3/’//配置请求基地址Vue.prototype.$http=fly/…

  • java mina框架实例_MINA框架简介和一个简单的例子

    基于MINA框架快速开发网络应用程序1.MINA框架简介MINA(MultipurposeInfrastructureforNetworkApplications)是用于开发高性能和高可用性的网络应用程序的基础框架。通过使用MINA框架可以可以省下处理底层I/O和线程并发等复杂工作,开发人员能够把更多的精力投入到业务设计和开发当中。MINA框架的应用比较广泛,应用的开源项目有Apache…

发表回复

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

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