一、 算法&數(shù)據(jù)結(jié)構(gòu)

1. 描述

博弈一直沒怎么學(xué)，每次遇到了就看看題解，這兩周被atc和?？蛙娪?xùn)了，還都沒做出來，思考了一下，暫且記錄我粗淺的認知。
如果我未來能好好學(xué)學(xué)，可能回來更新。

• 第一次做博弈可能是在LC，做了幾道題發(fā)現(xiàn)基本上都可以用記憶化搜索來枚舉局面。就記住了這個做法：
  • 記憶化搜索式做法，復(fù)雜度和局面狀態(tài)數(shù)有關(guān)。
  • 注意，我們不管當前的人是誰，只要這個人遇到了這個局面，計算他在最優(yōu)選擇下是否能贏，就是必勝態(tài)。
  • 必勝的條件是，選完后，下個人是必敗態(tài)；那么當前人的操作中，只要有一個必敗態(tài)，當前就是必勝態(tài)。（因為當前人可以選擇這個使下個人必敗的操作。）
  • 而只有無論怎么操作，下個人都是必勝時，當前才是必敗。因此有以下代碼方式,（狀態(tài)有倆參數(shù)）：

    @lru_cache(None)
    def dfs(m, n):if xxd遞歸出口:return False/Truefor i in range(1, (m + 1) // 2):  # 枚舉所有選擇if not dfs(i, n):   # 注意這個not,后繼態(tài)必敗，當前必勝return True		   return False
    

• dfs方式的問題是當狀態(tài)太多或選擇太多，復(fù)雜度不一定能過。這時就要想想，能不能有貪心策略了。
  • 但貪心又不是很簡單能想出來的，那么請果斷寫個dfs，然后打表！找規(guī)律！

2. 復(fù)雜度分析

1. dfs方式，具體分析，一般取決于狀態(tài)數(shù)和轉(zhuǎn)移方式。
2. 貪心打表方式：不一定。

3. 常見應(yīng)用

1. 基礎(chǔ)的博弈題。

4. 常用優(yōu)化

1. 注意?？偷难b飾器必須加括號:@lru_cache(None)。

二、 模板代碼

1. 打表貪心的博弈

例題: 小d的博弈

• 具體題解可以見我這場比賽的題解。

# Problem: 小d的博弈
# Contest: NowCoder
# URL: https://ac.nowcoder.com/acm/contest/53366/E
# Memory Limit: 524288 MB
# Time Limit: 2000 msimport sys
from functools import lru_cacheRI = lambda: map(int, sys.stdin.buffer.readline().split())
RS = lambda: map(bytes.decode, sys.stdin.buffer.readline().strip().split())
RILST = lambda: list(RI())
DEBUG = lambda *x: sys.stderr.write(f'{str(x)}\n')MOD = 10 ** 9 + 7
PROBLEM = """
"""@lru_cache(None)
def dfs(m, n):if m <= 2 and n <= 2:return Falseif m <= 2 or n <= 2:return Truefor i in range(1, (m + 1) // 2):if not dfs(i, n):return Truefor j in range(1, (n + 1) // 2):if not dfs(m, j):return Truereturn False#     603  ms
def solve1():n, m = RI()y = x = 0while n > 2:n = (n - 1) // 2x += 1while m > 2:m = (m - 1) // 2y += 1if x != y:print('Alice')else:print('Bob')#   573    ms
def solve():n, m = RI()if (n + 1).bit_length() != (m + 1).bit_length():print('Alice')else:print('Bob')if __name__ == '__main__':t, = RI()for _ in range(t):solve()# for i in range(1, 40):#     for j in range(1, 40):#         print('X' if dfs(i, j) else 'O', end=' ')#     print()

2. 464. 我能贏嗎

鏈接: 464. 我能贏嗎

• 第一步加個貪心判斷，然后dfs

class Solution:def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:@cachedef dfs(used_numbers,total):for i in range(maxChoosableInteger):if (used_numbers>>i)&1 == 0:  # used_numbers第i位是0，即i未被使用，他可以用if total + i +1 >= desiredTotal:return Trueif dfs(used_numbers|(1<<i),total+i+1) == False:  # 下一步的操作者，即下一個人輸?shù)?/span>return Truereturn Falsereturn (1+maxChoosableInteger)*maxChoosableInteger//2 >= desiredTotal and dfs(0,0)

3. Nim游戲–最最基礎(chǔ)版n=1。

鏈接: 292. Nim 游戲

• nim游戲應(yīng)該算一個小類別了，可以有n堆石子，每次也不一定讓取多少個石子。
• 我準備單開一個頁面寫nim游戲的sg函數(shù)。
• 這題由于只有一堆，策略就非常簡單，每次完剩余數(shù)字應(yīng)該是4的倍數(shù)，這樣對方一定拿不完，而我可以一步到同樣的狀態(tài)。對上下界的和取模即可。

class Solution:def canWinNim(self, n: int) -> bool:return bool(n%4)

三、其他

四、更多例題

五、參考鏈接

• 鏈接: 【agKc/ACM】ABC297G P2197 |基礎(chǔ)博弈論|SG函數(shù)|SG定理