垂直电商网站建设方案,wordpress商品系统,网站内容管理系统cms,html 网站新功能介绍[python刷题模板] 博弈入门-记忆化搜索/dp/打表 一、 算法数据结构1. 描述2. 复杂度分析3. 常见应用4. 常用优化二、 模板代码1. 打表贪心的博弈2. 464. 我能赢吗3. Nim游戏--最最基础版n1。三、其他四、更多例题五、参考链接一、 算法数据结构
1. 描述
博弈一直没…
[python刷题模板] 博弈入门-记忆化搜索/dp/打表 一、 算法数据结构1. 描述2. 复杂度分析3. 常见应用4. 常用优化二、 模板代码1. 打表贪心的博弈2. 464. 我能赢吗3. Nim游戏--最最基础版n1。三、其他四、更多例题五、参考链接一、 算法数据结构
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 Falsedfs方式的问题是当状态太多或选择太多复杂度不一定能过。这时就要想想能不能有贪心策略了。 但贪心又不是很简单能想出来的那么请果断写个dfs然后打表找规律
2. 复杂度分析
dfs方式具体分析一般取决于状态数和转移方式。贪心打表方式不一定。
3. 常见应用
基础的博弈题。
4. 常用优化
注意牛客的装饰器必须加括号: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_numbersi)1 0: # used_numbers第i位是0即i未被使用他可以用if total i 1 desiredTotal:return Trueif dfs(used_numbers|(1i),totali1) False: # 下一步的操作者即下一个人输掉return Truereturn Falsereturn (1maxChoosableInteger)*maxChoosableInteger//2 desiredTotal and dfs(0,0)3. Nim游戏–最最基础版n1。
链接: 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定理
