1 条题解

  • 0
    @ 2026-4-30 0:37:32

    solve\texttt{solve}

    考虑枚举走到每一个高速站点后一直走普通,先计算这样能到达的所有。

    这可以看作若干个线段,显然我们的准高速站点不会放在任何一个线段里(除了高速站点)。

    考虑贪心一下,每次往线段右端点的下一个放准高速。记录一下到达这个准高速的剩余时间和准高速到下一个线段前能跑的最长距离。

    对于每一个准高速,计算走普通到达的最远距离,此时又可以看作若干条新的线段,那此时反复地往线段右边放准高速。

    考虑用优先队列维护。以在剩余时间内最多能跑的普通站点数量。为什么不直接用剩余时间,因为你要考虑能跑的长度对能抵达的普通站点也有影响。如果你至多能跑一个站点剩余无穷大时间,那显然也是劣于剩 2A2A 时间但是能跑两个普通站点的。

    每次跑完尽可能远,如果还有距离就当作一个线段从新在线段右边假设建一个准高速站点,然后丢回优先队列里面。

    tips\texttt{tips}

    • 高速站点是经过的每一个普通站点也需要 BB 的代价,准高速同理,而不是两个相邻可停靠的高速或准高速收费 BBCC 的代价;
    • 问的是,所有行驶方案共至多到多少个站点,而不是问一次行驶最多能到多少站点;
    • 不是每个高速站点为左端点的线段都可以往右端点后面塞准高速,上文所说的若干条线段指的是如果两个线段有交集那需要合并。
    • 1

    信息

    ID
    9022
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者