P14055 [POI 2015 R3] 路标 Direction signs 题解
:::::info[题目基本信息]
考察：拓扑排序，bitset（省选/NOI-）。
题目简介：
有
数据范围：
-
1\le n\le 1000 -
1\le m\le 200 -
\forall i\in[1,n],j\in[1,m],1\le d_{i,j}\le 10^6 - 保证最多能选出的路牌数量不低于
\dfrac{n}{5} 。
::::: 保证最多能选出的路牌数量不低于\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) 。
code