今天我們來聊一聊另一種博弈--尼姆博弈，這一種博弈可以說是巴什博弈的一種變體，巴什博弈中“石子”的堆數為1堆，而在利姆博弈中“石子”的堆數為n堆，還有在尼姆博弈中取石子的規則也發生了變化，前一種博弈中取石子的數量限定在[1,L]，而后一種取石子的數量可以為任意數（但不能不取，而且還不能超過這一堆石子的總數），同樣也是兩人輪流來取，先取完者獲勝，
下面我們進行一下分析：
(1) 先假設只有兩堆石子，當兩者數量相同的時候，先手必敗(先手從一堆中取a個石子，后手模仿先手從另一堆也取a個，最后一定是先手敗)；當兩者數量不相等時，先手可以通過取石子將兩堆石子變為的數量變為一樣，這樣，后手就面臨必敗態了，
綜合來看的話：當誰面臨“兩堆石子的數量相等”這一狀態時，誰就必敗，
(2) 現在我們將情況推廣到普通狀態，我們先假設存在兩堆石子a=7,b=5，這是兩堆數量不同的石子堆，通過二進制拆分可以將他們化為：111 101,也就是（4+2+1）(4+1),我們現在可以將其視為5堆石子，其中有兩堆數量為4，兩堆數量為1的石子，也就是說，誰面臨這種情況，誰就必敗，而最后一堆誰將它一次性全部拿走，誰就是贏家，而通過二進制拆分可以將兩堆數量分別為4、1的石堆歸零不計，而通過異或這一操作正好可以達到這一要求，
由上得到結論：對每一堆石子的數量進行異或，最終的值為0時(尼姆和)，先手必敗，反之，先手必勝，
典型例題：
Matches Game
題意：n堆石子，兩個人輪流取，先取完者獲勝，
題解：尼姆博弈的模板，直接套用，
代碼：
#include<iostream> #include<algorithm> #define ll long long using namespace std; int main() { ll n,t; while(cin>>n) { ll sum=0; cin>>sum; for(int i=1; i<n; i++) { cin>>t; sum=sum^t; } if(sum==0) cout<<"No"<<endl; else cout<<"Yes"<<endl; } return 0; }
相似題目推薦 ：HDU - 2176 HDU-1850
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30653.html
標籤：C++
上一篇：運算式·運算式樹·運算式求值
下一篇：前綴和