摘要
Title: 894. 拆分-Nim游戏
Tag: 博弈论、sg函数
Memory Limit: 64 MB
Time Limit: 1000 ms

894. 拆分-Nim游戏

题意

给定 n堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。
思路

比如第 $a_i$ 堆石子，可以拆成 $b_1, b_2$ ，相当于将一个局面拆成了两个局面
由SG函数理论：多个独立局面的SG值，等于这些局面SG值的异或和
所以 $sg(a_i) = sg(b_1, b_2) = sg(b_1) \oplus sg(b_2)$
最后，再将 $a_i$ 这些的局面异或起来即可

代码

'''
Author: NEFU AB-IN
Date: 2023-03-22 22:16:04
FilePath: \Acwing\894\894.py
LastEditTime: 2023-03-22 22:23:37
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations

N = int(2e3 + 10)
INF = int(2e9)
f = [-1] * N


def sg(x):
    if f[x] != -1:
        return f[x]

    d = Counter()
    for i in range(x):
        for j in range(i + 1):
            d[sg(i) ^ sg(j)] = 1

    for i in range(INF):
        if d[i] == 0:
            f[x] = i
            return f[x]


n = int(input())
res = 0

lst = list(read())
for i in lst:
    res ^= sg(i)

print("Yes" if res != 0 else "No")

894. 拆分-Nim游戏

题意

思路

代码