文章目录

CEOI2021 Day2 T1 Stones 做题笔记

发布于

题意

Ankica 和 Branko 在玩游戏。
有 $n$ 堆石子,第 $i$ 堆有 $a_i$ 个。玩家轮流移除一堆石子中的若干个,取到最后一个石子的玩家获胜。
但在该游戏中每个玩家从哪堆石子中取石子是由另一名玩家固定的。

具体来说,游戏的回合数从 $1$ 开始每次递增,增量为 $1$,而游戏将会以如下方式进行:

  • 在奇数回合,Branko 将指定一个非空石子堆。Ankica 将移除这堆石子至少一个。
  • 在偶数回合,Ankica 将指定一个非空石子堆。Branko 将移除这堆石子至少一个。

作为专业的游戏玩家,在 Branko 摆完石子后,Ankica 很快意识到这个游戏对她有必胜策略。

你模拟 Ankica,跟交互库对弈。

$1 \leq n \leq 500$

题解

好题,可以先思考一下

查看题解
首先,考虑到在游戏仅剩下 石子数量为 $1$ 的石子堆 时,输赢关系仅与这样的石子堆数量有关,而且双方都不可能改变。
这就意味着,Ankica 必须在忽略所有 石子数量为 $1$ 的石子堆 的情况下,用剩下的石子堆操控输赢。

由考虑到,取石子时,要么一次全取走,要么留一颗给对手,否则就把主动权让给了对手,因为 一次全取走 和 留一颗给对手 对应这两种不同的胜负关系,(留一颗给对手 之后可以指定对手取这一堆)。

因此,在至少有一堆 石子数量不为 $1$ 的石子堆 时,Ankica 一定能通过上述方式赢。
如果没有一堆 石子数量不为 $1$ 的石子堆 时,双方都不可能改变结果。而题目保证给出的初始状态使得无论 Branko 怎么操作你都有必胜策略。所以不会出现这种情况。


暂无评论

发表评论