hash表

静态教务系统

今有某大学，里面有 n(≤ 100000) 名学生。每个学生有学号，学号在 [1, 109] 范围内分布。
给定所有学生的学号和成绩。
有 m(≤ 100000) 次查询，每次查询是给出一个学号，问其成绩。

直接用桶储存会出事的，因为不可能存开1e9的数组会爆空间。

因为n≤100000所以我们可以开一个结构体，有id和score两个属性，这样即可存下100000个学生。

但是仔细一想，嗯？这样只能遍历来查找了，查找的时间复杂度为$O(n)$。有m次查询，所以整个算法的时间复杂度为$O(nm)$，而n≤100000，m≤100000则最大时间复杂度为$10^{5}$*$10^{5}$即为$10^{10}$。这是不可接受，远远大于普遍算力两千万/s，必然会超时。

我们可以优化一下，先排序，然后使用二分进行查找，这样查找的时间复杂度为$O(logn)$。时间复杂度为$O(nlogn) O(logn)$

#include <bits/stdc++.h>
using namespace std;
struct Student {
    int id;
    int score;
};
int n, m;
Student stu[100005];
void input() {
    cin >> n >> m;
    for(int i=1; i<=n; i++)
        cin >> stu[i].id >> stu[i].score;
}
// 返回学号等于 id 的学生的成绩
// 如果 stu[] 按学号升序，我们就可以折半查找
int queryScore(int id) {
    for(int i=1; i<=n; i++)
        if(stu[i].id == id)
            return stu[i].score;   
    return -1;
}
void work() {//输入指令
    while(m--) {
        int id;
        cin >> id;
        cout << queryScore(id) << endl;
    }
}
int main() {
    input();
    work();
    return 0;
}

这样就算做出了这道题。

动态教务系统

是一个问题的加强版：

教务系统里面，初始没有任何学生资料。你需要应对 n 次操作：
INSERT id, score: 向系统中加入一个学生 id，成绩为 score。
2 QUERY id: 查询学号为 id 的学生成绩。

我们依然可以使用上一个方法，但是显然，会超时。因为插入的时候我们需要移动元素，时间复杂度会很高。

那怎么办呢？

我们可以分桶储存，第一个桶里放学号是1~1000的学生，查找仅需在该生的桶中查找即可。

但是这样依然会被卡点而超时，出题人可以使数据都在同一个桶中，这样你的算法就会退化成暴力。所以我们可以给学号摸上p，因为出题人没法知道你的p，所以你几乎不会被卡。

这就是hash，hash也有很多种，但是取模hash最好写，所以我们选择他。

p的选择

一般选择质数为p，因为这样可以使数据均匀分布。

扩展一下STL中的set和map，他们的底层是红黑树。

sets;

s.insert(x) 插入 x
s.count(x) 查询 x 在集合中的出现次数，即查询 x 在不在集合中
s.erase(x) 从集合中删除 x

mapma;

ma[key] 查询键值对
ma[key] = value 修改键值对
ma.count(key) 查询 key 出现次数，即查询是否在 map 中
ma.erase(key) 从 map 中删除 key

并查集

我们定义，一个人的朋友，也是另外一个人的朋友。

今天有m个人，一开始大家都没有朋友,输入x，y表示让x和y成为朋友。

所以我们可以转化一下，我们给每个人记录其首领。一个团伙只有一个首领。起初，第 i 个人的首领。例如，A的上线是 B，B的上线是 C，C 的上线是他自己。那么 A 的上线是C。将B和D交友，按理来讲应当由B的团伙吞并D的团伙。只需要把D的上线设为B的上线即可。

查询2个人是不是朋友，仅需查询是否有共同的上线即可。

但是这样容易被出题人卡测试点，我们可以直接把所有朋友设置成同一个上线，这样就可以降下来不少复杂度。我们可以吧他的时间复杂度当成$O(1)$。

eg:洛谷P3367

#include <bits/stdc++.h>
using namespace std;

int n, m;
int dad[10005];         // dad[x]: x 的上线
// 若 x 为首领，则其上线仍然是自己

void input() {
    cin >> n >> m;
}

void init() {
    for(int i=1; i<=n; i++)
        dad[i] = i;
}

// 寻找 x 的老大
int findLeader(int x) {
    if(dad[x] == x)
        return x;
    
    // 递归寻找 x 的老大，找到之后，把 dad[x] 直接设成老大（组织扁平化）
    dad[x] = findLeader(dad[x]);
    return dad[x];
}

// 合并 x, y 团伙
void uni(int x, int y) {
    int xLeader = findLeader(x), yLeader = findLeader(y);

    // 由 x 团伙吞并 y 团伙
    dad[yLeader] = xLeader;
}

// uni 是 O(n) 的
// 根源：要把每一个 y 团伙的 leader 直接设成 xLeader

// 询问 x, y 是否在同一个团伙
void ask(int x, int y) {
    if(findLeader(x) == findLeader(y))
        puts("Y");
    else
        puts("N");
}

void work() {
    while(m--) {
        int cmd, x, y;
        cin >> cmd >> x >> y;

        if(cmd == 1)
            uni(x, y);
        else
            ask(x, y);
    }
}

int main() {
    input();
    init();
    work();

    return 0;
}