0%

算法基础（5）

发表于 更新于 分类于 本文字数： 10k
Trie树，并查集，堆。

Trie树

Trie树是用来快速存储和查找字符串集合的数据结构。

Trie树的基础知识可以参考：

Trie树例题：Trie字符串统计（Acwing 835）

维护一个字符串集合，支持两种操作：

  1. “I x”向集合中插入一个字符串x；

  2. “Q x”询问一个字符串在集合中出现了多少次。

共有N个操作，输入的字符串总长度不超过 $10^5$，字符串仅包含小写英文字母。

输入格式：第一行包含整数N，表示操作数。接下来N行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。

输出格式：对于每个询问指令”Q x”，都要输出一个整数作为结果，表示x在集合中出现的次数。每个结果占一行。

数据范围：$1 \le N \le 2 \times 10^4$。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<iostream>
using namespace std;

const int N = 100010;

//son[N][26]存Trie树中每个节点的儿子
//cnt[]表示以当前节点为结尾的单词的个数
//idx表示当前用到的下标，注意：下标是0的点，即是根节点，又是空节点
int son[N][26], cnt[N], idx;
char str[N];

void insert(char str[])  //插入操作：在当前的Trie树中插入一个字符串
{
    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];
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n--)
    {
        char op[2];
        scanf("%s%s", op, str);
        if(op[0] == 'I')  insert(str);
        else printf("%d\n", query(str));
    }
    
    return 0;
}

Trie树例题2：最大异或对

在给定的N个整数$A_1，A_2……A_N$中选出两个进行xor（异或）运算，得到的结果最大是多少？

输入格式：第一行输入一个整数N。第二行输入N个整数$A_1$～$A_N$。

输出格式：输出一个整数表示答案。

数据范围：$1 \le N \le 10^5$，$0 \le A_i \le 2^31$。

异或运算是按位运算（二进制），相同得0，不同得1。同样先考虑暴力做法，可以用两重循环来解决。

1
2
3
4
5
6
int res = 0;
for(int i = 0; i < n; i++)  //枚举第一个数
{
	for(int j = 0; j < i; j++)   //枚举第二个数
        res = max(res, a[i] ^ a[j]);
}

接下来考虑用Trie树来优化内层循环，即从$a_0$到$ a_{i-1}$中找到与$a_i$异或最大的数。本题的数据范围是$0 \le a_i \le 2^31$，因此每个数可以看出一个31位的二进制串，假设$a_i=101110…1$，要找到与$a_i$异或最大的数，就要异或结果高位是1比较好，因此按$a_i$的位数从左往右找，在$a_0$到$ a_{i-1}$中，先找第30位是0的数，再从这部分数中找第29位是1的数，依次类推。在Trie树中，对于每个$a_i$，先查找再插入。

Trie树 不光可以存储字符串，也可以存储整数，也可以存储二进制数。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010, M = 31 * N;

int n;
int a[N];
int son[M][2], idx;

void insert(int x)  //在Trie树中插入一个数
{
    int p = 0;
    for(int i = 30; i >= 0; i--)   //从最高位开始存
    {
        int u = x >> i & 1;    //取二进制的每一位数
        if(!son[p][u])  son[p][u] = ++ idx;
        p = son[p][u];
    }
}

int query(int x)   //在当前的树中找出与x异或结果最大的数
{
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i--)
    {
        int u = x >> i & 1;
        if(son[p][!u])          //优先寻找是否有与当前位数相反的子节点
        {
            p = son[p][!u];
            res = res * 2 + !u;
        }
        else
        {
            p = son[p][u];
            res = res * 2 + u;
        }
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
        
        insert(a[i]);         //这里先插入再查找是为了避免处理边界问题，少写判断，即一开始树是空的
        int t = query(a[i]);
        res = max(res, a[i] ^ t);
    }
    
    printf("%d\n", res);
    
    return 0;
}

并查集

并查集的作用：

  1. 将两个集合合并
  2. 询问两个元素是否在一个集合当中

并查集可以在近乎$O(1)$的时间内完成这两个操作。

基本思想：每一个集合用一棵树（不一定是二叉树）来维护，树根的编号就是整个集合的编号，对于每一点都存储其父节点是谁，p[x]表示x的父节点。

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

问题2：如何求x的集合编号：while(p[x] != x) x = p[x];

