博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ 1022 SHOI2008 小约翰的游戏John 博弈论
阅读量:4946 次
发布时间:2019-06-11

本文共 837 字,大约阅读时间需要 2 分钟。

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

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

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

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

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

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

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

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

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

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

#include
#include
#include
#include
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"); }}

转载于:https://www.cnblogs.com/yxwkf/p/5349943.html

你可能感兴趣的文章
Ubuntu安装python虚拟环境以及apt-get和pip源更换
查看>>
ORG 07C00H的意思
查看>>
BZOJ1036;[ZJOI2008]树的统计
查看>>
激活码
查看>>
php 获取优酷视频的真实地址(2014.6月新算法)
查看>>
SQL数据库知识二(Day 25)
查看>>
WPF 入门笔记之事件
查看>>
Win7 64位硬盘安装Ubuntu 64位的细微配置
查看>>
keystore和truststore
查看>>
【Luogu】P3396哈希冲突(根号算法)
查看>>
ready与onload的性能
查看>>
matlab(5) : 求得θ值后用模型来预测 / 计算模型的精度
查看>>
第4章 类与对象 类和对象
查看>>
macro 标签,和静态文件,以及templates
查看>>
Kafka简介
查看>>
丶动态获取系统当前时间
查看>>
关于前端 的自适应
查看>>
解决IIS服务和用户上传的文件分别部署在不同的电脑上时,解决权限的问题
查看>>
自定义CCNode
查看>>
纪中集训 Day 6
查看>>