Moe's CF Life

哈喽，主人！~ 看到这道题是不是有点小困惑呀？没关系，让本猫娘来帮你理清思路，一步一步把这道题解决掉吧，喵~ ฅ'ω'ฅ

题目大意

这道题是说，有一个叫 Kristina 的女孩子，她有一个长度为 $n$ 的排列 (Permutation) $p$ 。

喵呜，先解释一下什么是排列哦！一个长度为 $n$ 的排列，就是说一个序列里包含了从 $1$ 到 $n$ 的所有整数，而且每个整数都只出现一次。比如 [1, 3, 2] 就是一个长度为 3 的排列，但 [1, 2, 2] 就不是啦，因为 2 出现了两次。

Kristina 呢，她把这个排列 $p$ 写了 $n$ 遍。但每次写的都缺了点东西：

第 1 次写的时候，她会跳过原始排列的第 1 个元素 $p_1$ 。
第 2 次写的时候，她会跳过原始排列的第 2 个元素 $p_2$ 。
...
第 $i$ 次写的时候，她会跳过原始排列的第 $i$ 个元素 $p_i$ 。

这样一来，她就得到了 $n$ 个长度都是 $n-1$ 的序列。

举个例子，如果原来的排列是 $p = [4, 2, 1, 3]$ ：

跳过 $p_1=4$ ，得到 [2, 1, 3]
跳过 $p_2=2$ ，得到 [4, 1, 3]
跳过 $p_3=1$ ，得到 [4, 2, 3]
跳过 $p_4=3$ ，得到 [4, 2, 1]

现在，题目会把这 $n$ 个残缺的序列（顺序是打乱的）给我们，我们的任务就是像侦探一样，根据这些线索，把原始的排列 $p$ 给找出来！是不是很有趣，喵？

题解方法

这道题看起来有点像拼图游戏，对吧？别急，让本猫娘带你找到最关键的那一块拼图！

我们来仔细观察一下上面那个例子里生成的序列：

[2, 1, 3]
[4, 1, 3]
[4, 2, 3]
[4, 2, 1]

让我们把目光集中在每个序列的第一个元素上，喵~

发现了什么没有？数字 4 出现了 3 次，而数字 2 只出现了 1 次。

我们来思考一下为什么会这样。原始排列是 $p = [p_1, p_2, ..., p_n]$ 。

当跳过 $p_1$ 时，生成的序列是 [p_2, p_3, ..., p_n]，它的开头是 $p_2$ 。
当跳过 $p_2$ 时，生成的序列是 [p_1, p_3, ..., p_n]，它的开头是 $p_1$ 。
当跳过 $p_3$ 时，生成的序列是 [p_1, p_2, p_4, ..., p_n]，它的开头是 $p_1$ 。
...
当跳过 $p_n$ 时，生成的序列是 [p_1, p_2, ..., p_{n-1}]，它的开头还是 $p_1$ 。

看出来了吗？在所有 $n$ 个生成的序列里，除了那个跳过了 $p_1$ 的序列，其他所有 $n-1$ 个序列的开头都是 $p_1$ ！

因为题目保证了 $n \ge 3$ ，所以 $n-1 \ge 2$ 。这意味着， $p_1$ 这个数字，在所有输入序列的开头位置，会出现 $n-1$ 次，而其他数字最多只会出现 1 次。

破案了，喵！

所以我们的解题步骤就是：

找到 $p_1$ ：我们统计一下所有输入序列的第一个数字，那个出现了超过一次（其实就是 $n-1$ 次）的数字，必然就是原始排列的第一个元素 $p_1$ ！
找到剩下的部分：我们已经知道 $p_1$ 了，那剩下的 [p_2, p_3, ..., p_n] 在哪里呢？还记得吗？这个序列恰好是那个唯一不以 $p_1$ 开头的序列！
拼合：我们在所有输入序列中找到那个不以 $p_1$ 开头的序列，把它原封不动地接在 $p_1$ 后面，就得到了完整的原始排列啦！

是不是很简单呀？就像猫咪能从一堆毛线球里准确地找到自己最喜欢的那一个，我们也能从一堆数字里找到那个最特别的 $p_1$ ，喵~

题解

下面是 C++ 的代码实现，本猫娘加上了详细的注释，方便主人理解哦~

cpp

#include <iostream>
#include <vector>
#include <numeric>

void solve() {
    int n;
    std::cin >> n;

    // 用一个二维 vector 来存储 n 个长度为 n-1 的序列，喵
    std::vector<std::vector<int>> sequences(n, std::vector<int>(n - 1));
    
    // 用一个数组来统计每个数字在所有序列的“首位”出现的次数
    // 数组大小是 n+1，这样就可以用 1 到 n 的下标了，很方便！
    std::vector<int> first_element_counts(n + 1, 0);

    // 读入 n 个序列
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n - 1; ++j) {
            std::cin >> sequences[i][j];
        }
        // 对于每个读入的序列，我们只关心它的第一个元素
        // 增加它在首位出现的计数
        first_element_counts[sequences[i][0]]++;
    }

    // 寻找那个出现了 n-1 次的“首位元素”，也就是 p1
    int p1 = -1;
    for (int i = 1; i <= n; ++i) {
        // 因为只有 p1 会出现超过1次，所以只要找到这个数就行啦
        if (first_element_counts[i] > 1) {
            p1 = i;
            break; // 找到了就不用再找了，喵~
        }
    }

    // 打印我们找到的 p1，这是最终答案的第一个数字
    std::cout << p1 << " ";

    // 现在要寻找剩下的部分 [p2, p3, ..., pn]
    // 这个序列是唯一一个不以 p1 开头的序列
    int rest_sequence_idx = -1;
    for (int i = 0; i < n; ++i) {
        if (sequences[i][0] != p1) {
            rest_sequence_idx = i; // 找到这个序列的索引
            break;
        }
    }

    // 把这个找到的序列原封不动地打印出来，就是排列的剩余部分
    for (int j = 0; j < n - 1; ++j) {
        std::cout << sequences[rest_sequence_idx][j] << (j == n - 2 ? "" : " ");
    }
    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;
}

知识点介绍

这道题虽然不难，但里面用到的思想可是很重要的哦！

排列 (Permutation) 排列是组合数学中的一个基本概念。在算法竞赛中，与排列相关的题目非常多，理解它的性质是解决这类问题的基础。
频率计数 (Frequency Counting) 这是本题解法的核心。我们通过统计每个数字在特定位置（这里是首位）出现的次数来找到突破口。频率计数是一个非常非常常用的技巧！
- 数组/哈希表：当数字的范围不大且固定时（比如本题的 1 到 n），可以直接用一个数组来计数，简单高效。如果数字范围很大或者不是整数，我们通常会使用哈希表（在 C++ 中是 std::map 或 std::unordered_map）。
观察与推导 (Observation and Deduction) 算法竞赛中，很多题目并不是让你直接套用某个复杂的算法模板。相反，它们需要你像小猫咪观察毛线球一样，仔细分析题目的条件和样例，发现其中隐藏的规律和性质。本题就是一个绝佳的例子，通过观察“首位元素”的规律，问题就迎刃而解了。培养这种观察和逻辑推导能力，对成为解题高手至关重要，喵！

好啦，这次的讲解就到这里啦！主人有没有完全明白呢？如果有任何问题，随时可以再来问本猫娘哦！ฅ/ᐠ. ̫ .ᐟ\ฅ

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