BZOJ.1022.[SHOI2008]小约翰的游戏John(博弈论 Anti-Nim)
2024-08-26 01:38:08
**Anti-Nim游戏: **
先手必胜当且仅当:
1.所有堆的石子数为1,且异或和为0
2.至少有一堆石子数>1,且异或和不为0
简要证明:
对于1:若异或和为1,则有奇数堆;异或和为0,则有偶数堆。比较显然。
对于2:(1)对于只有一堆石子数>1的情况(异或和一定不为0),先手可以操作这堆石子 将场面变为奇数堆个数都为1的石子堆
(2)对于至少有两堆石子数>1的情况:
- 若异或和=0,先手必败
- 若异或和!=0,先手必胜
类似Nim的证明,若异或和=0,则怎样操作都会使异或和!=0;若异或和!=0,则一定有一步能使异或和=0.(NP性质的转换)
这两种状态不断转换,总会在某一时刻变为2.(1)中的状态,即一个必胜态,而这个必胜态是由异或和=0时转移来的。
即异或和=0时一定会在某一时刻转移到一个必胜状态。
#include <cstdio>
#include <cctype>
#define gc() getchar()
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
int t=read(),n,res,a; bool f;
while(t--)
{
n=read(), f=res=0;
while(n--)
a=read(), a>1?f=1:0, res^=a;
puts(f^(res>0)?"Brother":"John");
}
return 0;
}
最新文章
- java8中lambda表达式的应用,以及一些泛型相关
- MySQL数据库权限操作指南
- 解决ASP.NET 自定义报表部署到IIS浏览时出现ASP.NET会话已结束问题
- iOS图片元数据的读写
- cocos2d(CCSprite绑定不规则刚体与精灵一起移动)
- Mybatis源码之Statement处理器SimpleStatementHandler(四)
- BZOJ_3689_异或之_可持久化Trie+堆
- ASP.NET Core中使用GraphQL - 第九章 在GraphQL中处理多对多关系
- Chapter 5 Blood Type——14
- 将文件转成clob添加到Oracle数据库中
- zookeeper注册与发现
- asp.net中的Filter类型其实是被当作单例的
- Linux中找到占用cpu最高的线程
- Nginx拦截指定国家的IP
- 基于VMware Workstation在Windows Server 2008 R2上搭建SQL Server 2012高可用性组(AlwaysOn Group)测试环境(二)
- Spring Batch 介绍
- 【python-字典】判断python字典中key是否存在的
- iOS 远程推送注册的小问题
- Android 使用DDMS查看内存使用情况
- JavaScript验证字符串只能包含数字或者英文字符的代码实例
热门文章
- 【Mysql sql inject】POST方法BASE64编码注入write-up
- DBSCAN密度聚类
- 『转载』hadoop 1.X到2.X的变化
- PNG,JPEG,BMP,JIF图片格式详解及其对比
- Zabbix Agent active批量调整客户端为主动模式监控
- PYTHON-字符编码&;文件处理-练习
- PYTHON-基本数据类型-元祖类型,字典类型,集合类型
- Java 开发环境配置--eclipse工具进行java开发
- 【转】js中的事件委托或是事件代理详解
- python+selenium十三:破解简单的图形验证码