HDU3032 Nim or not Nim?(Lasker’s Nim游戏)
Nim or not Nim?
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3759 Accepted Submission(s): 1937
Nim is usually played as a misere game, in which the player to take the last object loses. Nim can also be played as a normal play game, which means that the person who makes the last move (i.e., who takes the last object) wins. This is called normal play because most games follow this convention, even though Nim usually does not.
Alice and Bob is tired of playing Nim under the standard rule, so they make a difference by also allowing the player to separate one of the heaps into two smaller ones. That is, each turn the player may either remove any number of objects from a heap or separate a heap into two smaller ones, and the one who takes the last object wins.
3
2 2 3
2
3 3
Bob
题解:
每一轮允许两会中操作之一:①从一堆石子中取走任意多个②将一堆数量不少于2的石子分成都不为空的两堆。
这个问题可以用SG函数来解决。首先,操作①其实和Nim游戏没什么区别,对于一个石子数为k的点来说,后继可以为0…k-1。而操作②实际上是把一个游戏分成了两个游戏。根据游戏的和的概念,这两个游戏的和应该为两个子游戏的SG函数值的异或。而求某一个点的SG函数要利用它的后继,它的后继就应该为当前局面能产生的所有单一游戏,以及当前局面所有能分成的多个单一游戏的游戏的和。
比如说,状态3的后继有:0、1、2、(1,2),他们的SG值分别为0、1、2、3,所以sg(3) = 4。
那么这样,我们就能用SG函数解决这个问题。
但是,如果数据范围非常大的时候SG函数就不能用了,通过打表可以发现一个更优美的结论:
if(x%4==0) sg[x]=x-1;
if(x%4==1||x%4==2) sg[x]=x;
if(x%4==3) sg[x] = x+1。
#include<bits/stdc++.h>
using namespace std;
#define N 1000000
int T,n,x,ans; int get_sg(int x)
{
if(x%==) return x-;
else if(x%==||x%==) return x;
else if(x%==) return x+;
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);ans=;
for(int i=;i<=n;++i)
{
scanf("%d",&x);
ans^=get_sg(x);
}
if(ans) puts("Alice");
else puts("Bob");
}
return ;
}
最新文章
- 个人作业week3——代码复审
- 妈妈再也不担心我的编码问题了。中文编码融汇贯通,windows,django,python,java,html 【转】
- Ext.Net 学习随笔 001 安装Ext.Net
- Maven实战(六)依赖
- kindeditor编辑器
- Linux基本命令之逻辑测试一
- Ajax 表单验证 实现代码
- 基于visual Studio2013解决C语言竞赛题之1053洗牌
- thinkphp中fetch渲染模板的处理
- 如何开发自己的搜索帝国之ES图形化Kibana安装与使用
- 使用 ServiceAnt 更好地解耦你的程序
- Spring boot的第一个demo
- Vue-router重修01
- 六、latex中的特殊字符
- WarShall算法
- LeetCode(111):二叉树的最小深度
- IIS下https配置及安全整改
- 《全栈性能Jmeter》-4JMeter脚本开发
- poj-2514-模拟
- HDU 2164 Rock, Paper, or Scissors?
热门文章
- 详解Vue 方法与事件处理器
- 创建基于OData的Web API - Knowledge Builder API, Part III:Write Model
- [LC]66题 Plus One (加1)
- 资深架构师Sum的故事:(Mysql)InnoDB下,存储过程中事务的处理
- hdu 1285 确定比赛名次 (topsort)
- Web Scraper 翻页——利用 Link 选择器翻页 | 简易数据分析 14
- 【NHOI2018】拆除桥墩
- 【NHOI2018】字符串变换
- linux [CTRL]+c与[CTRL]+d
- day 17 re模块 正则表达式