BZOJ3895 取石子

这题思路不错。

首先考虑对于一个 >1 的堆,如果合并他对先手有利,那么这堆石子在取完之前一定会被先手合并。同理如果对后手有利也是。

既然合并这个动作要不就是对先手有利要么就是对后手有利,那肯定这堆石子最后会被合并。

并且在取完之前,合并这个动作无论在何时发生,都等同于在对这堆石子操作时的前两步内发生。

那么我们就可以把充裕堆 ( 大小 >1 的堆 ) 先提前合并了,然后在 DAG 游戏图上记搜 \mathrm{SG} 值。

操作分为几种:

  • 拿走一个孤单堆
  • 拿走充裕堆的一个石子
  • 把一个孤单堆合并到充裕堆内
  • 把两个孤单堆合并,成为充裕堆的一部分

然后就写个代码就好了。复杂度大概是 O(T \cdot \sum{a_i}) 的。

 

毒瘤题解#2 CEOI2008 | BZOJ1393 Knights

一道无比毒瘤的 Every-SG 的题。

注意此题BZOJ没有SPJ,方案输出要严格按照以下顺序 (找到了就输出) :

int dx[4]={-2,-2,-1,1},dy[4]={1,-1,-2,-2};

题面

上来先打表!这样:

把表打了你会发现一些奇怪的规律

然后写一下,我们就有:

好,那么这题基本就做完了。剩下的就是用用那个 Every-SG 的定理然后找一下方案罢了。。

 

毒瘤题解 BZOJ2410

某次搜 “Nim” 手贱搜出这破题来,结果自闭了一上午,自闭了。

首先考虑 k>2 的情况,因为任意一个格子都可以填颜色而两边的格子不会影响它,答案是 0 的格子数的奇偶性决定的。

那么再来考虑 k=1 的情况。此时我们把每段白格子单独拿出来看:

首先(除掉整个序列的开头和结尾)每段的第 1 和最后一个这两个格子是不能染色的。

那么假设我们在中间染了一个,那就分成了两个子局面,比较显然这两个子局面是相互独立的,那么我们就可以用 SG 定理了。

再考虑如何算一段白格的 \mathrm{SG} 。首先长度为 0 的白格子的 \mathrm{SG}0 ,长度为 1 的因为只能转移到 0 所以  \mathrm{SG}=1

那么接下来考虑长度为 n 的,我们先假设这 n 个格都能被染色

那么染位置 i 会让剩下两段为 i-2n-i-1

(注意特判 i=1i=n 的情况,这两种本质上是一样的)

那么我们爆算一波 \mathrm{SG}  值。

打个表找规律

0,1,1,2,0,3,1,1,0,3,3,2,2,4,0,5,2,2,3,3,0,1,1,3,0,2,1,1,0,4,5,2,7,4,
0,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,2,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7,4,
8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4,5,3,7,4,
8,1,1,2,0,3,1,1,0,3,3,2,2,4,4,5,5,9,3,3,0,1,1,3,0,2,1,1,0,4

然后发现除前两段之后循环节为 34

(其实这个非常神奇,不过这种模型居然也出现在 《Winning Ways》 里面了,Orz……可以看一下这个A002187 )

然后就直接乱搞就可以了。。

这就完了,再来考虑 k=2 的情况

如果你不去管全部空白的特殊情况,那么空白块总共有三种:

  1. 有一端与一个染色块相邻,另一端为整个序列的首或尾。
  2. 两端都与染色块相邻,两端颜色不同。
  3. 两端都与染色块相邻,两端颜色相同。

可以把 [2] 和 [3] 一起考虑,很轻松的使用归纳法证明 [2] 的 \mathrm{SG} 值都是 0 ,[3] 的 \mathrm{SG} 值都是 1

那么考虑第一种情况,随便画个图或者写个暴力可以得到长度为 n 的段的 \mathrm{SG}=n

这样就基本做完了。再回来考虑全部空白的情况。如果长度为 N ,后继局面显然有 N 种。

然后你发现每种都是两个子局面异或起来,假设先手从位置 i 劈开,那么就是 i-1 \oplus n-i

然后 O(n) 求一下 \mathrm{SG} 就好了。

不过事实上是数据过水,导致没有这类情况,不用写就能过。。。。

另外搜 A002187 的资料的时候我搜到一份很有趣的文档讲的是这个序列和井字格游戏的关系,好像可以出一道题的样子。。

 

