自动搬运

查看原文

来自洛谷，原作者为

	Exp10re My awAKen Dream.

搬运于2025-08-24 23:09:42，当前版本为作者最后更新于2025-02-14 20:10:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

神秘转化题。

前置知识：稳定婚姻问题。

解题思路

考虑对于一个任意排列 $p$，其不能作为一个合法答案的充要条件：$\exist 1\leq i,j \leq n,A_{j,p_i}\gt A_{i,p_i},A_{j,p_j}\gt A_{j,p_i}$，此时设 $p_j \leftarrow p_i$ 一定是一个更优的答案。

钦定 $\exist 1\leq i,j \leq n,A_{j,p_i}\gt A_{i,p_i},A_{j,p_j}\gt A_{j,p_i}$ 时 $j$ 与 $p_i$ 匹配称为更优匹配，不难发现 $p$ 为一个答案的条件为 $p$ 中不存在更优匹配。

注意到这个是稳定婚姻形式，考虑对每一行以及每个数钦定一个优先级。整理以上两个条件可以得到两个优先级：

• $A_{j,p_i}\gt A_{i,p_i}$ 表示数 $p_i$ 会倾向于 $p_i$ 位置较靠后的行。
• $A_{j,p_j}\gt A_{j,p_i}$ 表示行 $j$ 会倾向于行 $j$ 位置较靠前的数。

根据这个倾向求得的匹配必定是一个合法解，根据稳定婚姻的有解性可以得知其必定存在合法解。

时间复杂度 $O(TN^2\log N)$。