山东大学程序设计精英挑战赛G题解

题解

1. 状态建模

游戏区域宽度固定为 2，高度上限为 。记当前两列堆叠的最高占据层分别为 ，且不妨设 。定义：

• 当前最高高度
• 剩余可用高度 ，即还可以再"向上"放置多少层而不溢出。

显然所有合法操作都会使 增大，从而使 减少。游戏在某一步无法再放置合法方块时结束，该步的当前玩家判负。

2. 合法操作对状态的影响

三种方块的下落最终高度只取决于当前 ：

1. 横向 2×1：占据 这一层的两个格子。新高度变为 ，故 增加 1， 减少 1。
2. 纵向 2×1（选列 ）：在该列顶部再增加两层：。新最大高度：
   • 若在较高列放置：原较高列 变为 ，故 增加 2， 减少 2。
   • 若在较低列放置：设有序对 且 。在低列放置纵向块得到 。
     • 若 ，则 不变， 不变。但放置纵向块需要占据 两层，若 ，说明高列已经占据到 层，但低列在 层是空的，不冲突，可落下。此时最大高度仍为 。
     • 若 ，则新最大高度为 ，提升 2， 减少 2。

综合后可统一视作：纵向块的有效"最大高度提升"结果只可能是 2 或 0；但我们将证明"0 提升"不改变 SG 仅依赖 的结论。

3. 2×2 方块：占据 与 两层的两个列，故新高度 ， 增加 2， 减少 2。

合法性条件：

• 横向：需 （即 ）。
• 纵向在某列：需该列 。当剩余 时，总能在较高列放置一次纵向块。
• 2×2：需 （即 ）。

因此每一步对 的"净影响"只可能是：（横向），或 （纵向、2×2），或在某些纵向低列填充下保持 不变（高度差缩小但最大高度不变）。接下来我们说明" 不变的纵向操作"对整体 SG 不造成新的分支类型。

3. SG 函数是否需要区分高度差？

我们考虑状态 的"差值" 。是否需要将 纳入 SG 计算维度？

关键观察：一切导致 的操作（纵向放在单列）在后续都存在一招可快速"拉平"差值：

• 放置横向块或 2×2 方块，会令两列同时提升到同一高度（新的最大高度），即进入 的"对称态"。

同时，从任一不对称态（）出发，总能选择横向或 2×2，使 下降 1 或 2 并进入对称态。因此：

1. 所有非对称态的可选后继包含一个"对称态，剩余高度减少 1 或 2"。
2. 所有非对称态还可以通过继续纵向增加差值，等价于再次执行一次 操作或一次"差值修正但不减 "操作。

而"差值修正但不减 "（在较低列填纵向导致最大高度不变）只改变内部差值，不改变 ，后继集合最终仍会在将来某步选择横向或 2×2 引导到对称态并正式减少 。这类"空转"在 SG 上等价于添加一条指向同 Grundy 值状态的边，不影响 mex 计算结果（可以形式化为将所有含差值的状态并入仅按 分类的等价类）。

因此可严格缩减：SG 只依赖剩余高度 。

4. 化简为"减 1 或减 2"的取走游戏

在仅依赖 的视角下：

• 从 可以转移到 （横向）若
• 从 可以转移到 （纵向或 2×2）若

不存在其它有效改变 的结果。于是该游戏等价于经典单堆取石游戏：一堆剩余 个石子，每次可取 1 个或 2 个，不能取则当前玩家失败。

5. SG 函数递推与周期

设 为剩余高度 的 Grundy 值。递推：

其中当 时只有 一个后继。

计算前若干项：

	后继
0	—	0
1		1
2		2
3		0
4		1
5		2
6		0

出现长度为 3 的循环：（其中 时 Grundy 为 0）。

6. 胜负判定

初始状态 ，故 ，。先手（Alice）获胜当且仅当 ，即 。

于是：

• 若 ，先手必败，答案 Bob
• 否则先手必胜，答案 Alice

7. 最优策略描述

• 当 ：先手首先放置横向块（使剩余高度变为 ），之后采取"镜像策略"：每当对手减少 1，高度差回到 （非零 Grundy），再用减少 2；反之亦然，保持让对手面对 。

• 当 ：先手首先放置 2×2 块或纵向块提升两层（使剩余高度变为 ），后续同理。

• 当 ：任何操作都会把 变成 或 ，均为非零 Grundy，给对手一个可通过单步回归到 （再次 0）的机会，因此必败。

8. 复杂度与实现

只需判断 ，单组 ，总 。对 直接取模即可。