取石子（二）巴仕博弈+尼姆博弈

缺乏、安全感 2023-10-11 09:33 61阅读 0赞

巴什博弈：

问题：给你一堆石子共n个，你最多只能拿走m个，问什么情况下先手胜

结论：当n%(m+1)==0的时候先手输，反之则赢

简而言之，谁先面对k\*(m+1)(k是任意值)，谁就输

[题目][Link 1]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //巴什博弈
     2 //谁先面对m+1（m是最多拿多少石子）那谁就输
     3 //因为先手最多拿m个，而后收就可以将其补到m+1，所以后手一定赢
     4 #include<stdio.h>
     5 #include<string.h>
     6 #include<iostream>
     7 #include<algorithm>
     8 using namespace std;
     9 const int maxn=1e5+10;
    10 int main()
    11 {
    12     int t;
    13     scanf("%d",&t);
    14     while(t--)
    15     {
    16         int n,m;
    17         scanf("%d%d",&n,&m);
    18         //printf("%d\n",n%(m+1));
    19         if(n%(m+1))
    20             printf("Win\n");
    21         else printf("Lose\n");
    22     }
    23     return 0;
    24 }

尼姆博弈：

问题：给你n堆石子，每次只能在一堆中完成取石子任务，最少取一个，最多不限

结论：定义一个变量初始化为0，让这个变量对每一堆石子的数量都异或一下，如果结果是0，先手就输，否则就赢（就是谁面对异或值是0，谁就输了）

怎么走棋：我们可以每次走棋都考虑一下让他们全部值异或起来变成0

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <cstdio>
     2 #include <cmath>
     3 #include <iostream>
     4 using namespace std;
     5 int main()
     6 {
     7     int n,ans,temp;
     8     while(cin>>n)
     9     {
    10         temp=0;
    11         for(int i=0;i<n;i++)
    12         {
    13             cin>>ans;
    14             temp^=ans;
    15         }
    16         if(temp==0)  cout<<"后手必胜"<<endl;
    17         else cout<<"先手必胜"<<endl;
    18     }
    19     return 0;
    20 }
    21 
    22

本题------------------------------------------------------------------------------------------------------

[题目][Link 2]

题意：

给你N堆石子，你只能一次向一堆石子进行去取石子操作，没堆石子有n个，你每次最多取m个

错解：

原来以为这一道题就是巴什博弈的升级版

以为先找出来n%(m+1)!=0的石子堆的个数sum，然后在判断如果这个sum是奇数，那么先手赢，否则先手输

根据巴什博弈谁先面对k\*(m+1)谁就输了，那么n%(m+1)!=0的只要被操作一下，就会转化为n%(m+1)==0这种情况

但是！

如果 每堆数量为1   2   3，且m值极大的情况，此时sum为3，是一个奇数，但是却不是先手赢

比先取第三堆的3，另一个人取第二堆的1，那么还有两堆都是1，这样先手就输了

多堆是不适合巴什博弈的，他不一定会一下就把剩下的拿走完，还要看其他堆石子个数来决定

正解：

巴什博弈结论是谁先面对k\*(m+1)那么谁就输，意思就是最后一个取石子的还是先手，那么就可以说k\*(m+1)是不改变题目性质的，那么可以不用管 k\*(m+1)

这样的话相当于每一堆石子的数量都对(m+1)取余，这样的话每一堆中石子数量，最大为m，那么不就符合尼姆博弈最少取一个，最多取全部的宗旨了吗！

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //巴什博弈变形
     2 //给你了n堆，你可以找出来每一堆中不是n%（m+1）！=0的个数
     3 //然后再判断这个个数是奇数还是偶数不就可以了
     4 #include<stdio.h>
     5 #include<string.h>
     6 #include<iostream>
     7 #include<algorithm>
     8 using namespace std;
     9 typedef long long ll;
    10 const int maxn=1e5+10;
    11 int main()
    12 {
    13     ll t;
    14     scanf("%lld",&t);
    15     while(t)
    16     {
    17         t-=1;
    18         ll N,n,m,sum=0;
    19         scanf("%lld",&N);
    20         while(N--)
    21         {
    22             scanf("%lld%lld",&n,&m);
    23             sum=sum^(n%(m+1));
    24         }
    25         if(sum)
    26             printf("Win\n");
    27         else printf("Lose\n");
    28     }
    29     return 0;
    30 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11327874.html

[Link 1]: http://192.168.0.147/problem/23
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif
[Link 2]: http://192.168.0.147/problem/135