如何确定排列 $p_i$（$2 \le i \le 2n$）的详细题解

问题回顾

已知一个 $2n$ 的排列 $p_1, p_2, \dots, p_{2n}$，但我们不知道它的值。我们获得了一个 $n \times n$ 的网格 $G$，其中

即第 $i$ 行第 $j$ 列存放着排列中下标为 $i+j$ 的元素。

题目保证这样的排列存在且唯一，我们需要根据网格 $G$ 还原出整个排列。

核心观察

网格中出现的所有下标 $i+j$ 的取值范围是：

• 当 $i = j = 1$ 时，$i+j = 2$；
• 当 $i = n, j = n$ 时，$i+j = 2n$。

因此，网格直接给出了 $p_2, p_3, \dots, p_{2n}$ 的全部信息，但唯独缺少 $p_1$，因为没有任何一对 $(i,j)$ 能使 $i+j = 1$（$i,j \ge 1$）。

如何直接读出每一个 $p_k$？

我们只需选择合适的 $(i,j)$，使得 $i+j = k$，即可从 $G_{i,j}$ 获得 $p_k$。由于本题只要求输出排列，我们可以任意选择一种合法的方式读取。下面的取法是最简洁的，它用到了网格的第一行和最后一行。

对于 $2 \le k \le n$

取第一行（$i = 1$），列号 $j = k - 1$。
此时 $i+j = 1 + (k-1) = k$，且因为 $k \le n$，所以 $j = k-1 \le n-1 < n$，属于网格有效列范围。
因此：

直观理解：网格第一行对应 $i=1$，所有和从 $1+1=2$ 到 $1+n=n+1$。
因此第一行覆盖了 $p_2$ 到 $p_{n+1}$。我们只用其中的 $p_2 \dots p_n$，$p_{n+1}$ 留到后面处理。

对于 $n+1 \le k \le 2n$

取最后一行（$i = n$），列号 $j = k - n$。
此时 $i+j = n + (k - n) = k$，并且 $k \ge n+1$ 确保 $j \ge 1$，而 $k \le 2n$ 确保 $j \le n$，均合法。
因此：

直观理解：网格最后一行对应 $i=n$，所有和从 $n+1$（$j=1$）到 $2n$（$j=n$），恰覆盖 $p_{n+1} \dots p_{2n}$。

两张图的覆盖关系

• 第一行给了 $p_2, p_3, \dots, p_{n+1}$
• 最后一行给了 $p_{n+1}, p_{n+2}, \dots, p_{2n}$

实际使用中，我们可以仅用第一行的前 $n-1$ 列得到 $p_2 \dots p_n$，用最后一行的所有列得到 $p_{n+1} \dots p_{2n}$，这样每个 $p_k$ ($k \ge 2$) 都被唯一且明确地读取到。

边界验证

• 当 $k=2$，$G_{1,1} = p_2$，成立。
• 当 $k=n$，$G_{1,n-1} = p_n$，列号 $n-1$ 有效。
• 当 $k=n+1$，$G_{n,1} = p_{n+1}$，成立。
• 当 $k=2n$，$G_{n,n} = p_{2n}$，成立。

唯一未出现的 $p_1$

我们已经确定了 $p_2, p_3, \dots, p_{2n}$，而整个排列是 $1 \sim 2n$ 的一个排列，因此 $p_1$ 就是那个在 $[1, 2n]$ 中唯一没有出现过的整数。

实现时，可以用一个布尔数组 vis[1..2n]，初始均为 false，在读取网格时，对于每个 $G_{i,j}$，设 vis[G_{i,j}] = true。最后扫描 vis，找到仍为 false 的那个下标，它就是 $p_1$。这也正是标准程序中使用的方法。

算法流程

1. 读入 $n$ 和网格 $G$。
2. 初始化一个大小为 $2n+1$ 的数组 p 和布尔数组 used。
3. 对于每个 $i, j$：
   • 读取 $x = G_{i,j}$；
   • 记录 $p[i+j] = x$，并标记 $used[x] = \text{true}$。
4. 按顺序输出 $p_1 \dots p_{2n}$：
   • 若 $p[i] \neq 0$，直接输出（这部分是 $i \ge 2$ 的情况）；
   • 否则（仅 $i=1$ 时发生），在 $1 \sim 2n$ 中找到未使用的数输出，并标记已用。
5. 输出换行。

该算法的时间复杂度为 $O(n^2)$（主要来自读入网格），空间复杂度为 $O(n)$（除去存储网格的 $O(n^2)$，也可以不保存网格而直接边读边处理，但通常题目允许保存）。

为什么这种读法是唯一正确的？

因为题目保证网格对应一个合法的排列，那么对于每个 $k = 2 \dots 2n$，网格中可能存在多个位置 $(i,j)$ 满足 $i+j = k$，但它们必须全部相等（否则与排列的定义矛盾）。因此我们可以任取一个位置来获取 $p_k$。上述方法只是选择了其中最方便的位置，不会产生歧义。

完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n; cin >> n;
    vector<int> ans(2*n+1, 0);
    vector<bool> used(2*n+1, false);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int x; cin >> x;
            ans[i + j] = x;
            used[x] = true;
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (ans[i] != 0) cout << ans[i] << " ";
        else {
            for (int j = 1; j <= n * 2; j++) {
                if (!used[j]) {
                    used[j] = true;
                    cout << j << " ";
                    break;
                }
            }
        }
    }
    cout << "\n";
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t; cin >> t;
    while (t--) solve();
    return 0;
}