# CSP-S 2022 真题：可达候选压缩与乘法符号博弈

## 本节目标

学习当答案只选常数个对象时保留少量最优候选，以及把区间乘法极值按符号缩成四类代表值。

## 前置知识与课前自测

前置：BFS、Top-k、RMQ/稀疏表、极值分类。

1. 四个景点互异时，为每个中间点保留前三名候选为何可能足够？
2. 固定 $x$ 后，$\min_y xy$ 只需 B 区间的哪些值？

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

1. 与另一侧最多冲突两个编号，前三名中至少还有一个不冲突候选。
2. 若 x 非负取最小 B，若 x 负取最大 B；统一可检查 B 的最小与最大。

</details>

## 问题动机

《假期计划》的四点选择有 $O(n^4)$ 组合，《策略游戏》的每次查询又像需要枚举两个区间的笛卡尔积。两题分别通过“为每个接口只留少数最优候选”与“乘积只由符号类型和端值决定”删掉这些枚举。

## 精选例题 1：假期计划

### 来源、题意与范围

- [洛谷-P8817 假期计划](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P8817)
- $n\le2500,m\le10^4$；从家 1 访问四个不同景点 A、B、C、D 后回家，每段最多经过 $k+1$ 条边，最大化分数和。

<details><summary>Hint 1</summary>先求任意点对是否能在 k+1 条边内到达。</details>
<details><summary>Hint 2</summary>枚举中间 B、C；A 必须同时接家与 B，D 同时接 C 与家。</details>
<details><summary>Hint 3</summary>每个 B/C 只保留分数最高的三个端点候选。</details>

### Observations、Editorial 与证明

对每点 BFS 得可达矩阵。对每个 b，收集满足 `reach[1][a] && reach[a][b]` 的 a，保留分数前三。枚举可达的 b,c，再枚举两侧各至多三候选并检查四点互异。

任何最优方案的 a 若不在 b 的前三，前三中至多因等于 c,d 而淘汰两个，仍有一个分数不低且不冲突，可替换；d 同理。因此候选压缩不丢最优。复杂度 $O(n(n+m)+n^2)$。

### 核心伪代码与附件

```text
reach = BFS_from_every_vertex(limit=k+1)
best3[b] = top 3 scores among a reachable from home and able to reach b
for b,c where reach[b][c]:
    for a in best3[b], d in best3[c]:
        if a,b,c,d distinct: maximize score sum
```

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

## 精选例题 2：策略游戏

### 来源、题意与范围

- [洛谷-P8818 策略游戏](https://vjudge.net/problem/%E6%B4%9B%E8%B0%B7-P8818)
- $n,m,q\le10^5$；每问 L 从 A 区间先选 x，Q 从 B 区间选 y，L 最大化而 Q 最小化乘积 xy。

<details><summary>Hint 1</summary>固定 x，Q 只会选择 B 的最小值或最大值。</details>
<details><summary>Hint 2</summary>A 中只需最大/最小、最小非负、最大非正四类候选。</details>

### Observations

- 乘积关于 y 对固定 x 单调，内层最小只在 B 两端极值取得。
- 外层函数 `min(x*minB,x*maxB)` 在正半轴、负半轴分别单调，最优只在靠近 0 或远端的代表值。
- 零必须同时视为非负和非正，能把负收益提升到 0。

### Editorial 与正确性证明

稀疏表查询 B 的 min/max，以及 A 的 min/max、最小非负、最大非正。逐候选计算 Bob 的最坏乘积并取最大。A 任一正数的最坏值由 B 最小决定，在线性函数上最优位于正数区间端点；负数同理由 B 最大决定；四类代表覆盖这些端点与零。因此不会漏最优。

预处理 $O((n+m)\log(n+m))$，每问 $O(1)$。

### 核心伪代码与附件

```text
minB,maxB = RMQ(B range)
candidates = {minA,maxA,smallest_nonnegative_A,largest_nonpositive_A}
answer = max(min(x*minB, x*maxB) for valid x in candidates)
```

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

## 实现指南

《假期计划》先用限深 BFS 或全源可达性得到“距离至多 $k+1$”，再为每个点保留常数个分数最高候选；组合时必须显式检查四个景点互不相同。《策略游戏》的线段树节点应同时存正数最小/最大、负数最小/最大与零存在性；合并和查询时不要用 0 作“不存在”哨兵。

## 扩展与联系

两题都把大候选集压成常数个代表：依据不是经验，而是“冲突数上界”或“分段单调性”。

## 总结与自检

1. Top 3 的数字 3 从哪里来？
2. 若要选六个互异点，候选数怎样变化？
3. 乘法博弈为何要区分靠近 0 的极值？

## 课后训练建议

假期计划用 n≤10 枚举四元组对拍；策略游戏用区间双重枚举对拍所有符号组合。