[语言月赛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，该函数用于查找字符串 s 在整个文献列表中的索引。

接下来，我们使用一个数组 parent 来记录每个字符串的父节点。初始时，每个字符串的父节点都是其自身。

对于操作 '1 x y'，我们需要将字符串 s_x 的父节点改为 s_y。具体来说，我们将 parent[find(x)] 的值改为 find(y)。

对于操作 '2 x y'，我们需要判断两个字符串是否相似。具体来说，我们可以比较 find(x) 和 find(y) 是否相等。如果相等，则表示两个字符串相似；否则，表示两个字符串不相似。

复杂度分析

对于每个操作，我们都需要使用 find 函数来查找字符串的父节点。由于使用了路径压缩的并查集，find 函数的时间复杂度为 O(log n)。

因此，总的时间复杂度为 O(n + q log n)。

代码实现

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

vector<int> parent;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

int main() {
    int n, q;
    cin >> n >> q;

    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    parent.resize(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }

    for (int i = 0; i < q; i++) {
        int op, x, y;
        cin >> op >> x >> y;
        x--;
        y--;

        if (op == 1) {
            parent[find(x)] = find(y);
        } else {
            if (find(x) == find(y)) {
                cout << 'Yes' << endl;
            } else {
                cout << 'No' << endl;
            }
        }
    }

    return 0;
}

[语言月赛202304] 写大作业 - 计算理论大作业难题