题目描述

这个题目有一点难以理解, 然后我们拆开之后慢慢理解了之后, 其实会发现这个题目并没有想的那么难

首先我们输入一个序列$II$, 这个里面的第一个数字是代表了接下来会有多少个数字, 然后我们再输入进去

以此类推, 我们的序列$RR$也是这个样子, 第一个数字代表了接下来有多少个数字, 然后我们输入进去

然后我们要做的其实就是把我们的$RR$数组排序加去重就可以了, 然后遍历所有的$II$数组, 看有多少个$RR$可以找到, 最后输出即可

这里用一个图解释比较好理解一点

然后就是这样的一个意思

题解

解法一: 直接模拟

实现思路

我们可以直接用我们的STL容器set容器来实现我们的去重和排序, 然后我们每次遍历寻找, 如果set里面的元素可以在我们的I数组中找到, 我们可以放入, 然后我们接下来每一次都是要去放入, 最后输出总个数即可

代码实现

#include <bits/stdc++.h>

using namespace std;

signed main() {
    int n;
    cin >> n;
    vector<string> I(n);
    for (auto &it : I) cin >> it;
    // 这个是把我们的I数组输入进去
    int m;
    cin >> m;
    set<int> st;
    for (int i = 1; i <= m; i++) {
        int tmp;
        cin >> tmp;
        st.insert(tmp);
    }
    // 这个实现了我们R数组的去重和排序
    vector<int> res;
    for (auto &it : st) {
        int cnt = 0;
        bool okk = false;
        // cnt是有多少个
        // okk是我们是否找到
        for (auto &it1 : I) {
            if (it1.find(to_string(it)) != string::npos) {
                cnt += 1;
                if (okk == false) {
                    res.emplace_back(it);
                    okk = true;
                }
                // 如果找到了我们存入数组
            }
        }
        if (cnt != 0) {
            res.emplace_back(cnt);
            for (int i = 0; i < n; i++) {
                if (I[i].find(to_string(it)) != string::npos) {
                    res.emplace_back(i);
                    res.emplace_back(stoi(I[i]));
                }
            }
            // 我们每一次把我们的下标和我们的值存入
        }
    }
    cout << res.size() << " ";
    for (auto &it : res) {
        cout << it << " ";
    }
    cout << "\n";
    return 0;
}

时空复杂度分析

时间复杂度: $O(mlogm+nmlogm)O(mlogm\; +\; nmlogm)$

理由如下: 首先我们的set里面最多会有m个元素, 那么我们插入的时间复杂度就是mlogm的, 然后我们遍历我们的set容器, 每一次的遍历的时间复杂度是logm的, 我们最坏遍历m次, 所以我们外层循环时mlogm的, 我们里层每次要遍历我们的I数组, 这个大小是n的, 由于我们的保证我们的数据范围是在INT内, 所以我们可以把我们find函数的时间复杂度看成一个常数, 所以我们最后合并在一起, 我们总共的时间复杂度就是$O(mlogm+nmlogm)O(mlogm\; +\; nmlogm)$

空间复杂度: $O(nm)O(nm)$

理由如下: 我们最坏的情况下, 我们最后临时的res辅助数组会放入大概n * m个数据, 所以我们的空间复杂度在于这里了, 事实上这个数组可以优化掉

解法二: 优化我们的空间

实现思路

我们可以考虑用我们的时间换取我们的空间, 我们之所以开了一个新的数组是为了我们的方便, 如果我们把测试的循环多跑一次, 那么我们就可以不使用这个辅助的数组

代码实现

#include <bits/stdc++.h>

using namespace std;

signed main() {
    int n;
    cin >> n;
    vector<string> I(n);
    for (auto &it : I) cin >> it;
    // 这个是把我们的I数组输入进去
    int m;
    cin >> m;
    set<int> st;
    for (int i = 1; i <= m; i++) {
        int tmp;
        cin >> tmp;
        st.insert(tmp);
    }
    // 这个实现了我们R数组的去重和排序
    int res = 0;
    for (auto &it : st) {
        int cnt = 0;
        bool okk = false;
        // cnt是有多少个
        // okk是我们是否找到
        for (auto &it1 : I) {
            if (it1.find(to_string(it)) != string::npos) {
                cnt += 1;
                if (okk == false) {
                    res += 1;
                    okk = true;
                }
                // 如果找到了我们存入数组
            }
        }
        if (cnt != 0) {
            res += 1;
            for (int i = 0; i < n; i++) {
                if (I[i].find(to_string(it)) != string::npos) {
                    res += 2;
                }
            }
            // 我们每一次把我们的下标和我们的值存入
        }
    }
    cout << res << " ";
    for (auto &it : st) {
        int cnt = 0;
        bool okk = false;
        // cnt是有多少个
        // okk是我们是否找到
        for (auto &it1 : I) {
            if (it1.find(to_string(it)) != string::npos) {
                cnt += 1;
                if (okk == false) {
                    cout << it << " ";
                    okk = true;
                }
                // 如果找到了我们存入数组
            }
        }
        if (cnt != 0) {
            cout << cnt << " ";
            for (int i = 0; i < n; i++) {
                if (I[i].find(to_string(it)) != string::npos) {
                    cout << i << " " << I[i] << " ";
                }
            }
            // 我们每一次把我们的下标和我们的值存入
        }
    }
    cout << "\n";
    return 0;
}

时空复杂度分析

时间复杂度: $O(mlogm+nmlogm)O(mlogm\; +\; nmlogm)$

理由如下: 首先我们的set里面最多会有m个元素, 那么我们插入的时间复杂度就是mlogm的, 然后我们遍历我们的set容器, 每一次的遍历的时间复杂度是logm的, 我们最坏遍历m次, 所以我们外层循环时mlogm的, 我们里层每次要遍历我们的I数组, 这个大小是n的, 由于我们的保证我们的数据范围是在INT内, 所以我们可以把我们find函数的时间复杂度看成一个常数, 所以我们最后合并在一起, 我们总共的时间复杂度就是$O(mlogm+nmlogm)O(mlogm\; +\; nmlogm)$, 但是我们的这个做法事实上是要比我们解法一的速度慢的, 但是时间复杂度分析上是一样的

空间复杂度: $O(max(n,m))O(max(n,\; m))$

理由如下: 我们的空间占用都是在于我们输入的这两个数组里面了, 我们选取最大的那个数组长度作为我们空间复杂度