0810. Chalkboard XOR Game¶
题目信息¶
- 题号:
0810
- 难度:
Hard
- 主题:
博弈、按位异或、最优策略
- 原题:
- 重点:
若回合开始时剩余数字异或值为 0,当前玩家立即获胜;否则必须删除一个数字,而使删除后异或值变为 0 的玩家立即失败
题目重述¶
黑板上写有数组 nums 中的全部整数。Alice 与 Bob 轮流行动,Alice 先手。每个回合开始时,若黑板上所有剩余数字的按位异或结果为 0,当前玩家立即获胜;否则当前玩家必须删除黑板上的一个数字。
若一次删除操作使剩余数字的异或结果变为 0,执行该删除的玩家立即失败。双方都采用最优策略。请判断 Alice 最终是否能够获胜。
1 <= nums.length <= 1000,0 <= nums[i] < 2^16。
自建示例¶
开局异或值已经为零:
输入:nums = [5,5]
输出:true
解释:两个数字的异或结果为 0,Alice 在自己的第一个回合开始时立即获胜。
唯一删除会使自己失败:
输入:nums = [7]
输出:false
解释:开局异或值为 7,Alice 只能删除唯一数字;删除后剩余集合的异或值为 0,因此 Alice 立即失败。