0810. Chalkboard XOR Game

题目信息

题号:

0810

难度:

Hard

主题:

博弈、按位异或、最优策略

原题:

LeetCode 0810

重点:

若回合开始时剩余数字异或值为 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 立即失败。