892. 台阶-Nim游戏
| 2024-5-7
0  |  阅读时长 0 分钟
From
AcWing
Status
AC
Date
Tags
博弈论
Difficulty
简单

描述

现在,有一个 级台阶的楼梯,每级台阶上都有若干个石子,其中第 级台阶上有 个石子()。
两位玩家轮流操作,每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中(不能不拿)。
已经拿到地面上的石子不能再拿,最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。

输入格式

第一行包含整数
第二行包含 个整数,其中第 个整数表示第 级台阶上的石子数

输出格式

如果先手方必胜,则输出 Yes
否则,输出 No

数据范围

,

输入样例:

输出样例:

思路

此时我们需要将奇数台阶看做一个经典的Nim游戏,如果先手时奇数台阶上的值的异或值为0,则先手必败,反之必胜
证明: 先手时,如果奇数台阶异或非0,根据经典Nim游戏,先手总有一种方式使奇数台阶异或为0,于是先手留了奇数台阶异或为0的状态给后手 于是轮到后手: ①当后手移动偶数台阶上的石子时,先手只需将对手移动的石子继续移到下一个台阶,这样奇数台阶的石子相当于没变,于是留给后手的又是奇数台阶异或为0的状态 ②当后手移动奇数台阶上的石子时,留给先手的奇数台阶异或非0,根据经典Nim游戏,先手总能找出一种方案使奇数台阶异或为0 因此无论后手如何移动,先手总能通过操作把奇数异或为0的情况留给后手,当奇数台阶全为0时,只留下偶数台阶上有石子。 (核心就是:先手总是把奇数台阶异或为0的状态留给对面,即总是将必败态交给对面)
因为偶数台阶上的石子要想移动到地面,必然需要经过偶数次移动,又因为奇数台阶全0的情况是留给后手的,因此先手总是可以将石子移动到地面,当将最后一个(堆)石子移动到地面时,后手无法操作,即后手失败。
因此如果先手时奇数台阶上的值的异或值为非0,则先手必胜,反之必败!

代码

Loading...
目录