问题3：如何合并两个集合：设p[x]是x的集合编号，p[y]是y的集合编号，p[x]=y

针对问题2的优化：路径压缩。一旦从一个点往上找找到了根节点，就把这条路径上所有的点都指向根节点。

并查集例题1（Acwing 836）：

一共有n个数，编号是1~n，最开始每个数各自在一个集合中。

现在要进行m个操作，操作共有两种：

  1. “M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作
  2. “Q a b”，询问编号为a和b的两个数是否在同一个集合中；

输入格式：第一行输入整数n和m。接下来m行，每行包含一个操作指令，指令为“M a b”或“Q a b”中的一种。

数据范围：$1 \le n, m \le 10^5$

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
#include<iostream>
using namespace std;

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

int find(int x)   //返回x的祖宗节点 + 路劲压缩
{
    if(p[x] != x)  p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 0; i < n; i++)  p[i] = i;  //最开始每个数各自在一个集合中
    
    while(m--)
    {
        char op[2];  
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        
        if(op[0] == 'M')  p[find(a)] = find(b);  //将数a和b所在的两个集合合并，即让find(a)的父节点是find(b)
        else
        {
            if(find(a) == find(b))  puts("Yes");   //询问数a和b是否在同一个集合内，即find(a)是否等于find(b)
            else puts("No");
        }
    }
    
    return 0;
}

并查集例题2：连通块中点的数量（Acwing 837）

给定一个包含n个点（编号为1~n）的无向图，初始时图中没有边。现在要进行m个操作，操作共有三种：

  1. “C a b”，在点a和点b之间连一条边，a和b可能相等；
  2. “Q1 a b”，询问点a和点b是否在同一个连通块中，a和b可能相等；
  3. “Q2 a”，询问点a所在连通块中点的数量。

输入格式：第一行输入整数n和m。接下来m行，每行包含一个操作指令，指令为“C a b”，“Q1 a b”或“Q2 a”中的一种。

数据范围：$1 \le n, m \le 10^5$

可以发现这道题的前两个操作和并查集是一样的，我们可以用一个集合维护连通块，一个连通块中的点就在一个集合当中。当在两个连通块之间连一条边时，起到的作用就是把两个集合合并。额外的操作是统计一个集合中点的数量。

用cnt[N]表示每个集合中点的数量，我们只保证根节点的cnt[]是有意义的。将数a和b所在的两个集合合并时，即让find(a)的父节点是find(b)，然后让find(b)的cnt等于find(a)的cnt加上find(b)的cnt。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
using namespace std;

const int N = 100010;
int n, m;
int p[N], cnt[N];  //size[]存放每个集合中点的数量

int find(int x)   //返回x的祖宗节点 + 路劲压缩
{
    if(p[x] != x)  p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 0; i < n; i++)   //最开始每个数各自在一个集合中
    {
        p[i] = i; 
        cnt[i] = 1;
    }
    while(m--)
    {
        char op[4];  
        int a, b;
        scanf("%s", op);
        
        if(op[0] == 'C')
        {
            scanf("%d%d", &a, &b);
            if(find(a) == find(b))  continue;   //如果a和b在同一个集合中，那么就忽略这次合并操作
            cnt[find(b)] += cnt[find(a)];  //合并集合时，更新集合中点的数量，即find(b)的size[]
            p[find(a)] = find(b);  //将数a和b所在的两个集合合并，即让find(a)的父节点是find(b)
        }
        else if(op[1] == '1')
        {
            scanf("%d%d", &a, &b);
            if(find(a) == find(b))  puts("Yes");   //询问数a和b是否在同一个集合内，即find(a)是否等于find(b)
            else puts("No");
        }
        else 
        {
            scanf("%d", &a);
            printf("%d\n", cnt[find(a)]);  //询问a所在的集合中点的数量
        }
    }
    
    return 0;
}

并查集例题3：食物链（Acwing 240）

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：

第一种说法是”1 X Y”，表示X和Y是同类。

第二种说法是”2 X Y”，表示X吃Y。

此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1） 当前的话与前面的某些真的话冲突，就是假话；

2） 当前的话中X或Y比N大，就是假话；

3） 当前的话表示X吃X，就是假话。

你的任务是根据给定的N和K句话，输出假话的总数。

输入格式：第一行是两个整数N和K，以一个空格分隔。以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。若D=1，则表示X和Y是同类。若D=2，则表示X吃Y。

