菜单

ACM暑期培训题解 HDU-2176 & HDU-1850

八月 2, 2018 - 算法
ACM暑期培训题解 HDU-2176 & HDU-1850

复杂的Nim博弈问题

前言

两道稍微复杂一些的Nim博弈问题,用到了非常神奇的异或方式。

HDU-2176 取(m堆)石子问题

题目描述:

m堆石子,两人轮流取.只能在1堆中取.取完者胜.先取者负输出No.先取者胜输出Yes,然后输出怎样取子.例如5堆 5,7,8,9,10先取者胜,先取者第1次取时可以从有8个的那一堆取走7个剩下1个,也可以从有9个的中那一堆取走9个剩下0个,也可以从有10个的中那一堆取走7个剩下3个.

Input

输入有多组.每组第1行是m,m<=200000. 后面m个非零正整数.m=0退出.

Output

先取者负输出No.先取者胜输出Yes,然后输出先取者第1次取子的所有方法.如果从有a个石子的堆中取若干个后剩下b个后会胜就输出a b.参看Sample Output.

Sample Input

2
45 45
3
3 6 9
5
5 7 8 9 10
0

Sample Output

No
Yes
9 5
Yes
8 1
9 0
10 3

题目分析

这种从m堆里去石子的题目,可以拆分成一个一个的单独的Nim博奕,先说结论,只要满足每一堆的异或为0,就是先手必输,后手必胜,异或不为0,则是先手获胜。
这里给出分析过程:
对于某个局面(a1,a2,…,an),若a1^ a2 ^ …^ an不为0,一定存在某个合法的移动,将ai改变成ai’后满足a1^ a2^ …^ ai’^ …^ an=0。不妨设a1^ a2^ …^ an=k,则一定存在某个ai,它的二进制表示在k的最高位上是1。因为只有这样,才能使k的最高位为1。而且我们知道ai^ k < ai,所以此时我们ai^ k去替换ai,此时原式就变成了a1^ a2^ … ^ ai^ … ^ an^ k = k ^ k = 0。
这个操作说明了我们可以通过一次操作使任何一个异或不为0的序列变成异或为0的序列,而后手的操作一定会打破这种情况,如此往复会得到全0的结果,也就是先手会获得胜利。
类似的,如果开始情况下异或为0, 则先手会打破这种情况,后手就会获得胜利。
至于题目中要求的操作,我们可以通过什么提到的方式来实现,即求出所有比ai小的ai^ k,也就是替换后的结果。

代码实现


HDU-1850 Being a Good Boy in Spring Festival

题目描述:

一年在外 父母时刻牵挂
春节回家 你能做几天好孩子吗
寒假里尝试做做下面的事情吧

陪妈妈逛一次菜场
悄悄给爸爸买个小礼物
主动地 强烈地 要求洗一次碗
某一天早起 给爸妈用心地做回早餐

如果愿意 你还可以和爸妈说
咱们玩个小游戏吧 ACM课上学的呢~

下面是一个二人小游戏:桌子上有M堆扑克牌;每堆牌的数量分别为Ni(i=1…M);两人轮流进行;每走一步可以任意选择一堆并取走其中的任意张牌;桌子上的扑克全部取光,则游戏结束;最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负,我只想问大家:
——“先手的人如果想赢,第一步有几种选择呢?”

Input

输入数据包含多个测试用例,每个测试用例占2行,首先一行包含一个整数M(1<M<=100),表示扑克牌的堆数,紧接着一行包含M个整数Ni(1<=Ni<=1000000,i=1…M),分别表示M堆扑克的数量。M为0则表示输入数据的结束。

Output

如果先手的人能赢,请输出他第一步可行的方案数,否则请输出0,每个实例的输出占一行。

Sample Input

3
5 7 9
0

Sample Output

1

题目分析

本质上来讲这一题和上一题没有什么区别,只是把上一题的情况放在了具体的环境中,最后的输出由具体方案变成了方案数量,解题思路和上一题基本一样,每一堆的牌数求异或,若为0则输出0,若不为0则在后面求方案的时候计数,最后输出即可。

代码实现

总结

这两道题目就不算简单了,参考了一些资料才搞懂里面的道理。

标签:, ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注