[语言月赛202304] 写大作业

题目描述

扶苏为了写计算理论大作业已经 36 小时没有合眼了。

为了能快点睡觉，扶苏找到了 n 份文献，第 i 份文献是一个字符串 s_i，她打算把这些文献组合起来。

具体来说，一共有两种操作：

'1 x y'：把文献 s_x 整体拼接到 s_y 的后面，然后删除 s_x。
'2 x y'：查询 s_x 和 s_y 是否'相似'。

我们保证在 '1 x y' 操作出现后，字符串 s_x '不会' 出现在接下来的任何操作中。这就是说，操作 1 至多有 n-1 次。

'相似' 的定义是：对两个字符串 s_x 和 s_y，如果存在一种重新排列 s_x 的方法，使得重排后的 s_x 和 s_y 相等，则称 s_x 和 s_y '相似'。

例如，假设 s_1 = 'ab', s_2 = 'cd', s_3 = 'abcd'，则执行 '1 1 2' 后，s_1 被删除，s_2 = 'cdab', s_3 = 'abcd'；继续执行 '2 2 3' 后，因为可以把 s_2 重排为 'abcd'，所以 s_2 和 s_3 相似。

注意，操作 2 不会对字符串做出实际修改。

输入格式

第一行是两个整数，分别表示文献的数量 n 和操作的数量 q。
接下来 n 行，每行一个字符串，第 i 行的字符串表示 s_i。
接下来 q 行，每行三个整数 op, x, y，其含义见『题目描述』。

输出格式

对个操作 2，输出一行一个字符串。如果 s_x 和 s_y 相似，则输出 'Yes'，否则输出 'No'。

样例 #1

样例输入 #1

4 4
ab
cd
abcd
abcc
1 1 2
2 2 3
2 3 4
2 2 4

样例输出 #1

Yes
No
No

提示

数据规模与约定

对 30% 的数据，保证 n = 2，q = 1。
对 60% 的数据，保证 n ≤ 6，q ≤ 6，|s_i| ≤ 6。
对 100% 的数据，保证 2 ≤ n ≤ 10^5，1 ≤ q ≤ 10^6，1 ≤ o ≤ 2，1 ≤ x, y ≤ n，且输入字符串的总长度不超过 10^6，输入字符串仅含小写英文字母，且不是空串。

解题思路

本题可以使用并查集来解决。

首先，我们需要定义一个函数 find 来找到某个字符串所属的集合的代表元素。我们可以使用一个数组 parent 来记录每个字符串的父节点，当 parent[i] = i 时，表示字符串 i 是集合的代表元素。在 find 函数中，我们可以使用路径压缩的方式来优化查找过程。

接下来，我们需要定义一个函数 merge 来合并两个集合。假设我们要合并集合 A 和集合 B，我们只需要将集合 A 的代表元素的父节点设为集合 B 的代表元素即可。

在进行操作时，我们可以根据操作类型进行不同的处理：

当操作类型为 '1 x y' 时，我们将集合 x 的代表元素的父节点设为集合 y 的代表元素。
当操作类型为 '2 x y' 时，我们只需要判断集合 x 的代表元素和集合 y 的代表元素是否相等即可。

最后，我们将所有操作按顺序进行处理，得到最终的结果。

复杂度分析

由于我们使用了路径压缩和按秩合并优化，并查集的时间复杂度为 O(α(n))，其中 α(n) 是阿克曼函数的反函数。在实际情况下，α(n) 的值不会超过 5，因此我们可以认为并查集的时间复杂度为 O(1)。

由于每个操作都需要进行一次并查集操作，因此总的时间复杂度为 O(n+q)，其中 n 是文献的数量，q 是操作的数量。

算法实现

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

// 并查集的 find 操作
int find(vector<int>& parent, int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

// 并查集的 merge 操作
void merge(vector<int>& parent, int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    
    // 初始化并查集
    vector<int> parent(n + 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    // 读取文献的字符串
    vector<string> docs(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> docs[i];
    }
    
    // 处理操作
    for (int i = 0; i < q; i++) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            merge(parent, x, y);
        } else {
            int rootX = find(parent, x);
            int rootY = find(parent, y);
            // 判断代表元素是否相同
            if (rootX == rootY) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
    
    return 0;
}

完整代码

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

// 并查集的 find 操作
int find(vector<int>& parent, int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

// 并查集的 merge 操作
void merge(vector<int>& parent, int x, int y) {
    int rootX = find(parent, x);
    int rootY = find(parent, y);
    if (rootX != rootY) {
        parent[rootX] = rootY;
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    
    // 初始化并查集
    vector<int> parent(n + 1);
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    
    // 读取文献的字符串
    vector<string> docs(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> docs[i];
    }
    
    // 处理操作
    for (int i = 0; i < q; i++) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            merge(parent, x, y);
        } else {
            int rootX = find(parent, x);
            int rootY = find(parent, y);
            // 判断代表元素是否相同
            if (rootX == rootY) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
    }
    
    return 0;
}

语言月赛202304 - 写大作业 - 解题思路及代码实现