怀化网站优化公司推荐,郑州大搜索网站,网站制作西安企业网站制作,短视频素材下载网站 免费#xff08;一#xff09;一堆取石头
背景#xff1a; 在博弈论中#xff0c;有一种称为Nim游戏的经典问题#xff0c;它涉及到取石子的问题#xff0c;其中有许多变种。Nim游戏是一种零和博弈#xff0c;即两名玩家交替行动#xff0c;每次只能从一堆物品中取走一定数…一一堆取石头
背景 在博弈论中有一种称为Nim游戏的经典问题它涉及到取石子的问题其中有许多变种。Nim游戏是一种零和博弈即两名玩家交替行动每次只能从一堆物品中取走一定数量的物品无法分割物品。 题目中描述的场景是这样的 有n个石头两名玩家轮流进行操作每次可以从石头堆中取走1到m个石头其中m是一个固定的正整数。玩家可以根据自己的策略选择取多少个石头目标是使自己取得最后一个石头。 题解思路
令 ans n%m1为什么这样令后面会讲解
判断是否存在先手必胜策略这一问题即可一开始检验石子堆中的ans是否为0当ans为0时你面对的是ans0的局面你的任意操作都会使得当前ans不为0你的对手又足够聪明那你每执行一步他都会再次把ans0的局面返还给你那你最后必输
当ans不为0时你先手你又足够聪明你每次执行后都可以把ans0的局面留给对手最后你必胜。 为什么令 ans n%m1
当先手玩家取石头使石头个数 n 能够被m1整除时后手玩家所要面临的情况是无论怎么取都不可能取完石头。如果先手玩家能够保证后手玩家一直面临石头个数 n 能够被m1整除那么最后一次后手玩家面临的情况是石头的个数是 m1所以后手玩家无论怎么取都不可能取完石头最后只能是先手玩家将石头取完。
所以对于自己来说取胜的条件是自己面临的石头个数情况是 n%m1! 0然后自己取石头使石头个数能够被m1整数。 二多堆取石头
这里我转载一位大佬的博客博弈论石子游戏——nim 游戏_[模板]nim游戏_Wu_L7的博客-CSDN博客
题目描述 地上有 n 堆石子每堆石子数量小于 10^4每人每次可从任意一堆石子里取出任意多枚石子扔掉可以取完不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手且告诉你这 n 堆石子的数量他想知道是否存在先手必胜的策略。 题目思路
必胜策略即当你执行最后一步后你的对手已无石子可取他必败你必胜。最后局面是地上各个石子堆已无石子可取假设 ai 代表第 i 个石子堆中的石子数则 ai 0i ≤ n。即可得a1^a2^a3^……^an0^表示异或令ans a1^a2^a3^……^an要想必胜说明最后的局面一定是ans0那我只需要满足我每次操作完使得ans0即可那么每次留给对手的局面都是ans0怎么实现后面讲并且石子的初始数确定每次都取走一部分的石子在有限的步数内肯定会取完当执行到最后一步ans0时恰好最后的石子被你取完你必胜。
那么判断是否存在先手必胜策略这一问题即可一开始检验石子堆中的ans是否为0当ans为0时你面对的是ans0的局面你的任意操作都会使得当前ans不为0你的对手又足够聪明那你每执行一步他都会再次把ans0的局面返还给你那你最后必输当ans不为0时你先手你又足够聪明你每次执行后都可以把ans0的局面留给对手最后你必胜。
小tip
为什么每次操作之后都会使得ans0转化成ans ! 0并且足够聪明的你执行完一次操作之后又能把ans ! 0变成ans0
1、ans0执行一次操作之后为什么会转化为ans ! 0
异或即是把每个ai中转化为二进制的形式再对每一个位置的所有0和1进行异或操作举个例子5^360101^00110110。而ans a1^a2^a3^……^an每次只能对一个石子堆操作即每次操作只会影响aii ≤ n中的一个假设是对ak进行操作则没操作前的ak^其它ai的异或0说明其它ai的异或没操作前的ak因为两个相同的数相异或结果才为0现在对ak进行操作则ak的值肯定会变化其二进制形式也随之变化则操作后的ak!其它ai的异或所以操作后的ak^其它ai的异或! 0则ans ! 0。
2、为什么足够聪明的你执行完一次操作之后又能把ans ! 0变成ans0
ans a1^a2^a3^……^an是各个位置多个0和1的异或因为ans ! 0说明一定有个别位置中1的个数为奇数则我们可以把该位置上的1去掉一个或增加一个即取走一些石头使之为偶数则ans0。例如10^5151010^01011111这是最经典的了我们可以从10中拿走5则5^50所以想说明的是总有办法使ans0。
注
这里有个简单的取石头个数的技巧异或的简单计算方法
例如7和14的异或
7的二进制序列为 0111
14的二进制序列为1110
则异或结果是1001 9
简便计算
7可以写成2的倍数之和421
14可以写成2的倍数之和8420
然后约去两部分相同的部分7剩余一个114剩余一个8再将剩余的数相加其结果就是异或结果9。 本次内容到此结束了如果你觉得这篇博客对你有帮助的话 希望你能够给我点个赞鼓励一下我。感谢感谢…… 参考资料 【尼姆游戏学霸就是这样欺负人的】https://www.bilibili.com/video/BV1ek4y1q7JD?vd_source564abed1c36a31978eb9de7cdc6668d2 博客原文链接https://blog.csdn.net/Wu_L7/article/details/126266519 同时感谢上面两位创作者的输出让我受益匪浅。
