【模板】nim游戏

题目

洛谷P2197nim游戏

题解

假设第i堆石子有ai个。

当所有物品都被取完后,x=0,对手取走最后一个,我方失败。

若x!=0,设x的二进制表示下的最高位的1在第k位,那么至少存在一个ai,它的第k位为1,。显然,对ai有一种取法,使得x=0。

若x=0,任意一种取法都会导致x!=0。

综上,由数学归纳法得:x!=0先手必胜,因为永远可以让对手面对x=0的局面;x=0先手必败,因为永远可以让对手面对x!=0的必胜局面。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月26日 下午8:09

【小白解析】
此题解答看起来异常言简意赅:把所有石堆的石子数混在一起取异或得x(x=a1^a2^…^an),若得出的不是0,即先手必胜。需证明这一点没有必要处处落实在具体的游戏过程中。
先分析x==0的情况:此时不论一个玩家如何操作,必然有与之相对的操作,让被改变的x重归于0——因为异或的对称性保证了一个全部二进制位数为0的数,其每一位的构成一定是偶数数量的1和偶数数量的0——即任何成分都是成对的。因此,一种操作必然有其逆操作,让x由1和0的排列全部变为0。
在这种战略下,若先手者试图改变x==0的局势,后手者一定能将局势改回来——而后手者最后一次操作,一定是将所有石子取完,此时后手必胜。因此,需要保证先手者操作的每一次局势中,x!=0。换句话说,需保证后手者每次操作时,x==0。
而先手者只要有一局能使后手者操作时x==0,即可保证每局都如此。具体操作是:在接过被后手者魔改过的局势后,查找当前x位数最高的1:表示某一堆石子的数量,一定不小于这个位数上的1所对应的2的幂;同时因为异或操作中仅0^1==1,说明仅有这一堆有超过这个数目的石子。因此,只要从这一堆中取走一定数量的石子,使这一堆剩余石子的二进制表示正好与其它堆的异或结果相反,则一定能使x==0。
例:若有3堆石子,数目分别为8,2,1,则x表达为:

1011

此时对8进行操作。除8以外的x为:

0011

此时从8的那一堆中取走5个,使该堆剩余3个,则现在x的表达为:

0011^0011==0000

因为8所对应的1在对高位,对8那一堆进行操作一定能在一部之内让其余低位的所有1归零。