D. Sakurako's Hobby - 题解

比赛与标签

比赛: Codeforces Round 970 (Div. 3) 标签: dp, dsu, graphs, math 难度: *1100

题目大意喵~

你好呀，未来的算法大师！Sakurako酱遇到了一个有趣的问题，需要我们帮忙的说~

题目给了我们一个长度为 n 的排列 p（就是1到n的数字不重不漏地排成一队）和一个表示颜色的字符串 s。

首先，我们要理解一个叫做“可达”的概念。从一个整数 i 出发，我们不停地让 i 变成 p[i]，这样走下去能到达的所有数字，都算是从 i “可达”的。比如说，p = [3, 5, 6, 1, 2, 4]，我们从 i=1 出发：

i 现在是 1。
下一步 i 变成 p[1]，也就是 3。
再下一步 i 变成 p[3]，也就是 6。
再下一步 i 变成 p[6]，也就是 4。
再下一步 i 变成 p[4]，也就是 1。呀，我们回到了起点！所以，从 1 出发，可以到达 1, 3, 6, 4 这些数字。

接下来，每个数字都被染成了黑色（用 '0' 表示）或白色（用 '1' 表示）。Sakurako定义了一个函数 F(i)，它的值是从 i 出发可达的所有数字中，黑色数字的数量。

我们的任务就是，对于每一个 i (从 1 到 n)，计算出 F(i) 的值。很简单对不对，喵~？

解题思路喵！

看到这种 i 指向 p[i] 的关系，猫猫的直觉就告诉我们，这一定和图论有关的说！

我们可以把 1 到 n 这 n 个数字看作是图上的 n 个节点。对于每个 i，我们从节点 i 连一条有向边到节点 p[i]。因为 p 是一个排列，每个数字都只出现一次，所以这意味着：

每个节点都只有一条出边（指向 p[i]）。
每个节点也都只有一条入边（从某个 j 指向它，其中 p[j]=i）。

一个图里，每个节点都只有一条入边和一条出边，这是什么结构呢？喵~ 没错，它必然是由一个或多个不相交的环组成的！就像我们刚才例子里找到的 1 -> 3 -> 6 -> 4 -> 1，这就是一个环。

一旦我们想通了这一点，问题就变得超级简单了呐！

思考一下，如果几个节点（比如 u 和 v）在同一个环里，那么从 u 出发，沿着边走啊走，一定能到达 v。同样，从 v 出发也一定能走到 u。这意味着，同一个环里的所有节点，它们的可达集合是完全相同的，就是这个环里的所有节点！

所以，对于同一个环里的任何一个节点 i，F(i) 的值都是一样的，都等于这个环里黑色节点的总数。

那么我们的解题策略就清晰啦：

遍历所有节点，找到图中的每一个环。
为了避免重复计算，我们用一个 visited 数组来标记已经处理过的节点。
当我们遇到一个没有被访问过的节点 i 时，我们就知道发现了一个新的环。
从 i 出发，沿着 p 的指向一直走，把路径上的所有节点都记录下来，并标记为 visited，直到我们回到起点 i。这样，我们就找到了一个完整的环。
计算这个环里有多少个黑色节点。
最后，将这个黑节点的数量赋给环里每一个节点的答案 F 值。

重复这个过程，直到所有节点都被访问过，我们就得到所有答案啦！是不是很巧妙呢，喵~

代码实现喵！✨

cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 解决单个测试用例的函数喵
void solve() {
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    string s;
    cin >> s;

    // 为了方便查找，我们预处理一下颜色喵
    // col[k] 直接存储数字 k (1-based) 的颜色
    vector<char> col(n + 1);
    for (int i = 0; i < n; i++) {
        col[p[i]] = s[i];
    }

    // 将 1-based 的 p 数组转换为 0-based 的后继节点数组
    // next_node[i] 表示节点 i (0-based) 的下一个节点是啥
    vector<int> next_node(n);
    for (int i = 0; i < n; i++) {
        next_node[i] = p[i] - 1;
    }

    vector<int> ans(n, 0); // 存储最终答案 F(i) 的说
    vector<bool> visited(n, false); // 标记节点是否被访问过，防止重复处理同一个环

    // 遍历所有节点，寻找并处理每一个环
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            // 发现一个新环的起点！
            vector<int> cycle;
            int cur = i;
            
            // 沿着环走一圈，把所有节点收集起来
            while (!visited[cur]) {
                visited[cur] = true;
                cycle.push_back(cur);
                cur = next_node[cur];
            }

            // 计算这个环里有多少个黑色的节点（猫猫）
            int count_black = 0;
            for (int u : cycle) {
                // u 是 0-based 索引, 对应的数字是 u+1
                if (col[u + 1] == '0') {
                    count_black++;
                }
            }

            // 同一个环里的所有节点，答案都是相同的
            for (int u : cycle) {
                ans[u] = count_black;
            }
        }
    }

    // 漂漂亮亮地输出答案~
    for (int i = 0; i < n; i++) {
        cout << ans[i] << (i == n - 1 ? "" : " ");
    }
    cout << '\n';
}

int main() {
    // 这是加速输入输出的小魔法，让程序跑得更快喵~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析喵~

时间复杂度: O(N) 的说。对于每个测试用例，我们有一个外层循环遍历所有 n 个节点。visited 数组确保了每个节点只会被内层的 while 循环（即环的发现过程）访问一次。之后，每个节点也只会被计入一次黑色节点数量，并被赋值一次答案。所以每个节点相关的操作都是常数次的，总的时间复杂度就是线性的 O(N) 啦。
空间复杂度: O(N) 的说。我们需要 p 数组、col 数组、next_node 数组、ans 数组和 visited 数组来存储信息，这些都需要 O(N) 的空间。在寻找环时，cycle 向量最多也只会存储 n 个节点。所以总的空间复杂度也是 O(N) 的说。

知识点与总结喵！

这次的冒险旅程，我们学到了什么呢？猫猫来总结一下！

排列与图的转化: 这是一个非常经典的思想！当你看到一个排列 p，并且有 i -> p[i] 这样的关系时，一定要立刻联想到有向图。这往往是解题的第一步！
排列图的性质: 排列构成的图非常特殊，它是由若干个不相交的环组成的。理解并利用这个性质是解开本题的钥匙。
环检测算法: 我们用了一个非常朴素但有效的方法来找环：从一个未访问的节点出发，沿着边一直走，用 visited 数组标记路径，直到回到已访问节点。这本质上是一种深度优先搜索（DFS）的应用。
编程小技巧:
- 索引转换: 题目是 1-based，而C++数组是 0-based。代码中通过 p[i]-1 等操作优雅地进行了转换，这能让代码逻辑更清晰，减少出错的可能。
- 预处理: 提前建立 col 数组，将数字和颜色直接映射起来，避免了在主循环中反复查找，提高了效率。

总之，以后再遇到排列问题，不妨先试着把它画成一个图，说不定就能发现像这样可爱的环状结构，问题也就迎刃而解啦！继续加油，你超棒的喵~！

D. Sakurako's Hobby - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵！ ​

代码实现喵！✨ ​

复杂度分析喵~ ​

知识点与总结喵！ ​