巴什博弈：
问题：给你一堆石子共n个，你最多只能拿走m个，问什么情况下先手胜
结论：当n%(m+1)==0的时候先手输，反之则赢
简而言之，谁先面对k*(m+1)(k是任意值)，谁就输
代码：
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%(m+1)); 19 if(n%(m+1)) 20 printf("Win "); 21 else printf("Lose "); 22 } 23 return 0; 24 }
尼姆博弈：
问题：给你n堆石子，每次只能在一堆中完成取石子任务，最少取一个，最多不限
结论：定义一个变量初始化为0，让这个变量对每一堆石子的数量都异或一下，如果结果是0，先手就输，否则就赢（就是谁面对异或值是0，谁就输了）
怎么走棋：我们可以每次走棋都考虑一下让他们全部值异或起来变成0
代码：
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
本题------------------------------------------------------------------------------------------------------
题意：
给你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，那么不就符合尼姆博弈最少取一个，最多取全部的宗旨了吗！
代码：
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 "); 27 else printf("Lose "); 28 } 29 return 0; 30 }