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

一、 算法&数据结构

1. 描述

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

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

    @lru_cache(None)
    def dfs(m, n):
        if xxd递归出口:
            return False/True
    
        for 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 ms

import sys
from functools import lru_cache

RI = 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 False
    if m <= 2 or n <= 2:
        return True
    for i in range(1, (m + 1) // 2):
        if not dfs(i, n):
            return True
    for j in range(1, (n + 1) // 2):
        if not dfs(m, j):
            return True
    return False


#     603  ms
def solve1():
    n, m = RI()
    y = x = 0
    while n > 2:
        n = (n - 1) // 2
        x += 1
    while m > 2:
        m = (m - 1) // 2
        y += 1
    if 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:
        @cache
        def 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 True
                    if dfs(used_numbers|(1<<i),total+i+1) == False:  # 下一步的操作者，即下一个人输掉
                        return True
            return False

        
        return (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定理