F. Mathematical Analysis Rocks! - 题解

比赛与标签

比赛: Codeforces Round 116 (Div. 2, ACM-ICPC Rules) 标签: constructive algorithms, implementation, math 难度: *1200

喵喵，这道题在说什么呀？

各位同学晚上好喵~ 欢迎来到猫娘的算法小课堂！今天我们要解决的是一道关于寻找好朋友关系的有趣问题，听起来就很温馨是不是呀？

这道题是这样描述的：有 n 个学生，每个学生 i 都有一个最好的朋友 p[i]。这种好朋友关系是唯一的，也就是说，p 数组其实是 1 到 n 的一个排列组合。

他们有一个神奇的复习方法：

第一天：每个学生 i 看自己的笔记本。
第二天早上：每个学生会把自己的笔记本传给自己的好朋友 p[i]。所以第二天，是学生 p[i] 在看学生 i 的笔记本。
第三天早上：笔记本继续传递，学生 p[p[i]] 会拿到学生 i 的笔记本。
第四天早上：笔记本又传了一次，学生 p[p[p[i]]] 会拿到学生 i 的笔记本。

我们并不知道这个神秘的 p 数组（好朋友关系）是什么。但是，我们有两个线索：

数组 a：a_i 表示在第三天时，拿到学生 i 的笔记本的人是谁。
数组 b：b_i 表示在第四天时，拿到学生 i 的笔记本的人是谁。

我们的任务，就是根据这两个线索 a 和 b，把这个 p 数组给找出来！是不是很有趣的推理游戏呢，喵~

来和咱一起分析一下吧！

这道题看起来有点绕，但只要我们把逻辑理清楚，就会发现它其实是一只很温顺的小猫咪~

首先，我们来把题目中的信息翻译成数学语言，这样就清晰多啦！根据笔记本的传递规则：

第三天，学生 i 的笔记本会传到 p[p[i]] 手里。
题目又告诉我们，第三天拿到学生 i 笔记本的是 a_i。
所以，喵~ 我们得到了第一个关键等式：p[p[i]] = a_i

同样地，我们看第四天：

第四天，学生 i 的笔记本会传到 p[p[p[i]]] 手里。
题目告诉我们，第四天拿到学生 i 笔记本的是 b_i。
所以，我们得到了第二个关键等式：p[p[p[i]]] = b_i

现在我们手里有两个宝贝等式了，要怎么用它们来找到 p 呢？看呐看呐！b_i 可以写成 p[ p[p[i]] ] 的形式。我们把第一个等式 p[p[i]] = a_i 代入到第二个等式里，会发生什么奇妙的事情呢？

b_i = p[ (p[p[i]]) ] 将 p[p[i]] 替换为 a_i，就得到： b_i = p[a_i]

喵呀！我们找到了一个超级棒的关系：p[a_i] = b_i！

这个关系式告诉我们：对于任意一个学生 i（1 到 n），学生 a_i 的好朋友是学生 b_i。

因为题目保证了 a 数组是一个 1 到 n 的排列，这意味着当我们把 i 从 1 遍历到 n 时，a_i 的值也会不重不漏地覆盖 1 到 n 所有的学生。这样，我们就能确定出每一个学生的好朋友是谁了！

举个例子，当 i=1 时，我们知道了 p[a_1] = b_1；当 i=2 时，我们知道了 p[a_2] = b_2……以此类推，直到 i=n，我们就能把 p 数组的每一个位置都填满啦！

那么在实现的时候，我们可以这样做：遍历 i 从 1 到 n，然后直接设置 p[a_i] = b_i。但是，为了更方便地对 p 数组进行赋值（比如我们想按顺序计算 p[1], p[2], ...），我们可以换个思路：对于每个学生 k（从1到n），我们想知道 p[k] 是谁。根据我们的公式 p[a_i] = b_i，我们需要找到一个 i，使得 a_i = k。一旦找到了这个 i，那么 p[k] 就等于 b_i。

