摘要
Title: 4005. 取石子游戏
Tag: 博弈论、sg函数、找规律
Memory Limit: 64 MB
Time Limit: 1000 ms

4005. 取石子游戏

题意

Alice 和 Bob 正在玩一个取石子游戏。
共有 n个石子，双方轮流采取行动。
每当轮到一人行动时，该名玩家需要从石子堆中取走恰好 1或 2或 k个石子。
如果轮到一人行动时，已经没有石子可取，则该名玩家失败。
已知，双方都会采取最优策略，且 Alice 率先行动。
请问，最终谁将获胜。
思路

具体思路可以参考这篇博客 link
ps: 这篇博客的循环节找的不能说错，但最好是从0开始，如 $0,1,2,3$

遇到这种单堆石子博弈论问题，可以通过sg函数打表的方式找规律求解
比如这个题，就可以枚举k的取值，然后将sg值打表打出来找规律

代码

打表代码

'''
Author: NEFU AB-IN
Date: 2023-03-25 18:49:28
FilePath: \Acwing\4005\4005.py
LastEditTime: 2023-03-25 18:54:33
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations

N = int(1e3 + 10)
INF = int(2e9)
f = [-1] * N
# 打表代码

def sg(x):
    if f[x] != -1:
        return f[x]
    
    d = Counter()
    for i in lst:
        if x >= i:
            d[sg(x - i)] = 1
    
    for i in range(INF):
        if d[i] == 0:
            f[x] = i
            return f[x]


k = int(input())

lst = [1, 2, k]

for i in range(0, 20):
    print(i, sg(i))

正式代码

'''
Author: NEFU AB-IN
Date: 2023-03-25 18:57:14
FilePath: \Acwing\4005\4005.1.py
LastEditTime: 2023-03-25 19:00:55
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations

N = int(1e3 + 10)
INF = int(2e9)
# 正式代码

for _ in range(int(input())):
    n, k = read()
    if k % 3:
        if n % 3:
            print("Alice")
        else:
            print("Bob")
    else:
        ys = n % (k + 1)
        if ys % 3 == 0 and ys != k:
            print("Bob")
        else:
            print("Alice")

4005. 取石子游戏

题意

思路

代码