(反NIM)
2024-08-29 14:13:34
题目大意是和普通的NIM游戏一样,但是却是取到最后一个是输的,天真的以为就是反过来,其实并不是这样的
结论
先手必胜的条件为
①:所有堆的石子数均=1,且有偶数堆。
②:至少有一个堆的石子数>1,且石子堆的异或和≠0。
证明
一、当所有堆的石子数均为1时
(1):石子异或和(t)=0,即有偶数堆。此时显然先手必胜。
(2):t≠0,即有奇数堆。此时显然先手必败。
二、当有一堆的石子数>1时,显然t≠0
(1):总共有奇数堆石子,此时把>1的那堆取至1个石子,此时便转化为一.(2),先手必胜。
(2):总共有偶数堆石子,此时把>1的那堆取完,同样转化为一.(2),先手必胜。
三、当有两堆及以上的石子数>1时
(1):t=0,那么可能转化为以下两个子状态:
①:至少两堆及以上的石子数>1且t≠0,即转为三.(2)。
②:至少一堆石子数>1,由二可知此时必胜。
(2):t≠0,根据Nim游戏的证明,可以得到总有一种方法转化为三.(1)状态。
观察三我们发现,三.(2)能把三.(1)扔给对面,而对面只能扔给你三.(2)或必胜态。所以当三.(2)时先手必胜。综上,所有堆的石子数均=1且t=0/至少有一个堆的石子数>1且t≠0时,先手必胜。
参考HDU2509
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int main()
{
int ts;//确定是T态还是S态
int n;
int i,j;
int m[];
int Nuheap;//充裕堆的个数
while(scanf("%d",&n)!=EOF)
{
Nuheap=;
ts=;
for(i=;i<=n;i++)
{
scanf("%d",&m[i]);
if(m[i]>=)
Nuheap++;
ts^=m[i];
}
if((ts==&&Nuheap>=)||(ts!=&&Nuheap==)) //我们知道 如果当前是T2态,那么只能转变成S1或者S2态,此时对手应用正确的方法必胜,所以这个是必败点,同理S0态也是必败点;
{
printf("No\n");
}
else
{
printf("Yes\n");
}
}
return ;
}
最新文章
- BZOJ 3626: [LNOI2014]LCA [树链剖分 离线|主席树]
- 实验环境里新创建成功的web application却在浏览器中返回404错误
- HTML5 canvas globalCompositeOperation绘图类型讲解
- 转——使用Axure制作App原型应该怎样设置尺寸?
- ubuntu中一些软件的命令安装及设置
- 多系统通讯-DotNetMQ
- MSSQL的编译和执行过程
- Chrome浏览器查看cookie
- 利用ffmpeg将H264解码为RGB
- C# 文件上传(可以多文件上传)
- 闲聊DOS命令
- windows下ruby中显示中文的3种方法
- 【Linux】常用命令,持续更新
- Android Studio 合并分支代码到主干的操作总结
- Hadoop的启动和停止说明
- kaldi的TIMIT实例一
- vue2.0中使用sass
- Nginx中防盗链(下载防盗链和图片防盗链)及图片访问地址操作记录
- Spring的AOP配置文件和注解实例解析
- 2.2.11同步synchronized方法无限等待与解决
热门文章
- TYVJ 1094 矩形分割
- Java如何调用dll
- TFS自定义开发中的反射应用
- Java学习路线-知乎
- 【Java】Java程序员面试宝典(第三版)第5章----Java程序设计基本概念
- tar压缩解压缩
- require用法及源码解析
- SpringSecurity04 利用JPA和SpringSecurity实现前后端分离的认证和授权
- 报错:org.springframework.dao.InvalidDataAccessApiUsageException: Executing an update/delete query; nested exception is javax.persistence.TransactionRequiredException: Executing an update/delete query
- 积累遇到过的linux终端操作指令