浅谈有偏序限制的排列字典序问题

KSCD_ · 2025-09-28 07:38:41 · 个人记录

做 AGC001F 的时候想的，结果越想越乱，总结一下。

• 逆排列：对 p 来说满足 q_{p_i}=i 且 p_{q_i}=i 的排列 q。事实上两个条件等价，都是值与下标互换。
• 引理：最小化 p 的字典序，相当于最大化其逆排列 q 的逆序字典序。

考虑 p 字典序最小在 q 上是什么，发现要让 1 尽可能靠前，再让 2 尽可能靠前，以此类推。因此倒着进行这个过程，直到只能填 1 时才填 1，否则在只能填 2 时填 2，这对应其字典序最大。

有以下三个问题：

• 要求排列中 i 在 j 之前出现，求字典序最小的排列 p。

相当于字典序最小的拓扑序，因此直接由 i 向 j 连边，每次取入度为零的最小值放在 p 开头即可。

• 要求 p_i<p_j，求字典序最小的排列 p。

比较自然的想法是 i 向 j 连边，之后每次取最小编号并赋值。然而这是错的，容易用 n=3,(3,1) 直接卡掉。

这是因为该过程并没有尽可能最小化 p_1，而是最小化了 p 的逆排列 q 的字典序。然而根据引理，实际上要做的是最大化 q 的逆序字典序。

该限制转化到 q 上为 i 在 j 之前出现，求逆序字典序最大的排列 q，根据上一题这需要由 j 向 i 连边，并倒着确定每个 q 的取值，之后再转化回原排列 p。

然后发现这次的拓扑排序部分与上题相比取了个逆，这与 q 转化回 p 的取逆抵消了。因此本题可以直接由 j 向 i 连边，每次取最大编号并赋值， 这与上一段中的做法等价。

• 要求排列中 i 在 j 之前出现，之后要求先让 1 尽可能靠前，在此前提下让 2 尽可能靠前，以此类推。

再次考虑逆排列 q，发现这其实就是 q_i\lt q_j，求字典序最小的排列 q，只需要对上题的结果取逆排列即可得到答案，这可以直接在拓扑排序部分修改。本题有原题 HDU4857。