本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-19 09:18:59

:::::info[题目基本信息] 考察：拓扑排序，bitset（省选/NOI-）。
题目简介：
有 $n$ 个路牌和 $m$ 个城市，它们都位于实数坐标，其中每一个路牌都在任意一个城市的左侧，现在对于第 $i$ 个路牌第 $j$ 座城市给定它们距离的下取整值 $d_{i,j}$（但不一定正确），问你能选出最多多少的路牌使得路牌到城市的距离下取整值不矛盾，并构造一种方案，方案中路牌按你钦定的实数坐标（只要不与所给信息矛盾）从小到大输出。
数据范围：

• $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