10.18 CSP-S模拟赛

· · 个人记录

T1

只考虑连 a_u \leq a_v 的边，把所有边按照边权从小到大排序，跑一遍 dfs 求出最长路即可。

T2

你发现这种要求满足限制的题，且可以通过 x_r - x_l = d_i 构造关系。直接考虑差分约束，如果说出现当前 u,v 距离与之前所求矛盾则无解。根据 \begin{cases}x_r - x_l \leq d_i \\ x_l - x_r \leq -d_i\end{cases} 建边。

T3

T4

首先所有被其它区间完全覆盖的区间一定是要删的。

将所有线段左端点第一关键字右端点第二升序排序，考虑 dp。记 f_{i,j} 表示前 i 个中选了 j 个删除，钦定 i 不删的最长区间覆盖。转移枚举上一个没删的区间。

f_{i,j} = \max\limits_{k < i}\{f_{k,j - (i - k - 1)} + r_i - \max(l_i,r_k)\}

显然我们需要分讨后面的 \max。

那么只需要单调队列维护第二种情况的同时更新第一种即可。