1 Trie树

  • 高效存储字符串集合
  • 存储：按字符串内容，从左到右依次设置结点，并标记结束位置
  • 查找：查找字符串是否存在 & 出现几次
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

const int N=100010;
int son[N][26], cnt[N], idx;
void insert(char str[]){
    int p = 0;
    for (int i=0; str[i]; i++){
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
} 
int query(char str[]){
    int p = 0;
    for (int i=0; str[i]; i++){
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

2 并查集

快速地处理（近乎O(1)）：

  • 合并两个集合
  • 询问两个元素是否在一个集合中

基本原理：

  • 每个集合用一棵树来表示，树根的编号是集合的编号；
  • 每个结点存储父结点，p 表示其父结点

问题1：如何判断树根：if (p[x] == x);

问题2：如何找到所属集合根结点：while(p[x] ≠ x) x = p[x]; （路径压缩）

问题3：如何合并两个集合（px是x的集合编号，py是y的集合编号）：p[x] = py;

问题4：维护集合元素的个数 size()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

const int N=100010;
int n, m;
int p[N];

int find(int x){
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    scanf("%d%d", &n ,&m);
    for (int i=1; i<= n; i++){
        p[i] =i;
        size[p[i]] = 1;
    }
    while (m--){
        char op[2];
        int a, b;
        scanf("%s", &op);
        
        if (op[0] == 'C'){
            scanf("%d%d", &a, &b);
            p[find(a)] = find(b);
            size[find(b)] += size[find(a)];        
        }
        else if (op[0] == '1'){
            scanf("%d%d", &a, &b);
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else{
            scanf("%d", &a);
            printf("%d\n", size[find(a)]);
        }
    }
    return 0;
}

3 堆

  • 小根堆：每个点都小于等于左右儿子

    • 插入一个数（STL） 
      1

      heap[++size] = x; up(size);
    • 求集合当中最小值（STL） 
      1

      heap[1];
    • 删除最小值（STL） 
      1

      heap[1] = heap[size]; size--; down(1);
    • 删除任意一个元素 
      1

      heap[k] = heap[size]; size--; down(k); up(k);
    • 修改任意一个元素 
      1

      heap[k] = x; down(k); up(k);

  • 堆是完全二叉树，用数组存储，1号位是根结点

  • 一个结点是x，左孩子是2x，右孩子是2x+1

五个操作完全可以用以下两个函数组合起来操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void down(int u){
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[u]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[u]) t = u * 2 + 1;
    if (u != t){
        swap(h[u], h[t]);
        down(t);
    }
}
void up(u){
    while (u / 2 >= 1 && h[u / 2] > h[u]){
        swap(h[u / 2], h[u]);
        u /= 2;
    }
}