自己黑自己做的網(wǎng)站找相似圖片 識(shí)別
1002.Random Nim Game
詐騙博弈題
題目大意
Nim是一種雙人數(shù)學(xué)策略游戲,玩家輪流從不同的堆中移除棋子。在每一輪游戲中,玩家必須至少取出一個(gè)棋子,并且可以取出任意數(shù)量的棋子,條件是這些棋子都來自同一個(gè)棋子堆。走最后一步棋(即取出最后一塊棋子)的人獲勝。
現(xiàn)在更改游戲規(guī)則,在每個(gè)回合中,棋手必須選擇一個(gè)棋子堆。假設(shè)他選擇的堆包含 x x x 個(gè)棋子,將從 [ 1 , x ] [1,x] [1,x] 中隨機(jī)一個(gè)整數(shù) y y y ,并從堆中移除 y y y 個(gè)棋子
求先手獲勝的概率,答案取模
解題思路
看起來很嚇人的一道題(誰被嚇退了我不說)//
考慮只有一個(gè)堆的情況
若只有 1 1 1 個(gè)棋子,先手必勝
如果有 2 2 2 個(gè)棋子,有 1 2 \dfrac{1}{2} 21? 的概率拿完獲勝,有 1 2 \dfrac{1}{2} 21? 的概率余 1 1 1 失敗,綜合勝率 1 2 \dfrac{1}{2} 21?
? \vdots ?
如果有 x ( x > 1 ) x\ (x>1) x?(x>1) 個(gè)棋子,有 n ? 2 n \dfrac{n-2}{n} nn?2? 的概率轉(zhuǎn)移到 剩余個(gè)數(shù) > 1 >1 >1 的狀態(tài),有 1 n \dfrac{1}{n} n1? 的概率拿完獲勝,有 1 n \dfrac{1}{n} n1? 的概率余 1 1 1 失敗。遞歸得到 x > 1 x>1 x>1 的狀態(tài)下的綜合勝率為 1 2 \dfrac{1}{2} 21?
再考慮多堆的情況
如果所有堆的棋子數(shù)量均為 1 1 1 ,則當(dāng)堆數(shù) n n n 為奇數(shù)時(shí)先手必勝
如果有某堆的數(shù)量多于 1 1 1 個(gè),那么必勝態(tài)將以 1 2 \dfrac{1}{2} 21? 的概率流轉(zhuǎn)
綜上所述,如果所有堆的棋子數(shù)量均為 1 1 1 ,則當(dāng)堆數(shù) n n n 為奇數(shù)時(shí)先手必勝, n n n 為偶數(shù)時(shí)先手必?cái)?#xff0c;其余情況綜合勝率 1 2 \dfrac{1}{2} 21?
參考代碼
參考代碼為已AC代碼主干,其中部分功能需讀者自行實(shí)現(xiàn)
void solve()
{ll n;cin >> n;ll mx=0,t;FORLL(i,1,n){cin >> t;mx=max(mx,t);}if(mx>1) cout << inv(2) << endl;else if(n%2) cout << 1 << endl;else cout << 0 << endl;
}