哈希表

unordered_map 和 unordered_set 具有很大的常数。其实我们可以自己实现一个飞快的哈希表。

struct hash_table {
    static const int MOD = 1e6 + 171;
    struct Node {
        int key, v, next;
    } pool[N];
    int nn, head[MOD];
    inline hash_table() {
        nn = 0;
        for(int i = 0; i < MOD; i++) head[i] = 0;
    }
    int &insert(int key, int v) {
        // assert(nn < N - 1);
        pool[++nn] = {key, v, head[key % MOD]};
        head[key % MOD] = nn;
        return pool[nn].v;
    }
    bool count(int key) {
        for(int i = head[key % MOD]; i; i = pool[i].next) {
            if(pool[i].key == key) return true;
        }
        return false;
    }
    int &operator[](int key) {
        for(int i = head[key % MOD]; i; i = pool[i].next) {
            if(pool[i].key == key) return pool[i].v;
        }
        return insert(key, 0);
    }
};

Y227 求好元素

本题卡常，使用 unordered_set 不能通过，必须手写哈希表。

核心代码

const int MOD = 1E6 + 171;

vector<int> mp[MOD];

void insert(int x) {
    x += 2e9;
    mp[x % MOD].push_back(x);
}

bool find(int x) {
    x += 2e9;
    int tmp = x % MOD;
    for(auto i : mp[tmp]) {
        if(i == x) return true;
    }
    return false;
}