– END –

随便搞搞 ICG (公平组合游戏) 和其余的博弈

写在阅读之前:

本文是我在 10 月份期间开始的对一些见过或者想要学习的博弈模型的一个总结计划。本文篇幅较长,覆盖多种模型,以下是一份可以帮助阅读、理清主干的主题清单:

(待填充)

请注意本文分多页,可以在文末翻页

文章中数学证明、公式较多,请做好阅读理解的准备。这篇文不是闹着玩的,读就请认真读它。先说一句比较自以为是的话:

读这篇文学习博弈论的过程,并不是去背公式或者记性质,而是去熟悉并掌握处理博弈问题的一般思维方式。

快速索引:

Wythoff Game –  第 1 页

Nim Game – 第 2 页

从 Nim Game 到其他组合游戏 ||  归纳与推广、泛化模型 – 第 3 页

SG 函数的构造 || 更进一步的推广 – 第 4 页

Anti-Nim 与 Anti-SG – 第 5 页

Multi-SG || Every-SG – 第 6 页

翻硬币游戏 || NimK || 扩展 NimK第 7 页

树上删边游戏 || 无向图的删边游戏 – 第 8 页

扩展阅读列表  – 第   页

记号约定清单:

对于集合,用 \mathbb{A} 的字体表示。

对于局面,用 \mathbf{a} 的字体或 \mathrm{S},\mathrm{T} 来表示。

\text{s.t.}  → “ 使得 ”  , such that subject to 的缩写。

\forall \exists 分别为 “ 任意 ” 和 “ 存在 ” 的意思(数学量词)。

\oplus  → 代表 xor ( 按位异或 ) 运算。

DAG → 有向无环图。

ICG → 公平组合游戏。

SG → Sprague-Grundy 函数


Wythoff Game

经典的 Wythoff 博弈模型。

这个模型的描述是这样的:地上有两堆石子,其中一堆有 m 个石子,另外一堆有 n 个石子。两名玩家轮流取走石子,规定每次要么从其中一堆石子中取走任意多个石子,要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了,谁就输了。也就是说,取到最后一个石子的玩家获胜。

这玩意其实还可以描述为:

把国际象棋棋子皇后放在棋盘上,两人遵循棋子的走法,轮流移动棋子,但只能将棋子往左方、下方或者左下方移动。谁先将棋子移动到棋盘的最左下角,谁就获胜。

描述局面、获得结论

我们知道博弈的关键就是局面,那么我们考虑用一个数学模型去描述局面好了。我们把局面记作一个无序二元组 (n,m)

  • 首先我们知道 (0,0) 是一个必败态
  • 其次, (n,0) \,(n \in \mathbb{N}_{+}) (n,n) \,(n \in \mathbb{N}_{+}) 是必胜态,因为先手拿走 n 就好了。
  • 再然后,我们考虑一个更加一般的状态 A=(n,m) \,( n,m \in \mathbb{N}_{+} \,\, , n \ne m)

我们先给出结论:所有先手必败的数对(我们称为奇异局面)分别是:

(1, 2), (3, 5), (4, 7), (6, 10), (8, 13)

更严格地来说,其实是:

\mathbb{S} = \{(\lfloor 1 \cdot \varphi \rfloor , \lfloor 1 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 2 \cdot \varphi \rfloor , \lfloor 2 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 3 \cdot \varphi \rfloor , \lfloor 3 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 4 \cdot \varphi \rfloor , \lfloor 4 \cdot \varphi^2 \rfloor ) \}

其中的 \varphi \frac{ \sqrt{5}+1 }{2}

关于这个结论最科学的推法(而不是什么打表找规律),这里有我整理的一份文档,可以读一读 : Wythoff Game

证明结论

这里我们尝试证明这些状态的三个性质,从而证明这个构造是先手必败的(设状态为 \forall A \in \mathbb{S} )  :

  • 状态 A 无法一步转移到状态 (0,0)
  • 状态 A 无法一步转移到 \mathbb{S} 的另一个状态。
  • 状态集合 \mathbb{S} 之外的任何非零状态都可以一步转移到一个零状态\mathbb{S} 中的某一状态。

这样我们的博弈策略是后手始终把当前状态转移到 \mathbb{S} 中的状态,从而可以胜利。

对于上面三条性质的证明,可以在这里找到。我有空再仔细补坑