P11232 [CSP-S 2024] 超速检测 题解

M1rai · 2024-10-27 17:11:03 · 题解

前言

场上调这个东西调了 3h，好在最后调出来了。

前情提要 & 笑点解析：ABC368E。

恭喜差分约束成为第一个让我后悔学过的算法。

思路

先把物理的皮去掉，能测出每辆车是否超速的测试仪一定构成一段区间，二分一下把这些区间表示出来即可。

然后就变成了给定一些区间和一些点，求最少选几个点能使每个区间都包含至少一个点。

设 c_i 代表第 i 个测试仪选不选（选是 0，不选是 1），pf_i 代表 c_i 的前缀和。于是一个区间 [l,r] 的限制变成了如下不等式：pf_r-pf_{l-1}<r-l+1。

考虑差分约束跑最短路，最大化这些不等式的解。

由于需要让解合法，还得加上如下限制：pf_i-pf_{i-1}\geq 0、pf_i-pf_{i-1}\leq 1，pf_i\leq m。

于是按上面的式子正常连边就好了，连完会发现边权全是正的，跑 dij 即可，那我们就做完了。很搞笑的做法对吧！