算法基础课|数学知识|博弈论

发表于 分类于 浏览： 阅读时长 ≈ 1 分钟
ACWing 算法基础课笔记 博弈论相关

博弈论

（先手）必胜状态和必败状态

  • 必胜状态：
    • 先手进行某一个操作，留给后手的是一个必败状态时，我们称先手处于一个必胜状态。即先手可以走到某一个必败状态
  • 必败状态：
    • 先手进行某一个操作，无论怎么操作，留给后手的一定是必胜状态，我们称先手处于一个必败状态。即先手走不到任意一个必败状态。

结论：

有N堆石子

$a_1,a_2,a_3,a_4,a_5…$, 如果$a_1 \wedge a_2 \wedge a_3 \wedge a_4… \wedge a_n \not= 0$ ，则先手必胜，否则先手必败

证明

Untitled

SG函数

  • mex函数：设集合S是一个自然数集合，mex(s)表示不属于s的最小自然数
    • mex({2,3,4,5}) = 0
    • mex({1,2,3}) = 0
    • mex({0,1,3,4}) = 2

Untitled

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def sg(x):
    if f[x] != -1: return f[x]
    s = set()
    for item in a:
        if x >= item:
            s.add(sg(x - item))
    for i in range(len(s) + 1):
        if i not in s:
            f[x] = i
            break
    return f[x]
res = 0
for item in lis:
    res = res ^ sg(item)