# 省选联考 2023：区间可达闭包与有限博弈逆推

## 本节目标

学习在单向运动中做区间闭包，以及把带胜负、和棋、最快获胜/最慢失败规则的游戏统一成有限状态图逆推。

## 前置知识与课前自测

前置：区间排序、BFS、博弈图、拓扑式逆推。

1. 单向向右行驶时，可换乘线路集合怎样随最远可达点扩张？
2. 博弈状态若能走到一个“对下一玩家必败”的状态，当前是什么状态？
3. 必败状态的失败步数应取后继中的最小还是最大？

<details><summary>答案</summary>

1. 所有左端点不超过当前最远点且能继续向右的线路被纳入，更新最远右端点。
2. 必胜。
3. 当前玩家会拖延失败，取所有必胜后继距离的最大值再加一。

</details>

## 问题动机

《火车站》的转乘路径数可以指数多，《过河卒》又允许在状态图中循环而产生和棋。直接搜索单条路径都会被重复状态淹没。正确对象是不动点闭包：前者不断扩张单调可达区间，后者从终局反向扩张必胜/必败吸引域。

## 精选例题 1：火车站

### 来源、题意与范围

- [洛谷-P9166 火车站](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P9166)
- $n,m\le2\times10^5$，线路是数轴区间；从 x 上车后方向不变，可在覆盖站换轨，求所有可能最终停靠的线路端点。

<details><summary>Hint 1：左右方向独立</summary>分别计算向右和向左的可达线路闭包。</details>
<details><summary>Hint 2：向右扫描</summary>按左端点排序，只要 `l<=current_right` 就可能接入并扩张右端。</details>

### Observations、Editorial 与证明

向右时，初始可达位置为 x。所有左端点不超过当前最远位置的线路都能在某个已到达站换入；若其右端大于 x，它的右端可成为停靠结果，并可能扩张闭包。按左端点扫描每条线路一次。向左对称地按右端点降序扫描。

归纳扫描前所有不超过边界的站可达；新线路与可达区间相交，可在交点换入并沿同方向到端点。反之左端点尚超过边界的线路没有可换乘站，不能提前进入。复杂度 $O(m\log m)$。

### 核心伪代码与附件

```text
right = x
for intervals ordered by left endpoint while left <= right:
    if interval.right > x: record interval.right
    right = max(right, interval.right)
repeat symmetrically toward left
output sorted distinct recorded endpoints
```

[完整 C++17 附件](../../参考实现/12-历年真题/洛谷-P9166.cpp)

## 精选例题 2：过河卒

### 来源、题意与范围

- [洛谷-P9169 过河卒](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P9169)
- 棋盘至 $10\times10$，一黑两红、红先行；双方最优，能赢则最快保证获胜，必败则尽量拖延，可能和棋。输出胜者与总步数。

<details><summary>Hint 1：状态规模</summary>状态是黑位置、无序红位置对、轮到谁，约百万级。</details>
<details><summary>Hint 2：逆推规则</summary>能走到对手必败则必胜；所有后继都让对手必胜才必败；其余最终为和。</details>
<details><summary>Hint 3：距离</summary>必胜取最小必败后继距离，必败在所有必胜后继确定后取最大。</details>

### Observations

- 题目巨大的“100 的幂塔回合”只是表达无限循环视作和棋；有限状态图中未被胜负吸引域覆盖的状态就是和。
- 红棋同质，位置对排序可把状态减半。
- 不必存数百万状态的反图；根据当前轮次反向枚举上一步可能位置即可生成前驱。

### Editorial 与证明

枚举所有合法位置三元组与轮次，计算出度并初始化终局：黑到第一行、黑红重合、当前无合法步。用按距离的小根堆逆推。弹出必败状态时，未知前驱立即成为必胜；弹出必胜状态时，令前驱未确认后继数减一，全部后继均必胜后前驱成为必败，距离取最大后继加一。剩余未知为和。

这正是有限零和完全信息博弈的吸引域定义。小根堆保证必胜状态第一次由距离最小的必败后继确定；必败等待全部后继后取最大，符合双方题面策略。

状态 $O(S^3)$、边转移常数，其中可通行格 $S\le100$；内存约百万状态数组。

### 核心伪代码与附件

```text
initialize terminal WIN/LOSS states with distance 0
priority_queue ordered by distance
while queue:
    state = pop()
    for predecessor p generated on demand:
        if state is LOSS: mark p WIN with distance+1
        else:
            remaining_successors[p] -= 1
            record maximum winning-successor distance
            if remaining becomes 0: mark p LOSS with max+1
unknown states after propagation are draws
```

[完整 C++17 附件](../../参考实现/12-历年真题/洛谷-P9169.cpp)

## 实现指南

《火车站》将向右与向左完全分开，排序后每条线路只进入扫描指针一次；结果端点要排序去重。《过河卒》对两枚同质红棋的位置始终排序，以唯一编码压缩状态；必胜前驱在看到第一个必败后即可确定，必败前驱则必须等全部后继确定为必胜，两者的距离 min/max 不得混用。

## 扩展与联系

火车站是单调可达闭包，过河卒是胜负吸引闭包；两者都从已知集合反复加入满足局部条件的新对象，直到不动点。

## 总结与自检

1. 线路端点处为何仍可换轨？
2. 必胜/必败逆推的量词分别是什么？
3. 和棋为何对应最终未知状态？
4. 距离的 min/max 为什么不同？

## 课后训练建议

火车站与显式区间图 BFS 对拍；过河卒在 $3\times3$ 棋盘显式建全反图，对拍按需前驱版本。