P11985 [JOIST 2025] 比太郎之旅 2 / Bitaro's Travel 2
2026-10-06
简述题意
给定 h×w 的网格,每个格子有一个高度 ai,j,接下来 q 次询问,每次给定两个点 (xs,ys),(xt,yt),求最小跳跃次数。
对于每次跳跃,若当前山峰高度为 x,那么可以跳到 x+L+0.5 的位置。
可以移动任意多次,只要到达的山峰不超过当前高度,并且高度不会发生变化。
题解
考虑如何刻画跳跃,显然越跳月高一定不劣,并且对于当前点来说,可以去到所有 a≤x+L 的位置,这显然可以图论建模,两点间边权为 max(au,av),那么可以走过所有边权 ≤wu+L。
要在图中求两点间最大边权最小值,可以使用 Kruskal 重构树,两点 LCA 即为其最大边权,至于求步数,只需要使用倍增优化跳 top 即可。