为了能够快速地 "根据 a_i 的值 k，找到对应的索引 i"，我们可以预处理一下，创建一个辅助数组（或者叫哈希表）pos_a，pos_a[k] 就用来存储满足 a_i = k 的那个 i。这样查找就是 O(1) 的啦，非常快！

把思路变成代码喵！

好啦，思路已经很清晰了，让我们把它变成可爱的代码吧！

cpp

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 使用这两行可以让输入输出更快一些，对付大数据时很有用哦，喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    // a[i] 表示第 i+1 个学生的笔记本在第三天被谁拿到了
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // b[i] 表示第 i+1 个学生的笔记本在第四天被谁拿到了
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }

    // 创建一个辅助数组 pos_a，用来快速查找
    // pos_a[k] 存储的是值为 k 的元素在 a 数组中的索引 (0-based)
    vector<int> pos_a(n + 1);
    for (int i = 0; i < n; i++) {
        // a[i] 是学生编号 (1-based), i 是数组索引 (0-based)
        // pos_a[学生编号] = 数组索引
        pos_a[a[i]] = i;
    }

    // p 数组就是我们要找的答案啦！
    vector<int> p(n + 1);
    // 我们要计算 p[1], p[2], ..., p[n]
    for (int k = 1; k <= n; k++) {
        // k 在这里代表了学生 a_i 的值
        // 我们想计算 p[k]
        // 根据我们的推导 p[a_i] = b_i
        // 这里的 k 就是那个 a_i
        // 我们需要找到对应的 i，也就是 pos_a[k]
        // 所以 p[k] = b[pos_a[k]]
        p[k] = b[pos_a[k]];
    }

    // 漂亮地输出答案~
    for (int i = 1; i <= n; i++) {
        cout << p[i];
        if (i < n) {
            cout << ' ';
        }
    }
    cout << '\n';

    return 0;
}

跑得快不快呀？

时间复杂度: O(n) 的说我们分析一下代码的每个部分：读取输入的 a 和 b 数组需要 O(n) 的时间。创建 pos_a 辅助数组需要遍历一次 a 数组，也是 O(n)。计算 p 数组需要一个从 1 到 n 的循环，还是 O(n)。最后输出答案也是 O(n)。所以总的时间复杂度就是 O(n) 啦，非常高效！
空间复杂度: O(n) 的说我们需要存储 a, b, pos_a 和 p 这几个数组，它们的大小都和 n 成正比。所以空间复杂度是 O(n)。

这次又学到了什么呢~

通过解决这个问题，我们又get了一些新技能，真开心呐！

抓住核心关系: 解决这类问题的关键，就是从题目描述中提炼出变量之间的数学关系。p[p[i]] = a_i 和 p[p[p[i]]] = b_i 这两个等式就是我们解题的钥匙，通过代换和推理，就能找到最终的答案。
置换与映射: 这个问题里的 p 数组其实就是一个置换（Permutation）。很多算法题的本质都是在处理各种各样的置换和映射关系。
用空间换时间: 当我们需要频繁地根据一个数组中的值来查找它的索引时，可以预先建立一个“值 -> 索引”的反向映射数组（就像代码里的 pos_a）。这是一个非常经典且有用的技巧，能把查找时间从 O(n) 优化到 O(1)，大大提升程序效率！
注意索引: 在编程时要特别小心题目中的1-based索引和C++中常用的0-based索引之间的转换，喵~ 很多小bug都是从这里来的哦！

希望这次的题解对你有帮助！继续加油，算法的世界里还有更多有趣的冒险等着我们去探索呢，喵~

F. Mathematical Analysis Rocks! - 题解 ​

比赛与标签 ​

喵喵，这道题在说什么呀？ ​

来和咱一起分析一下吧！ ​

把思路变成代码喵！ ​

跑得快不快呀？ ​

这次又学到了什么呢~ ​