lessons/课程/12-历年真题/03-CSP-S2022可达候选与符号博弈.md

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

本节目标

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

前置知识与课前自测

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

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

答案

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

问题动机

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

精选例题 1：假期计划

来源、题意与范围

• 洛谷-P8817 假期计划
• $n\le2500,m\le10^4$；从家 1 访问四个不同景点 A、B、C、D 后回家，每段最多经过 $k+1$ 条边，最大化分数和。

Hint 1

先求任意点对是否能在 k+1 条边内到达。

Hint 2

枚举中间 B、C；A 必须同时接家与 B，D 同时接 C 与家。

Hint 3

每个 B/C 只保留分数最高的三个端点候选。

Observations、Editorial 与证明

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

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

核心伪代码与附件

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 附件

精选例题 2：策略游戏

来源、题意与范围

• 洛谷-P8818 策略游戏
• $n,m,q\le10^5$；每问 L 从 A 区间先选 x，Q 从 B 区间选 y，L 最大化而 Q 最小化乘积 xy。

Hint 1

固定 x，Q 只会选择 B 的最小值或最大值。

Hint 2

A 中只需最大/最小、最小非负、最大非正四类候选。

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)$。

核心伪代码与附件

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 附件

实现指南

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

扩展与联系

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

总结与自检

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

课后训练建议

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