输出格式：只有一个整数，表示假话的数目。

数据范围：$1 \le N \le 50000, 0 \le K \le100000$。

通过确定每个点与根节点之间的关系，来确定任意两个点之间的关系。由于三种动物的关系是循环被吃，就用每个点到根节点之间的距离来表示它与根节点之间的关系。如果一个点到根节点的距离是1，表示它可以吃根节点；如果一个点到根节点的距离是2，表示它被根节点吃（1吃根，2吃1，根吃2）；如果一个点到根节点的距离是3，表示它和根节点是同类…….如此类推，每3个 一循环。因此可以把集合中所有的点归为三类，用并查集维护每个点到根节点的距离，按点到根节点的距离对3取模：

  • 余1——可以吃根节点；
  • 余2——可以被根节点吃；
  • 余0——与根节点是同类。

在用并查集维护时，每个点存的是其到父节点的距离，做路径压缩时，就更新为其到根节点的距离。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
using namespace std;

const int N = 50010;

int n, m;
int p[N], d[N];

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

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++)  p[i] = i;  //有n个动物，以1-N编号
    
    int res = 0;
    while(m--)
    {
        int t, x, y;
        scanf("%d%d%d", &t, &x, &y);
        
        if(x > n || y > n)  res ++;   //如果x大于n，或者y大于n，则一定是假话；
        else
        {
            int px = find(x), py = find(y);   //先找到x和y的根节点
            if(t == 1)
            {
                if(px == py && (d[x] - d[y]) % 3)  res ++;   //当x 和 y 在同一个集合内时，x，y到根节点的距离模3不相等时一定是假话
                else if(px != py)    //当x 和 y不在同一个集合内时，就要合并,q且要让两者是同类（这时还没法判断，因为不在一个集合内）
                {
                    p[px] = py;  //不妨让x的根节点的父节点 等于 y的根节点的父节点
                    d[px] = d[y] - d[x];  //这样(d[x] + d[px] - d[y]) % 3就等于0了，即x和y是同类
                }
            }
            else
            {
                if(px == py && (d[x] - d[y] - 1) % 3)  res ++; //当x和y在同一个集合内时，x到根节点距离模3比y的多1就是真话，否则就是假话
                else if(px != py)   //当x和y不在同一个集合内时，合并集合，更新距离
                {
                    p[px] = py;
                    d[px] = d[y] - d[x] + 1;
                }
            }
        }
        
    }
    printf("%d\n", res);    
    
    return 0;
}

堆

堆，要支持的操作：

  1. 插入一个数
  2. 求集合当中的最小值
  3. 删除最小值
  4. 删除任意一个元素
  5. 修改任意一个元素

堆是一棵完全二叉树。小根堆：每个点的值都小于等于左右儿子的。

堆的基础知识可以参考：数据结构与算法（19）优先级队列

完全二叉树的基础知识可以参考：

用数组模拟堆，堆的存储方式：用一个一维数组，1号点是根节点（下标从1开始），节点x的左儿子是2x，右儿子是2x+1。有两个基本操作：down(x)，把一个节点往下移，如果把一个节点的值变大了，它有可能就要往下移；up(x)，把一个节点往上移，如果把一个数变小了，它有可能就要往上移 。用这两个基本操作就可以实现上面的五个操作：

  1. 插入一个数：heap[++ size] = x; up[x];
  2. 求集合当中的最小值：heap[1];
  3. 删除最小值：（用堆的最后一个元素覆盖掉堆顶元素）heap[1] = heap[size]; size--; down(1);
  4. 删除任意一个元素：heap[k] = heap[size]; size --; down(k); up(k);（每次donw和up只会执行一个）
  5. 修改任意一个元素：heap[k] = x; down(k); up(x);

堆例题1：堆排序（Acwing 838）

输入一个长度为n的整数数列，从小到大输出前m小的数。

输入格式：第一行包含整数n和m。第二行包含n个整数，表示整数数列。

输出格式：共一行，包含m个整数，表示整数数列中前m小的数。

数据范围：$1 \le m, n \le 10^5$，$1 \le 数列中元素 \le 10^9$

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], cnt;

