• 【数据结构】—— Trie/并查集/堆

    Trie

    Trie（字典树）是一种用于实现字符串快速检索的多叉树结构。Trie树的每个结点都拥有若干个字符指针，若在插入或者检索字符串时扫描到一个字符 c，就沿着当前结点的 c 字符指针，走向该节点指向的节点。

    AcWing 835. Trie字符串统计

    输入样例：

    1. 5
    2. I abc
    3. Q abc
    4. Q ab
    5. I ab
    6. Q ab

    输出样例：

    1. 1
    2. 0
    3. 1

    插入操作

    1. void insert(char str[])
    2. {
    3.     int p = 0;
    4.     for(int i = 0; str[i]; i ++ )
    5.     {
    6.         int u = str[i] - 'a';
    7.         // 不存在节点就创建一个结点
    8.         if(!son[p][u]) son[p][u] = ++ idx;
    9.         p = son[p][u];
    10.     }
    11.     
    12.     // 结尾标记
    13.     cnt[p] ++ ;
    14. }

    查询操作 

    1. int query(char str[])
    2. {
    3.     int p = 0;
    4.     for(int i = 0; str[i]; i ++ )
    5.     {
    6.         int u = str[i] - 'a';
    7.         if(!son[p][u]) return 0;
    8.         p = son[p][u];
    9.     }
    10.     return 1;
    11. }

    https://www.acwing.com/solution/content/14695/ 

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 100010;
    6.  
    7. // 下标是0的点既是根节点，又是空节点
    8. int son[N][26], cnt[N], idx; 
    9. char str[N];
    10.  
    11. void insert(char str[])
    12. {
    13.     int p = 0;
    14.     for(int i = 0; str[i]; i ++ )
    15.     {
    16.         int u = str[i] - 'a';
    17.         // 不存在节点就创建一个结点
    18.         if(!son[p][u]) son[p][u] = ++ idx;
    19.         p = son[p][u];
    20.     }
    21.     
    22.     // 结尾标记
    23.     cnt[p] ++ ;
    24. }
    25.  
    26. int query(char str[])
    27. {
    28.     int p = 0;
    29.     for(int i = 0; str[i]; i ++ )
    30.     {
    31.         int u = str[i] - 'a';
    32.         if(!son[p][u]) return 0;
    33.         p = son[p][u];
    34.     }
    35.     return cnt[p];
    36. }
    37.  
    38. int main()
    39. {
    40.     int n; cin >> n;
    41.     while(n -- )
    42.     {
    43.         char op[2];
    44.         scanf("%s%s", op, str);
    45.         if(op[0] == 'I') insert(str);
    46.         else printf("%d\n", query(str));
    47.     }
    48.     return 0;
    49. }

    AcWing 143. 最大异或对 

    输入样例：

    1. 3
    2. 1 2 3

    输出样例：

    3

    暴力做法 

    1. int res = 0;
    2. for(int i = 0; i < n; i ++ )
    3. {
    4.     for(int j = 0; j < i; j ++ )
    5.         res = max(res, a[j] ^ a[i]);
    6. }
    7.

    优化 

    第二层循环等价于在 a0 ~ ai 找一个异或对最大的数，这里可以采用Trie树的结构来优化

    其实来说,一个整数,是可以转化成为一个32位的二进制数,而也就可以变成长度为32位的二进制字符串.
    既然如此话,那么我们可以这么做,每一次检索的时候,我们都走与当前AiAi这一位相反的位置走,也就是让Xor值最大,如果说没有路可以走的话,那么就走相同的路.

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 100010,M = 31 * N;
    7.  
    8. int n;
    9. int a[N];
    10. int son[M][2],idx;
    11.  
    12. void insert(int x)
    13. {
    14.     int p = 0;
    15.     for(int i = 30;i >= 0;i --)
    16.     {
    17.         int u = x >> i & 1;
    18.         if(!son[p][u]) son[p][u] = ++ idx;
    19.         p = son[p][u];
    20.     }
    21. }
    22.  
    23. int query(int x)
    24. {
    25.     int p = 0,res = 0;
    26.     for(int i = 30;i >= 0;i --)
    27.     {
    28.         int u = x >> i & 1;
    29.         if(son[p][!u]) {
    30.             p = son[p][!u];
    31.             res = res * 2 + !u;
    32.             
    33.         }else {
    34.             p = son[p][u];
    35.             res = res * 2 + u;
    36.         }
    37.     }
    38.     return res;
    39. }
    40.  
    41. int main()
    42. {
    43.     cin >> n;
    44.     for(int i = 0;i < n;i ++) scanf("%d",&a[i]);
    45.     
    46.     int res = 0;
    47.     
    48.     for(int i = 0;i < n;i ++)
    49.     {
    50.         //减少一次特判
    51.         insert(a[i]);
    52.         
    53.         int t = query(a[i]);
    54.         res = max(res,a[i] ^ t);
    55.     }
    56.     
    57.     cout << res;
    58.     
    59.     return 0;
    60. }

    并查集

    并查集（Disjoint-Set）是一种可以动态维护若干个不重叠的集合，并支持合并与查询的数据结构，主要可以实现以下两个操作：

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

    并查集用一个树形结构来存储每个集合，树上的每个节点都是一个元素，树根是集合的代表元素。整个并查集就是一个森林（若干棵树）。

    每个集合用一棵树来表述。树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点

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

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

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

    AcWing 836. 合并集合 

    输入样例：

    1. 4 5
    2. M 1 2
    3. M 3 4
    4. Q 1 2
    5. Q 1 3
    6. Q 3 4

    输出样例：

    1. Yes
    2. No
    3. Yes

     https://www.acwing.com/solution/content/33345/

    初始化

    for(int i = 1; i <= n; i ++ ) p[i] = i;

    查找 + 路径压缩 

    1. int find(int x){ //返回x的祖先节点 + 路径压缩
    2.     //祖先节点的父节点是自己本身
    3.     if(p[x] != x){
    4.         //将x的父亲置为x父亲的祖先节点,实现路径的压缩
    5.         p[x] = find(p[x]);    
    6.     }
    7.     return p[x]; 
    8. }

     合并操作

    p[find(a)] = find(b)

     

     

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 100010;
    6.  
    7. int n, m;
    8. int p[N];
    9.  
    10. int find(int x)
    11. {
    12.     if(x != p[x]) p[x] = find(p[x]);
    13.     return p[x];
    14. }
    15.  
    16. int main()
    17. {
    18.     cin >> n >> m;
    19.     for(int i = 1; i <= n; i ++ ) p[i] = i;
    20.     
    21.     while(m -- )
    22.     {
    23.         char op[2];
    24.         int a, b;
    25.         scanf("%s%d%d", op, &a, &b);
    26.         if(op[0] == 'M') p[find(a)] = find(b);
    27.         else
    28.         {
    29.             if(find(a) == find(b)) puts("Yes");
    30.             else puts("No");
    31.         }
    32.     }
    33.     return 0;
    34. }

    AcWing 837. 连通块中点的数量 

    输入样例：

    1. 5 5
    2. C 1 2
    3. Q1 1 2
    4. Q2 1
    5. C 2 5
    6. Q2 5

    输出样例：

    1. Yes
    2. 2
    3. 3

    注意事项：当两个点已经是连通的状态时，再在这两个点直接连边的时候，不能增加连通块点的数量

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 100010;
    6.  
    7. int n, m;
    8. int p[N], cnt[N];
    9.  
    10. int find(int x)
    11. {
    12.     if (p[x] != x) p[x] = find(p[x]);
    13.     return p[x];
    14. }
    15.  
    16. int main()
    17. {
    18.     cin >> n >> m;
    19.  
    20.     for (int i = 1; i <= n; i ++ )
    21.     {
    22.         p[i] = i;
    23.         cnt[i] = 1;
    24.     }
    25.  
    26.     while (m -- )
    27.     {
    28.         string op;
    29.         int a, b;
    30.         cin >> op;
    31.  
    32.         if (op == "C")
    33.         {
    34.             cin >> a >> b;
    35.             a = find(a), b = find(b);
    36.             if (a != b)
    37.             {
    38.                 p[a] = b;
    39.                 cnt[b] += cnt[a];
    40.             }
    41.         }
    42.         else if (op == "Q1")
    43.         {
    44.             cin >> a >> b;
    45.             if (find(a) == find(b)) puts("Yes");
    46.             else puts("No");
    47.         }
    48.         else
    49.         {
    50.             cin >> a;
    51.             cout << cnt[find(a)] << endl;
    52.         }
    53.     }
    54.  
    55.     return 0;
    56. }

    AcWing 240. 食物链 

    输入样例：

    1. 100 7
    2. 1 101 1 
    3. 2 1 2
    4. 2 2 3 
    5. 2 3 3 
    6. 1 1 3 
    7. 2 3 1 
    8. 1 5 5

    输出样例：

    3

    TIPS：记录每个点和根节点之间的关系

    余1：可以吃根节点

    余2：可以被根节点吃

    余0：与根节点是-同类

     

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 50010;
    6.  
    7. int n, m;
    8. int p[N], d[N];
    9.  
    10. int find(int x)
    11. {
    12.     if (p[x] != x)
    13.     {
    14.         int t = find(p[x]);
    15.         d[x] += d[p[x]];
    16.         p[x] = t;
    17.     }
    18.     return p[x];
    19. }
    20.  
    21. int main()
    22. {
    23.     scanf("%d%d", &n, &m);
    24.  
    25.     for (int i = 1; i <= n; i ++ ) p[i] = i;
    26.  
    27.     int res = 0;
    28.     while (m -- )
    29.     {
    30.         int t, x, y;
    31.         scanf("%d%d%d", &t, &x, &y);
    32.  
    33.         if (x > n || y > n) res ++ ;
    34.         else
    35.         {
    36.             int px = find(x), py = find(y);
    37.             if (t == 1)
    38.             {
    39.                 if (px == py && (d[x] - d[y]) % 3) res ++ ;
    40.                 else if (px != py)
    41.                 {
    42.                     p[px] = py;
    43.                     d[px] = d[y] - d[x];
    44.                 }
    45.             }
    46.             else
    47.             {
    48.                 if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;
    49.                 else if (px != py)
    50.                 {
    51.                     p[px] = py;
    52.                     d[px] = d[y] + 1 - d[x];
    53.                 }
    54.             }
    55.         }
    56.     }
    57.  
    58.     printf("%d\n", res);
    59.  
    60.     return 0;
    61. }

    堆 

    从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。

    堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。

    由堆性质，树根存的是最大值

    考虑使用一个序列  \small h 来表示堆。 \small h_i 的两个儿子分别是  \small h_{2i} 和 \small h_{2i+1}， 1 是根结点

    如何手写一个堆：

    1.插入一个数： \small heap[++ size] = x; up(size)

    2.求集合当中的最小数：\small heap[1]

    3.删除最小数：\small heap[1] = heap[size]; size--;down(1)

    4.删除任意一个元素：\small heap[k] = heap[size];size--;up(k);down(k)

    5.修改任意一个\small heap[k]=x;down(k);up(k)

    AcWing 838. 堆排序 

    输入样例：

    1. 5 3
    2. 4 5 1 3 2

    输出样例：

    1 2 3

    AcWing 838. 堆排序 分析i=n/2 - AcWing

    1. #include 
    2. #include 
    3.  
    4. using namespace std;
    5.  
    6. const int N = 100010;
    7.  
    8. int n, m;
    9. int h[N], size;
    10.  
    11. void down(int u)
    12. {
    13.     int t = u;
    14.     if(u * 2 <= size && h[u * 2] < h[t] ) t = u * 2;
    15.     if(u * 2 + 1<= size && h[u * 2 + 1] < h[t] ) t = u * 2 + 1;
    16.     if(u != t)
    17.     {
    18.         swap(h[u], h[t]);
    19.         down(t);
    20.     }
    21. }
    22.  
    23. int main()
    24. {
    25.     cin >> n >> m;
    26.     for(int i = 1; i <= n ; i ++ ) scanf("%d", h[i]);
    27.     
    28.     for(int i = n / 2; i; i -- ) down(i);
    29.     
    30.     while(m -- )
    31.     {
    32.         printf("%d ", h[1]);
    33.         h[1] = h[size --];
    34.         down(1);
    35.     }
    36. }

     AcWing 839. 模拟堆

    输入样例：

    1. 8
    2. I -10
    3. PM
    4. I -10
    5. D 1
    6. C 2 8
    7. I 6
    8. PM
    9. DM

    输出样例：

    1. -10
    2. 6
    1. #include 
    2. #include 
    3. #include 
    4.  
    5. using namespace std;
    6.  
    7. const int N = 100010;
    8.  
    9. int h[N], ph[N], hp[N], cnt;
    10.  
    11. void heap_swap(int a, int b)
    12. {
    13.     swap(ph[hp[a]],ph[hp[b]]);
    14.     swap(hp[a], hp[b]);
    15.     swap(h[a], h[b]);
    16. }
    17.  
    18. void down(int u)
    19. {
    20.     int t = u;
    21.     if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    22.     if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    23.     if (u != t)
    24.     {
    25.         heap_swap(u, t);
    26.         down(t);
    27.     }
    28. }
    29.  
    30. void up(int u)
    31. {
    32.     while (u / 2 && h[u] < h[u / 2])
    33.     {
    34.         heap_swap(u, u / 2);
    35.         u >>= 1;
    36.     }
    37. }
    38.  
    39. int main()
    40. {
    41.     int n, m = 0;
    42.     scanf("%d", &n);
    43.     while (n -- )
    44.     {
    45.         char op[5];
    46.         int k, x;
    47.         scanf("%s", op);
    48.         if (!strcmp(op, "I"))
    49.         {
    50.             scanf("%d", &x);
    51.             cnt ++ ;
    52.             m ++ ;
    53.             ph[m] = cnt, hp[cnt] = m;
    54.             h[cnt] = x;
    55.             up(cnt);
    56.         }
    57.         else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
    58.         else if (!strcmp(op, "DM"))
    59.         {
    60.             heap_swap(1, cnt);
    61.             cnt -- ;
    62.             down(1);
    63.         }
    64.         else if (!strcmp(op, "D"))
    65.         {
    66.             scanf("%d", &k);
    67.             k = ph[k];
    68.             heap_swap(k, cnt);
    69.             cnt -- ;
    70.             up(k);
    71.             down(k);
    72.         }
    73.         else
    74.         {
    75.             scanf("%d%d", &k, &x);
    76.             k = ph[k];
    77.             h[k] = x;
    78.             up(k);
    79.             down(k);
    80.         }
    81.     }
    82.  
    83.     return 0;
    84. }

     

  • 相关阅读:
    算法day31|455，476，53
    Linux中网络排查命令traceroute
    nginx 负载均衡
    抽象类与接口
    生产脚本1
    解读vue3源码-响应式篇1(手写一个简单的响应式函数)
    Eclipse 主网即将上线迎空投预期，Zepoch 节点或成受益者？
    05-Redis 持久化之RDB 的奥秘
    【JAVA程序设计】（C00082）基于SSM+uniapp前后端分离的美发服务平台微信小程序
    CDN网络科普小文（故事版）
  • 原文地址：https://blog.csdn.net/forever_bryant/article/details/126048173