自动搬运

查看原文

来自洛谷，原作者为

	周子衡 Shadow is the light!

搬运于2025-08-24 22:38:51，当前版本为作者最后更新于2022-05-14 18:05:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

• 题意： 给定 $n\times n$ 正整数方阵 $A$，保证 $1\sim n^2$ 的每个正整数都在其中出现过。你每次可以交换 $A$ 中同行 / 同列的两个元素。你需要用尽可能少的交换次数将 $A$ 变为另一个方阵 $B$，其中 $B_{i,j}=(i-1)\times n+j$，并构造一组方案。
• 由于本题找到最优解十分困难，你的方案步数只要不超过一定范围即可。具体地，设 $k(C)$ 表示把某个 $n\times n$ 方阵 $C$ 变为 $B$ 的最小步数，记 $k_0$ 为在全部的 $C$ 中，$k(C)$ 的最大值。你只需要构造出一种不超过 $k_0$ 步的方案即可通过。
• $n\leq 1000$。

好题。

我们先来试着确定一下 $k_0$ 的值。很容易观察到 $n^2-1 \leq k_0\leq 2n^2$，也就是说 $k_0$ 和 $n^2$ 是同阶的。到底在 $n^2$ 附近还是 $2n^2$ 附近呢？或者都不是？通过直觉（或者是实验），可以猜想应该在 $2n^2$ 附近。读者可以来试着自己证明一下。

我们先来说明 $k_0\geq 2(n^2-n)$。

考虑构造两张有向图 $R,C$。对 $A$ 中的每个元素，我们在 $R$ 中从它所在的行向它应该在的行连一条边；在 $C$ 中从它所在的列向它应该在的列连一条边。可以知道，$R$ 和 $C$ 都是欧拉图。对欧拉图 $G$，定义 $\mathrm{cyc}(G)$ 表示能将 $G$ 拆分出的最大环数。可以发现，$\mathrm{cyc}$ 的最小值为 $n$，最大值为 $n^2$，且操作结束时 $R,C$ 的 $\mathrm{cyc}$ 值都会达到 $n^2$；一次操作只会对 $R,C$ 中的某一个有影响，且对有影响的那个图，它的 $\mathrm{cyc}$ 值至多只会变化 $1$。我们只需要说明存在某个 $A$ 使得开始的时候 $R,C$ 的 $\mathrm{cyc}$ 值都只有 $n$，就可以说明 $k_0\geq 2(n^2-n)$。这是简单的：把目标方阵循环下移一格再循环右移一个，得到的方阵就满足条件。

（“最大环数”这个概念在这里也有出现过，读者可以比较一下。）

好的，接下来我们将构造地证明：对任意方阵 $A$，都存在 $2(n^2-n)$ 步的复原方式，从而解决本题。

考虑一行一行地复原。首先可以知道：任意时刻我们都可以在 $2$ 步之内把某个元素还原到它应在的位置上。同时，当前 $n-1$ 行都复原时，复原最后一行至多需要 $n-1$ 次操作。计算一下可以发现，只要我们复原除了最后一行的某一行时能少用 $1$ 次操作，我们就解决了这题。

当复原某一行时，我们只看应该出现在这一行的所有元素。对每个该行元素，从它在的列向它应在的列连一条边，形成一张有向图。这个有向图每个点都有一条入边，则必有一个环。找到这个环，设环长为 $c$，我们先用至多 $c$ 次操作把这 $c$ 个点对应的元素都转移到该行上，然后再在行内用 $c-1$ 次操作复原这 $c$ 个元素。剩下的元素每个 $2$ 次复原即可。

关于实现细节：本题要求 $O(n^2)$ 的时间复杂度，可以在操作的同时维护每个元素所在的位置。注意常数。

后记

这题题解鸽了挺久的，谢罪 QaQ

以及，代码就鸽掉了 QaQ