博弈论简单题赏

Bellala, 20240730

CF1956B Nene and the Card Game

*800

一副牌有 各两张,随机发给你和 Nene,每个人发 张,轮流出牌。打出一张牌后,若桌上之前已经有这张牌,则得一分。Nene 会在她自己的得分最高的情况下让你的得分最低。

给定你的初始手牌,问你最高可以获得多少分。

CF1956B Nene and the Card Game

解析

假设你手上有 张单牌和 张对子,那么 Nene 也会有 张单牌和 张对子。因此,你无法用单牌得分,只能得到手上全部对子的分数。

CF1990A Submission Bait

*900

给定 个正整数,Alice 和 Bob 轮流按下列规则取走 中的一个数:

  • 如果之前没有取过任何数,那么本轮可以随便取。
  • 否则,假设之前取过的所有的数的最大值为 ,则本轮所取的数必须大于等于

Alice 先手,无法进行操作的人输。请输出两人都用最优策略的情况下的胜者。

CF1990A Submission Bait

解析

从大到小判断每个数字的出现次数,只要有一个数字出现过的次数为奇数,那就是先手胜。

CF1972B Coin Games

*900

桌子上有 枚硬币围成一个圆圈,每枚硬币要么朝上,要么朝下。两名玩家轮流操作。

在每次操作中,玩家选择一枚正面朝上的硬币,取出硬币并翻转与其相邻的两枚硬币。玩家进行操作前,如果只剩下两枚硬币,则取出一枚,另一枚不翻转(因为会翻转两次);如果只剩下一枚硬币,则不会翻转任何硬币;如果没有正面朝上的硬币,玩家就输了。

两人做的都是最优决策,请问先手是否会获胜。

CF1972B Coin Games

解析

假设在全部硬币中,有 个硬币是正面朝上。

操作中取出硬币会改变 的奇偶性,而翻转相邻的硬币一定不会改变 的奇偶性。

所以玩家的操作实际上就是改变 的奇偶性。

那么先手必胜当且仅当 为奇数。

Bash 游戏

只有一堆 个石子,两个人轮流从这堆石子中取,每次至少取 个,最多取 个。最后取完者胜。

反 Bash 游戏

只有一堆 个石子,两个人轮流从这堆石子中取,每次至少取 个,最多取 个。最后取完者胜。

2 堆石子的 Nim 游戏

两堆石子,分别有 个和 个。每次可以任选一堆,从中取走至少 个石子,最后取完者胜。两人轮流操作,问先手还是后手有必胜策略。

HDU1404 Digital Deletions

一串由0~9组成的数字,可以进行两个操作:

  1. 把其中一个数变为比它小的数;
  2. 把其中一个数字0及其右边的所有数字删除。

两人轮流进行操作,最后把所有数字删除的人获胜,问先手胜还是后手胜。