1510. Stone Game IV¶
题目信息¶
- 题号:
1510
- 难度:
Hard
- 主题:
博弈论、动态规划、完全平方数
- 原题:
- 重点:
两人轮流移除正完全平方数颗石子,无法行动者失败;判断先手在双方最优策略下能否获胜
题目重述¶
一堆中初始有 n 颗石子。Alice 与 Bob 轮流行动,Alice 先手。每次必须移除 x^2 颗石子,其中 x 为正整数且移除数量不能超过当前剩余石子数。
无法进行合法操作的玩家失败。假设双方都采用最优策略,请判断 Alice 是否必胜。
1 <= n <= 10^5。
自建示例¶
先手唯一选择会把必胜状态交给对手:
输入:n = 2
输出:false
解释:Alice 只能移除一颗,Bob 随后移除最后一颗并获胜。
石子数本身是完全平方数时先手可立即取完:
输入:n = 1
输出:true
解释:Alice 移除 1^2 颗石子后,Bob 无法行动。