P14055 [POI 2015 R3] 路标 Direction signs 题解

保证最多能选出的路牌数量不低于 $\dfrac{n}{5}$ 这一条件引导我们考虑先随机一个 $u$ 并钦定它在最终的构造方案中（错误率有 $\dfrac{4}{5}$，为方便估计正确率我们可以将随机三次都错误的概率近似成 $\dfrac{1}{2}$）这样我们随机 $\Theta(1)$ 次就有很大概率随机到正确答案。
设 $\Delta d_{i,j}$ 表示实际未下取整与 $d_{i,j}$ 的值的差（容易得到 $\Delta d_{i,j}\in[0,1)$），同时设 $x_i$ 表示路标 $i$ 的坐标，$y_j$ 表示城市 $j$ 的坐标， 我们容易得到：
$y_j-x_i-\Delta d_{i,j}=d_{i,j}$ 这个式子中 $y_j$ 和 $x_i$ 的范围我们是一点也不知道，所以我们考虑消元消去它们。
由于 $u$ 的这个式子我们钦定已经成立，所以我们考虑令 $i$ 所对应的式子和 $u$ 所对应的式子相减得到：
$\begin{aligned}a_{i,j}&=d_{i,j}-d_{u,j}\\&=(y_j-x_i-\Delta d_{i,j})-(y_j-x_u-\Delta d_{u,j})\\&=x_u+\Delta d_{u,j}-x_i-\Delta d_{i,j}\end{aligned}$ 我们观察到我们只需要再找到另一个 $a_{i,j_2}$ 与其相减即可，为了令其计算出的都不是负数所以我们找到该值最小的 $idx_i$ 与其相减得到：
$\begin{aligned}b_{i,j}&=a_{i,j}-a_{i,idx_i}\\&=(x_u+\Delta d_{u,j}-x_i-\Delta d_{i,j})-(x_u+\Delta d_{u,idx_i}-x_i-\Delta d_{i,idx_i})\\&=\Delta d_{u,j}+\Delta d_{i,idx_i}-\Delta d_{i,j}-\Delta d_{u,idx_i}\end{aligned}$ 那么 $b_{i,j}$ 的值域是多少呢？
因为 $idx_i$ 能使得 $a_{i,idx_i}$ 最小，所以 $b_{i,j}\ge 0$，又因为 $\Delta d_{i,j}\in[0,1)$，所以 $b_{i,j}<2$，又因为 $d_{i,j}\in\mathbb Z$，所以 $a_{i,j}\in\mathbb Z$，进一步地 $b_{i,j}\in\mathbb Z$，所以最终 $b_{i,j}\in\{0,1\}$！
现在存在 $b_{i,j}$ 不满足这个条件的 $i$ 一定不能放在答案里，那么我们对 $b_{i,j}$ 的定义式进行变形得到：
$\Delta d_{i,j}=\Delta d_{u,j}+\Delta d_{i,idx_i}-b_{i,j}-\Delta d_{u,idx_i}$ 现在我们要开始填数了，定 $i$，要求每个 $j$ 都满足要求，由于 $\Delta d_{i,idx_i}$ 和 $\Delta d_{u,idx_i}$ 这两项与 $j$ 无关，可以当做定值，又由于 $\Delta d_{i,j}\in[0,1)$，那么我们就得到 $i$ 合法的充要条件：
$\text{D}_{j\in[1,n]}(\Delta d_{u,j}-b_{i,j})<1$ 其中 $\displaystyle D_i(x)=\max_{i}(x)-\min_{i}(x)$。
利用我们得到的 $b_{i,j}$ 的值域（$b_{i,j}\in\{0,1\}$），我们容易得到最终的条件：
$\max_{j\in[1,n],b_{i,j}=0}\Delta d_{u,j}<\min_{j\in[1,n],b_{i,j}=1}\Delta d_{u,j}$ 设 $S_i=\{j|j\in[1,n],b_{i,j}=1\}$，那么构造的集合合法当且仅当里面所有的 $S_i$ 两两包含，否则条件会产生矛盾。
这样这道题就简单了，给所有的满足 $S_i\subseteq S_j$ 的 $(i,j)$ 连边（建出双向边，即 $S_i=S_j$ 时只保留一个方向）然后跑拓扑排序，找到最长路即可。
这时时间复杂度是 $\Theta(n^2m)$ 的，能过 $60$ 分。
注意到 $S_i\subseteq S_j$ 这个条件可以使用 bitset 优化，那么时间复杂度会除以一个 $w$，就可以通过了。
时间复杂度为 $\Theta(\dfrac{n^2m}{w})$，空间复杂度为 $\Theta(nm)$。