void down(int u)
{
    int t = u;  //t表示当前节点u，它的左右孩子，三者之间的最小值的下标
    if(u * 2 <= cnt && h[u * 2] < h[t])  t = u * 2;    //t和左孩子比较
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])  t = u * 2 + 1;   //t和右孩子比较
    if(u != t)   //当前节点不是最小值时，down操作要求它与左右孩子中的最小值交换
    {
        swap(h[u], h[t]);
        down(t);
    }
}

void up(int u)
{
    while(u / 2 && h[u / 2] > h[u])
    {
        swap(h[u / 2], h[u]);
        u /= 2;
    }
} 

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)  scanf("%d", &h[i]);   //下标从1开始
    cnt = n;
    
    //建堆，后n / 2 个元素是在最低层的，它们没有左右孩子，保持不动就行；让i = n / 2开始倒着进行down操作即可建堆
    //从 i = n / 2 开始，是保证每次down的时候，下面的孩子节点已经是堆了；这样建堆的时间复杂度是O(n)
    for(int i = n / 2; i ; i--)  down(i);
    
    while(m--)
    {
        printf("%d ", h[1]);   //取堆顶元素，即堆中的最小值
        //删除堆顶元素
        h[1] = h[cnt];
        cnt --;
        down(1);
    }
    
    return 0;
}

堆例题2：模拟堆（Acwing 839）

维护一个集合，初始时集合为空，支持如下几种操作：

  1. “I x”，插入一个数x；

  2. “PM”，输出当前集合中的最小值；

  3. “DM”，删除当前集合中的最小值（数据保证此时的最小值唯一）；

  4. “D k”，删除第k个插入的数；

  5. “C k x”，修改第k个插入的数，将其变为x；

输入格式：第一行包含整数N。接下来N行，每行包含一个操作指令，操作指令为”I x”，”PM”，”DM”，”D k”或”C k x”中的一种。

输出格式：对于每个输出指令“PM”，输出一个结果，表示当前集合中的最小值。每个结果占一行。

数据范围：$1 \le N \le 10^5$，$-10^9 \le x \le 10^9$

这道题的难点在于操作4和5，怎么快速地找到第k个插入的数。这就需要额外维护两个数组，用ph[k]存第k个插入的点在堆中的位置(下标)，hp[k]表示堆中的位置为k的点是第几个插入的点；如ph[j] = k, hp[k] = j; 可以理解为映射。这样例题1代码中普通的swap()操作就要改成这里的堆的特有的交换操作heap_swap()。

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

const int N = 100010;

int h[N], cnt;  
int ph[N], hp[N]; 
//ph[k]存第k个插入的点在堆中的位置(下标)，hp[k]表示堆中的位置为k的点是第几个插入的点；如ph[j] = k, hp[k] = j; 可以理解为映射

void heap_swap(int a, int b)  //a，b是数在堆中的位置，这个需要注意一下
{
    swap(ph[hp[a]], ph[hp[b]]);   
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;  //t表示当前节点u，它的左右孩子，三者之间的最小值的下标
    if(u * 2 <= cnt && h[u * 2] < h[t])  t = u * 2;    //t和左孩子比较
    if(u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])  t = u * 2 + 1;   //t和右孩子比较
    if(u != t)   //当前节点不是最小值时，down操作要求它与左右孩子中的最小值交换
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while(u / 2 && h[u / 2] > h[u])
    {
        heap_swap(u / 2, u);
        u /= 2;
    }
} 

int main()
{
    int n, m = 0;  //m记录插入了多少个数
    scanf("%d", &n);
    
    while(n--)
    {
        char op[5];
        int k, x;
        
        scanf("%s", op);
        if(!strcmp(op, "I"))  //插入一个数x
        {
            scanf("%d", &x);
            cnt ++;
            m ++;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        else if(!strcmp(op, "PM")) printf("%d\n", h[1]);  //输出集合中最小的数，即堆顶
        else if(!strcmp(op, "DM"))  //删除集合中最小的数，即堆顶
        {
            heap_swap(1, cnt);
            cnt --;
            down(1);
        }
        else if(!strcmp(op, "D"))   //删除插入的第k个数
        {
            scanf("%d", &k);
            k = ph[k];
            heap_swap(k, cnt);
            cnt --;
            down(k);  up(k);
        }
        else    //修改第k个插入的数，将其变为x
        {
            scanf("%d%d", &k, &x);
            k = ph[k];
            h[k] = x;
            down(k);  up(k);
        }
    }
    
    return 0;
}