03-CSP-S2022可达候选与符号博弈.md 4.5 KB
CSP-S 2022 真题：可达候选压缩与乘法符号博弈
本节目标
学习当答案只选常数个对象时保留少量最优候选，以及把区间乘法极值按符号缩成四类代表值。
前置知识与课前自测
前置：BFS、Top-k、RMQ/稀疏表、极值分类。
- 四个景点互异时，为每个中间点保留前三名候选为何可能足够？
- 固定 $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
精选例题 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)
实现指南
《假期计划》先用限深 BFS 或全源可达性得到“距离至多 $k+1$”，再为每个点保留常数个分数最高候选；组合时必须显式检查四个景点互不相同。《策略游戏》的线段树节点应同时存正数最小/最大、负数最小/最大与零存在性；合并和查询时不要用 0 作“不存在”哨兵。
扩展与联系
两题都把大候选集压成常数个代表：依据不是经验，而是“冲突数上界”或“分段单调性”。
总结与自检
- Top 3 的数字 3 从哪里来？
- 若要选六个互异点，候选数怎样变化？
- 乘法博弈为何要区分靠近 0 的极值？
课后训练建议
假期计划用 n≤10 枚举四元组对拍；策略游戏用区间双重枚举对拍所有符号组合。