Table Recovery

题目描述

Bessie 有一张 $N\times N$（$1\le N\le 1000$）的加法表，其中第 $r$ 行第 $c$ 列的整数为 $r+c$，对所有 $1\le r,c\le N$ 都成立。例如当 $N=3$ 时，这张表如下： 2 3 4 3 4 5 4 5 6 不幸的是，Elsie 拿到了这张表，并通过以下三类操作（可执行任意多次）对其进行了置换。 交换两行 交换两列 选择表中都出现过的两个值 $a$ 和 $b$，然后同时将表中所有的 $a$ 变为 $b$，并将所有的 $b$ 变为 $a$。 Elsie 总是按操作类型递增的顺序执行操作；也就是说，她会先执行任意多次（也可能一次都不执行）第 $1$ 类操作，然后执行任意多次第 $2$ 类操作，最后执行任意多次第 $3$ 类操作。 请帮助 Bessie 还原在 Elsie 完成所有第 $1$ 类与第 $2$ 类操作之后、但尚未进行任何第 $3$ 类操作之前，表可能处于的某一种状态。可能存在多个答案，此时你应输出字典序最小的那个。 比较两张表的字典序时，按自然顺序（从上到下逐行读取，每行从左到右）读取两张表，比较它们第一次出现不同的位置上的元素大小。

输入格式

第一行包含 $N$。 接下来 $N$ 行每行包含 $N$ 个整数，表示 Elsie 置换后得到的 Bessie 的加法表。

输出格式

输出在完成所有第 1 类与第 2 类操作之后、但尚未进行任何第 3 类操作之前，表的字典序最小的可能状态。保证答案存在。

1
2

2

3
3 4 2
5 2 3
6 3 5

4 2 3
5 3 4
6 4 5

6
8 10 5 6 7 4
12 11 10 4 8 2
5 4 6 7 9 8
10 2 4 8 5 12
6 8 7 9 3 5
4 12 8 5 6 10

7 5 8 9 10 6
4 2 5 6 7 3
8 6 9 10 11 7
5 3 6 7 8 4
9 7 10 11 12 8
6 4 7 8 9 5

提示

无论 Elsie 执行什么操作，这张表都不会改变。 这里是一种 Elsie 可能执行的操作序列。 2 3 4 3 4 5 4 5 6 ->（操作 1：交换第 2 列与第 3 列） 2 4 3 3 5 4 4 6 5 ->（操作 1：交换第 1 列与第 2 列） 4 2 3 5 3 4 6 4 5 ->（操作 3：交换值 2 与 3） 4 3 2 5 2 4 6 4 5 ->（操作 3：交换值 3 与 4） 3 4 2 5 2 3 6 3 5 注意：下面这种也是在第 1 类与第 2 类操作后可能得到的表状态，但它不是字典序最小的，因为第一行的第二个元素比正确答案中的更大。 4 6 5 3 5 4 2 4 3 评分： 输入 4-5：$N\le 6$ 输入 6-7：$N\le 8$ 输入 8-11：$N\le 100$ 输入 12-15：无额外限制。 题目署名：Benjamin Qi

标签: USACO|2025|Silver

来源

USACO|2025|Silver