---

前言

博弈類問題大致分為：
公平組合游戲、非公平組合游戲（絕大多數(shù)的棋類游戲）和 反常游戲

---

巴什博弈(Bash Game)

一共有n顆石子，兩個人輪流拿，每次可以拿1~m顆石子
最先取光石子的一方為勝（沒有石子可以拿的人為敗），根據(jù)n、m返回誰贏

分析：

我們從最簡單的情景開始分析
當石子有 1?m 個時，先手必勝（一次拿完）
當石子有m+1個時，先手無論拿幾個，后手都可以拿完，先手必敗
不難發(fā)現(xiàn)：面臨 m+1個石子的人一定失敗。
這樣的話，最優(yōu)策略一定是：通過拿走石子，使得對方拿石子時還有 m+1個剩余

推廣至一般情況：
【1】當n不可被m+1整除時，先手必勝
為什么？ n %（m+1）= r，先手拿走 r ，后手即面臨 m+1的整數(shù)倍顆石子，必敗
【2】同理，當n可被m+1整除時，先手必敗

---

測試鏈接 hduoj1846

示例code：

c = int(input())
for _ in range(c):n, m = map(int, input().split())if n % (m + 1) == 0:print("second")else:print("first")

---

小試牛刀

hduoj2188

題解：

# 和前面幾乎一樣的code
c = int(input())
for _ in range(c):n, m = map(int, input().split())if n % (m + 1) != 0:print("Grass")else:print("Rabbit")

---

PN分析

---

實戰(zhàn)檢驗

Roy&October之取石子

題目背景

Roy 和 October 兩人在玩一個取石子的游戲。

題目描述

游戲規(guī)則是這樣的：共有 $n$ 個石子，兩人每次都只能取 $p^k$ 個（ $p$ 為質(zhì)數(shù)，$k$ 為自然數(shù)，且 $p^k$ 小于等于當前剩余石子數(shù)），誰取走最后一個石子，誰就贏了。

現(xiàn)在 October 先取，問她有沒有必勝策略。

若她有必勝策略，輸出一行 October wins!；否則輸出一行 Roy wins!。

輸入格式

第一行一個正整數(shù) $T$，表示測試點組數(shù)。

第 $2$ 行$～$ 第 $T+1$ 行，一行一個正整數(shù) $n$，表示石子個數(shù)。

輸出格式

$T$ 行，每行分別為 October wins! 或 Roy wins!。

樣例輸入

3
4
9
14

樣例輸出

October wins!
October wins!
October wins!

提示

對于 $30\%$ 的數(shù)據(jù)，$1\le n\le 30$；

對于 $60\%$ 的數(shù)據(jù)，$1\le n\le 10^6$；

對于 $100\%$ 的數(shù)據(jù)，$1\le n\le 5\times 10^7$, $1\le T\le 10^5$。

（改編題）

思路：

每次可以拿質(zhì)數(shù)的自然數(shù)次方顆石子
對于6的倍數(shù)，一定不是質(zhì)數(shù)的某一自然數(shù)次方
1,2,3,4,5都可以一次取到，
當n=6時，第一個人無論怎么取，后手贏
推至一般情況：
當n不是6的倍數(shù)，先手贏
當n是6的倍數(shù)，后手贏

題解代碼：

t = int(input())
for _ in range(t):n = int(input())if n % 6 == 0:print("Roy wins!")else:print("October wins!")

---

總結(jié)

巴什博弈是一個相對簡單的問題，但它引入了重要的概念，比如P態(tài)和N態(tài)的概念，對理解更復(fù)雜的組合博弈非常有用。
此外，如何通過數(shù)學(xué)公式快速得出結(jié)論也是解決此類問題的關(guān)鍵技巧之一。

---

如果有更多問題或需要進一步的幫助，可以在評論區(qū)留言討論哦！
如果喜歡的話，請給博主點個關(guān)注 謝謝