[python刷题模板] 博弈入门-记忆化搜索/dp/打表

一、 算法&数据结构

1. 描述

博弈一直没怎么学，每次遇到了就看看题解，这两周被atc和牛客军训了，还都没做出来，思考了一下，暂且记录我粗浅的认知。
如果我未来能好好学学，可能回来更新。

• 第一次做博弈可能是在LC，做了几道题发现基本上都可以用记忆化搜索来枚举局面。就记住了这个做法：
  • 记忆化搜索式做法，复杂度和局面状态数有关。
  • 注意，我们不管当前的人是谁，只要这个人遇到了这个局面，计算他在最优选择下是否能赢，就是必胜态。
  • 必胜的条件是，选完后，下个人是必败态；那么当前人的操作中，只要有一个必败态，当前就是必胜态。（因为当前人可以选择这个使下个人必败的操作。）
  • 而只有无论怎么操作，下个人都是必胜时，当前才是必败。因此有以下代码方式,（状态有俩参数）：

    @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,后继态必败，当前必胜return True		   return False
    

• dfs方式的问题是当状态太多或选择太多，复杂度不一定能过。这时就要想想，能不能有贪心策略了。
  • 但贪心又不是很简单能想出来的，那么请果断写个dfs，然后打表！找规律！

2. 复杂度分析

1. dfs方式，具体分析，一般取决于状态数和转移方式。
2. 贪心打表方式：不一定。

3. 常见应用

1. 基础的博弈题。

4. 常用优化

1. 注意牛客的装饰器必须加括号:@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:  # 下一步的操作者，即下一个人输掉return Truereturn Falsereturn (1+maxChoosableInteger)*maxChoosableInteger//2 >= desiredTotal and dfs(0,0)

3. Nim游戏–最最基础版n=1。

链接: 292. Nim 游戏

• nim游戏应该算一个小类别了，可以有n堆石子，每次也不一定让取多少个石子。
• 我准备单开一个页面写nim游戏的sg函数。
• 这题由于只有一堆，策略就非常简单，每次完剩余数字应该是4的倍数，这样对方一定拿不完，而我可以一步到同样的状态。对上下界的和取模即可。

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

三、其他

四、更多例题

五、参考链接

• 链接: 【agKc/ACM】ABC297G P2197 |基础博弈论|SG函数|SG定理