P1571 题解

rainygame · 2023-05-31 22:55:51 · 题解

本题大部分都是 O(m \log m+n) 的，这里给出一个期望 O(n\times\frac{n}{mod}) 的解法，其中我设 mod = 10^5+7。

好吧，这就是哈希做法。

哈希其实就是一种更省空间的映射，因为本题的编号 \le 2\times10^9，所以我们无法直接映射 x，只能映射 x \bmod mod 的值，而哈希就是通过取模来用更小的空间实现接近 O(1) 的查询。

但是可能会出现冲突，也就是两个数取模这个数相同的情况。这个时候我们就可以使用拉链法，也就是在每个取模后的值那里拉一个链表，插入对于相同的就在链表后直接插入，查询时就枚举这个链表的每一个元素。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100001
#define MOD 100007

int n, m, x;
int a[MAXN];

struct Hash{
    list<int> li[MOD];
    void insert(int x){
        li[x % MOD].push_back(x);
    }

    bool find(int x){
        for (auto i: li[x % MOD]){
            if (i == x) return true;
        }
        return false;
    }
}ha;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i(1); i<=n; ++i) cin >> a[i];
    while (m--){
        cin >> x;
        ha.insert(x);
    }

    for (int i(1); i<=n; ++i){
        if (ha.find(a[i])) cout << a[i] << ' ';
    }

    return 0;
}