题解：P11232 [CSP-S 2024] 超速检测（民间数据）

26 Oct, 2024 11:06 PM +08:00

挺麻烦的一个题，赛时调了 $2h$ 。

$O(nm)$ 算出来第一个输出，然后 $O(2^mnm)$ 枚举删哪些测速点，可以骗到一点分。

对 $p$ 从小到大排序，设 $v_{i, q}$ 是第 $i$ 辆车在 $q$ 点的速度，则对于第 $i$ 辆车 $A$ ：

如果 $a_i<0$ ， $A$ 超速当且仅当 $v_{i, P}>V$ ，其中 $P$ 是最小的 $p_j$ 满足 $p_j\space{\geq}{\space}d_i$
如果 $a_i\space{\geq}\space0$ ， $A$ 超速当且仅当 $v_{i, p_m}>V$

对于 $a_i<0$ ，显然可以二分，整体时间复杂度 $O(n\log{m})$ 。

$p$ 是有序的，可以把每辆车的测超速范围看成一个线段 $X$ ，具体来说，对于第 $i$ 辆车：

如果 $a_i<0$ ， $X_i=[P,Q]$ ，其中 $P$ 是最小的 $j$ 满足 $v_{i, p_j}>V$ ， $Q$ 是最大的 $j$ 满足 $v_{i, p_j}>V$ 。
如果 $a_i\space{\geq}\space0$ ， $X_i=[P,m]$ ，其中 $P$ 是最小的 $j$ 满足 $v_{i, p_j}>V$ 。

因为 $v_{i, p_j}$ 在 $p_j\space{\geq}{\space}d_i$ 上具有单调性，所以二分求 $X$ ，时间复杂度 $O(n\log{m})$ 。

此时问题转化成 P1803 线段覆盖，整体时间复杂度 $O(n\log{m})$ 。

代码略（

本文最初发表于 Luogu，于 2026-04-19 同步至本站。