- 题意： 给定 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 步的方案即可通过。
-
好题。
我们先来试着确定一下 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