今天要学习数据结构进阶了!今天的课表有:

  1. hash表
  2. 并查集
  3. 线段树

晚上还可以要学习st表。(虽然这些都是提高组的内容,但是谁知道出题人会怎么想呢?)

但是作为衔接还是不错的。

hash表

静态教务系统

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

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

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

但是仔细一想,嗯?这样只能遍历来查找了,查找的时间复杂度为$O(n)$。有m次查询,所以整个算法的时间复杂度为$O(nm)$,而n≤100000m≤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 次操作:

  1. INSERT id, score: 向系统中加入一个学生 id,成绩为 score。
  2. 2 QUERY id: 查询学号为 id 的学生成绩。

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

那怎么办呢?

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

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

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

p的选择

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

扩展一下STL中的setmap,他们的底层是红黑树。

set s;

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

map <int, int> ma;

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

并查集

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

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

所以我们可以转化一下,我们给每个人记录其{% label 首领 red %}。一个团伙只有一个{% label 首领 %}。 起初,第 i 个人的{% label 首领 % }是自己。 交友操作。由 x 团伙吞并 y 团伙。 对于 y 所在团伙的每一个人,将其首领改成 x 所在团伙的首领。
询问操作。返回两个人是否拥有相同的首领。

我们发现,每次交友可能会产生大量人员更改首领。 $O(n)$ 交友,$O(1)$ 查询。

对于每一个人,我们不直接记录其首领,而是记录其{% label 上线 blue %}。例如,A的{% label 上线 blue %}是 B,B的{% label 上线 blue %}是 C,C 的{% label 上线 blue %}是他自己。 那么 A 的{% label 上线 blue %}是C。将B和D交友,按理来讲应当由B的团伙吞并D的团伙。只需要把D的{% label 上线 blue %}设为B的{% label 上线 blue %}即可。

查询2个人是不是朋友,仅需查询是否有共同的{% label 上线 blue %}即可。

但是这样容易被出题人卡测试点,我们可以直接把所有朋友设置成同一个{% label 上线 blue %},这样就可以降下来不少复杂度。我们可以吧他的时间复杂度当成$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;
}

一道经典的模板题,按照模板即可。

线段树

因为篇幅原因,所以会另起一页。请查看course-day-7-2 | CS奇妙 (loveoi.net)

This post was written on July 27, 2022