取球博弈

2026-05-03 暂无评论

全文共 292 字，阅读约 1 分钟

题目描述

两个人玩取球游戏。
一共有 N 个球，每人轮流取球，每次可取集合 {n1, n2, n3} 中的任意数目。
如果无法继续取球，则游戏结束。
此时，持有奇数个球的一方获胜。如果两人都是奇数，则为平局。
双方都采用最优策略，判断先手是否能赢。

解题思路

博弈 + 记忆化搜索，状态定义很关键。

游戏涉及三个维度：

剩余球数 num
当前玩家持有的球数奇偶性 x1
对方持有的球数奇偶性 x2
轮到谁 i（先手/后手）

用 dfs(num, x1, x2, i) 表示当前局面下，先手的胜负情况：

1：先手赢
-1：先手输
0：平局

先手轮次取 max（选对自己最有利的），后手轮次取 min（让对方最不利的）。加上 @lru_cache 剪枝，避免重复计算。

代码

import sys
sys.setrecursionlimit(10000)

from functools import lru_cache

n1, n2, n3 = map(int, input().split())
arr = list(map(int, input().split()))
moves = [n1, n2, n3]


@lru_cache(None)
def dfs(num, x1, x2, i):
    # 检查是否还能取球
    ok = False
    for v in moves:
        if num >= v:
            ok = True
            break
    if not ok:
        # 游戏结束，判断胜负
        if x1 == 1 and x2 == 0:
            return 1
        if x1 == 0 and x2 == 1:
            return -1
        return 0

    if i:
        # 先手轮次：取 max
        result = -1
        for j in moves:
            if j <= num:
                new_x1 = (x1 + j) % 2
                r = dfs(num - j, new_x1, x2, False)
                result = max(r, result)
                if result == 1:
                    break
        return result
    else:
        # 后手轮次：取 min（对方会让你最不利）
        result = 1
        for j in moves:
            if j <= num:
                new_x2 = (x2 + j) % 2
                r = dfs(num - j, x1, new_x2, True)
                result = min(r, result)
                if result == -1:
                    break
        return result


ans = []
for x in arr:
    res = dfs(x, 0, 0, True)
    if res == 1:
        ans.append('+')
    elif res == 0:
        ans.append('0')
    else:
        ans.append('-')
print(*ans)