Powered by:NEFU AB-IN

Link

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 permutationsN = 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)] = 1for i in range(INF):if d[i] == 0:f[x] = ireturn 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 permutationsN = 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")