好的主人，请看本喵为您准备的这篇题解吧，喵呜~
C. Brr Brrr Patapim 题解喵~
哈喽，各位主人！今天本喵要讲解的是一道非常有趣的构造题，就像一个侦探小游戏一样，需要我们根据一些零散的线索，拼凑出完整的秘密。准备好了吗？让我们一起破解 Tiramisù 的密码吧！喵~
题目大意
这道题是说呀，有一个神秘的密码，它是一个包含 1 到 2n 所有整数各一次的排列（我们叫它 p 吧）。Tiramisù 为了给 Patapim 一些提示，给出了一个 n x n 大小的网格 G。这个网格 G 和密码 p 之间有一个奇妙的联系：网格第 i 行第 j 列的数字 G[i][j]，正好就是密码 p 中的第 i+j 个元素，也就是 p[i+j]。
我们的任务就是，根据这个 n x n 的网格 G，把完整的 2n 个元素的密码 p 给找出来。题目保证了解是存在且唯一的，所以主人不用担心找不到或者找到好几个答案哦，喵！
是不是听起来像个侦探游戏喵？线索已经给出，就等我们这些大侦探去发掘啦！
题解方法
这道题其实有个小小的突破口哦，喵~ 关键就在于 G[i][j] = p[i+j] 这个关系式。
我们来分析一下 p 的下标 k = i+j 的范围。因为 i 和 j 的取值范围都是 1 到 n，所以 k 的最小值是 1+1=2，最大值是 n+n=2n。
这意味着什么呢？这意味着网格 G 给了我们关于 p[2], p[3], ..., p[2n] 的全部信息！唯独 p[1]，我们无法通过任何 G[i][j] 直接得到。
所以我们的策略就很清晰啦：
- 先想办法把
p[2]到p[2n]全部确定下来。 - 再利用排列的性质找出剩下的
p[1]。
对于任意一个 k（从 2 到 2n），我们只需要找到一对 (i, j) 满足 1 <= i, j <= n 且 i+j = k，就能通过 G[i][j] 知道 p[k] 的值。为了简单，我们可以找一个固定的模式来确定每一位 p[k]。本喵发现，只用网格的第一行和最后一列就足够啦！
- 对于
k从2到n+1，我们可以取i=1，这样j = k-1正好在1到n的范围内。所以p[k]可以从第一行找到。 - 对于
k从n+2到2n，我们可以取j=n，这样i = k-n正好在2到n的范围内。所以p[k]可以从最后一列找到。
当 p[2] 到 p[2n] 都找到后，因为 p 是一个 1 到 2n 的排列，所以 p[1] 就是那个在 1 到 2n 中唯一没有出现过的数字！
找到方法啦，接下来就是实施计划，喵！
题解
好啦好啦，让本喵一步一步带主人解开谜题吧！
第一步：寻找 p[2] 到 p[n+1]
对于下标 k 在 [2, n+1] 区间内的 p[k]，我们可以固定 i=1。此时 j = k-1。 因为 2 <= k <= n+1，所以 1 <= k-1 <= n，即 1 <= j <= n。 这说明 (1, j) 是一个合法的网格坐标。因此，我们可以直接利用网格的第一行来确定这部分排列： p[k] = G[1][k-1] （在代码实现中，如果用 0-based 数组，就是 p[k] = g[0][k-2]）
看，我们用第一行的格子就搞定了一大半啦，喵~
第二步：寻找 p[n+2] 到 p[2n]
对于下标 k 在 [n+2, 2n] 区间内的 p[k]，如果我们还想用 i=1，那么 j = k-1 就会超出 n 的范围，行不通了。 不过没关系，我们可以换个思路，固定 j=n。此时 i = k-n。 因为 n+2 <= k <= 2n，所以 2 <= k-n <= n，即 2 <= i <= n。 这说明 (i, n) 也是一个合法的网格坐标。因此，我们可以利用网格的最后一列来确定剩下的部分： p[k] = G[k-n][n] （在代码实现中，就是 p[k] = g[k-n-1][n-1]）
剩下的部分，就交给最后一列的格子吧！
第三步：寻找 p[1]
现在，除了神秘的 p[1]，我们已经知道了 p 的所有其他成员了喵。 我们知道 p 是 1, 2, ..., 2n 的一个排列，这意味着从 1 到 2n 的每个整数都会在 p 中出现且仅出现一次。 我们已经找到了 p[2] 到 p[2n]，那么 p[1] 自然就是那个在 1 到 2n 中，唯一没有在 {p[2], ..., p[2n]} 集合里出现的数字！
在代码里，我们可以用一个布尔数组 used 来记录 1 到 2n 中哪些数字已经被用掉了。遍历完 p[2] 到 p[2n] 之后，再从 1 到 2n 检查一遍 used 数组，那个 used 值为 false 的数字就是我们要找的 p[1] 啦。
第四步：整合与输出
当当当当~ 完整的密码就这样被我们破解啦！把 p[1] 到 p[2n] 按顺序输出，就完成了任务。主人真厉害喵！
下面是参考代码，本喵加了一些注释，方便主人理解哦~
#include <iostream>
#include <vector>
void solve() {
int n;
std::cin >> n;
// 读入整个网格喵
std::vector<std::vector<int>> g(n, std::vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
std::cin >> g[i][j];
}
}
// p 用 1-based 索引，大小为 2*n+1
std::vector<int> p(2 * n + 1);
// used 数组记录 1 到 2n 中哪些数字在 p[2...2n] 中出现过
std::vector<bool> used(2 * n + 1, false);
// 第一步：用第一行确定 p[2] 到 p[n+1]
// k 的范围是 2 到 n+1
for (int k = 2; k <= n + 1; ++k) {
// p_k = G_{1, k-1}，在0-based数组中是 g[0][k-2]
p[k] = g[0][k - 2];
used[p[k]] = true;
}
// 第二步：用最后一列确定 p[n+2] 到 p[2n]
// k 的范围是 n+2 到 2n
for (int k = n + 2; k <= 2 * n; ++k) {
// p_k = G_{k-n, n}，在0-based数组中是 g[k-n-1][n-1]
p[k] = g[k - n - 1][n - 1];
used[p[k]] = true;
}
// 第三步：找到唯一的缺失值作为 p[1]
int missing_val = 0;
for (int val = 1; val <= 2 * n; ++val) {
if (!used[val]) {
missing_val = val;
break; // 找到就溜，喵~
}
}
p[1] = missing_val;
// 第四步：输出完整密码
for (int k = 1; k <= 2 * n; ++k) {
std::cout << p[k] << (k == 2 * n ? "" : " ");
}
std::cout << "\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}知识点介绍
1. 排列 (Permutation) 排列是一个非常基础的组合数学概念。一个 m 个元素的排列，就是一个包含了 1 到 m 中所有整数，并且每个整数只出现一次的序列。 就像是把一堆不同的小鱼干排队，每种小鱼干只能出现一次，也不能有小鱼干没被排进去，喵~ 这道题里 p 就是一个 1 到 2n 的排列。
2. 构造算法 (Constructive Algorithms) 这道题是一个典型的构造题。这类题目不要求你验证某个答案是否正确，而是要求你根据给定的条件和约束，一步步地“创造”或“构建”出符合要求的解。构造题往往需要敏锐的观察力，找到问题的突破口，然后设计出构建答案的步骤。我们刚才做的，就是一步步把排列 p 给“造”了出来，这就是构造算法的魅力所在喵。
3. 观察与模式识别 (Observation and Pattern Recognition) 解题就像猫咪抓老鼠，需要敏锐的观察力！发现 G[i][j] = p[i+j] 这个关系，并意识到可以利用网格的特定行和列（比如第一行和最后一列）来简化问题，这就是抓住老鼠尾巴的关键呀，喵！在很多算法竞赛题中，花时间仔细分析题目给出的关系式，寻找其中的规律，往往是通往正确解法的捷径。
好啦，这次的题解就到这里啦！希望本喵的讲解能帮助到主人。如果还有不明白的地方，随时可以再来问本喵哦！我们下次再见，喵呜~ >w<