• ＜数据结构＞ - 数据结构在算法比赛中的应用（下）

    目录

    Trie树 

    Trie字符串统计

    最大异或对

    并查集

    合并集合

    连通块中点的数量

    食物链

    堆

    堆排序

    模拟堆

     哈希表

    模拟散列表

    字符串哈希

    Trie树 

    Trie字符串统计

    思路：

    设 idx索引用于构建树， 结点son[节点位置][节点分支指针]，cnt[]记录单词个数

    1. #include 
    2.  
    3. using namespace std;
    4.  
    5. const int N = 100010;
    6.  
    7. int son[N][26], cnt[N], idx;    //因为只包含小写字母，所以每个节点最多有26个子节点
    8. char str[N];
    9.  
    10. void insert(char *str)
    11. {
    12.     int p = 0;  //下标是0的点即是根节点，又是空节点,如son[0][0]为根节点的分支'a'
    13.     for (int i = 0; str[i]; i ++ )  //字符串末尾有'\0'
    14.     {
    15.         int u = str[i] - 'a';
    16.         if (!son[p][u]) son[p][u] = ++ idx;
    17.         p = son[p][u];
    18.     }
    19.     cnt[p] ++ ; //记录这个单词
    20. }
    21.  
    22. int query(char *str)
    23. {
    24.     int p = 0;
    25.     for (int i = 0; str[i]; i ++ )
    26.     {
    27.         int u = str[i] - 'a';
    28.         if (!son[p][u]) return 0;
    29.         p = son[p][u];
    30.     }
    31.     return cnt[p];
    32. }
    33.  
    34. int main()
    35. {
    36.     int n;
    37.     scanf("%d", &n);
    38.     while (n -- )
    39.     {
    40.         char op[2];
    41.         scanf("%s%s", op, str);
    42.         if (*op == 'I') insert(str);
    43.         else printf("%d\n", query(str));
    44.     }
    45.  
    46.     return 0;
    47. }

    最大异或对

    思路：

    字典树不单单可以高效存储和查找字符串集合,还可以存储二进制数字：将每个数以二进制方式存入字典树,找的时候从最高位去找有无该位的异. 

     

     取x的第i位二进制数作为结点

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. int const N=100010,M=31*N;  //M表示trie树的结点个数，即：31个二进制长度*总数
    6.  
    7. int n,idx;
    8. int a[N];
    9. int son[M][2];  //因为只需要存二进制1和0，所以2即可
    10.  
    11. void insert(int x)
    12. {
    13.     int p=0;
    14.     for(int i=30;i>=0;i--)
    15.     {
    16.         int u=x>>i&1;       //取x的第i位二进制数是什么
    17.         if(!son[p][u]) son[p][u]=++idx;
    18.         p=son[p][u];
    19.     }
    20. }
    21.  
    22. int search(int x)
    23. {
    24.     int p=0,res=0;
    25.     for(int i=30;i>=0;i--)  //遍历31个二进制位
    26.     {
    27.         int u=x>>i&1;
    28.         if(son[p][!u])  //为了取异或后最大值，如果有不同的就先走
    29.         {
    30.             p=son[p][!u];
    31.             res=res*2+1;    //异或相异为1，res整体向前挪一位+1
    32.         }
    33.         else
    34.         {
    35.             p=son[p][u];
    36.             res=res*2+0;    //相同为0
    37.         }
    38.     }
    39.     return res;
    40. }
    41.  
    42. int main()
    43. {
    44.     cin>>n;
    45.     for(int i=0;i
    46.     {
    47.         cin>>a[i];
    48.         insert(a[i]);
    49.     }
    50.     int res=0;
    51.     for(int i=0;i
    52.     {
    53.         res=max(res,search(a[i]));
    54.     }
    55.     cout<
    56.     return 0;
    57. }

    并查集

    合并集合

    思路：

    路径压缩具体操作： 

    如图

    find(1) p[1] = 2  p[1] = find(2)
    find(2) p[2] = 3  p[2] = find(3)
    find(3) p[3] = 4  p[3] = find(4)
    find(4) p[4] = 4  将p[4]返回 

    于是一路回溯；4=p[4]=p[3]=p[2]=p[1];
     

    1. #include
    2. using namespace std;
    3.  
    4. int p[100010];
    5.  
    6. int find(int x)
    7. {
    8.     if(p[x]!=x) p[x]=find(p[x]);
    9.     return p[x];
    10. }
    11.  
    12. int main()
    13. {
    14.     int n,m;
    15.     cin>>n>>m;
    16.     for(int i=1;i<=n;i++) p[i]=i;
    17.     while(m--)
    18.     {
    19.         char op;
    20.         int a,b;
    21.         cin>>op>>a>>b;
    22.         if(op=='M') p[find(a)]=find(b); //将a的根插到b的根下，成为b分支
    23.         else 
    24.         {
    25.             if(find(a)==find(b))
    26.                 printf("Yes\n");
    27.             else
    28.                 printf("No\n");
    29.         }
    30.     }
    31.     return 0;
    32. }

    连通块中点的数量

    算法 - 并查集详解：

    http://t.csdn.cn/SsIY9

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

    食物链

    思路

     

    如果不是同一颗树，就把x树插到y树下，成为分支；由前面的合并操作，我们已经算出x到根px的距离d[x],y到根py的距离d[y]；那么如何算px到py的距离呢？

    我们设距离为 ？；

    由于需要满足是同一种类，即最终的x到根距离%3==y到根距离%3

    公式为（d[x]+?）%3==（d[y]）%3;

    简化得  ？=d[y]-d[x];

    1. else if (px != py)  //如果是不同的树
    2. {
    3.     p[px] = py;     //把x树插到y树下，成为分支
    4.     d[px] = d[y] - d[x];    //
    5. }

    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]];    //d[p[x]]就指p[x]到上一个节点的距离，最终d[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;    //有n种动物
    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);     //找x和y的根节点
    37.             if (t == 1) //判断同类，顺手记录
    38.             {
    39.                 if (px == py && (d[x] - d[y]) % 3) res ++ ;     //x和y在同一颗树上，
    40.                                                                 //两个值到根节点的距离%3不同，说明不是同一类
    41.                 else if (px != py)  //如果是不同的树
    42.                 {
    43.                     p[px] = py;     //把x树插到y树下，成为分支
    44.                     d[px] = d[y] - d[x];    //根px到根py的距离
    45.                 }
    46.             }
    47.             else    //判断是否x吃y
    48.             {
    49.                 if (px == py && (d[x] - d[y] - 1) % 3) res ++ ;//x和y在同一颗树上，
    50.                                                            //x值到根节点的距离没有比y距离多1，说明吃不掉
    51.                 else if (px != py)
    52.                 {
    53.                     p[px] = py;
    54.                     d[px] = d[y] + 1 - d[x];    //同理  
    55.                 }
    56.             }
    57.         }
    58.     }
    59.  
    60.     printf("%d\n", res);
    61.  
    62.     return 0;
    63. }
    64.

    堆
     

    堆排序

     思路：

    1、向上调整算法：

    1. void up(int u)
    2. {
    3.     while(u/2&&h[u/2]>h[u])
    4.     {
    5.         swap(h[u/2],h[u]);
    6.         u/=2;
    7.     }
    8. }

    2、向下调整算法 ：

    1. void down(int u)
    2. {
    3.     int t = u;
    4.     if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    5.     if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    6.     if (u != t)
    7.     {
    8.         swap(h[u], h[t]);
    9.         down(t);
    10.     }
    11. }

    如何手写一个堆？完全二叉树 5个操作

    1. 插入一个数         heap[ ++ size] = x; up(size);
    2. 求集合中的最小值   heap[1]
    3. 删除最小值         heap[1] = heap[size]; size -- ;down(1);
    4. 删除任意一个元素   heap[k] = heap[size]; size -- ;up(k); down(k);
    5. 修改任意一个元素   heap[k] = x; up(k); down(k);

    h[i] 表示第i个结点存储的值，i从1开始，2*i是左子节点，2*i + 1是右子节点
    size 既表示堆里存储的元素个数，又表示最后一个结点的下标

    i为什么从n/2开始down？

            因为n是最大值，n/2是n的父节点，因为n是最大，所以n/2是最大的有子节点的父节点，所以从n/2往前遍历，就可以把整个数组的父节点遍历一遍

     如图，我们找到最大父节点5，然后向上遍历4321都是父节点，而5就是n/2

    1. #include 
    2. using namespace std;
    3. int const N = 100010;
    4.  
    5. int h[N], siz; //堆有两个变量h[N]，size; 怎么这里的size和文件里有冲突，只能改成siz了
    6.  
    7. void down(int u)
    8. {
    9.     int t = u;//t存储三个结点中存在的最小的结点的下标，初始化为当前结点u
    10.     if (u * 2 <= siz && h[u * 2] < h[t]) t = u * 2; // 左子节点存在并且小于当前结点，更新t的下标
    11.     if (u * 2 + 1 <= siz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;//右子节点存在并且小于当前结点，更新t的下标
    12.     if (t != u)//如果t==u意味着不用变动，u就是三个结点中拥有最小值的结点下标，否则交换数值
    13.     {
    14.         swap(h[t], h[u]);
    15.         down(t); //交换数值后，t这个结点存储原本u的值，u存储存储t的值（三个数中的最小值）。u不用调整了，但t情况不明，可能需要调整。直到它比左右子节点都小
    16.     }
    17. }
    18.  
    19. int main()
    20. {
    21.     int n, m;
    22.     cin >> n >> m;
    23.     for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]); 
    24.     siz = n; //初始化size,表示堆里有n 个元素
    25.  
    26.     for (int i = n / 2; i; i --) down(i); //把堆初始化成小根堆，从二叉树的倒数第二行开始，把数字大的下沉
    27.  
    28.     while (m -- )
    29.     {
    30.         printf("%d ", h[1]);
    31.         h[1] = h[siz];
    32.         siz --;
    33.         down(1);
    34.     }
    35.  
    36.     return 0;
    37. }
    38.

    模拟堆

    思路：

    操作与堆排序一样，但由于需要插入和删除第k个数，要用额外数组作为指针存储位置，以便快速找到k，于是交换位置的同时也要交换指针

    因为需要插入和删除第k个数，所以需要用hp[]记录idx值，然后用ph[]记录hp[]对应的结点 

     

    理解hp与ph数组，以及为什么需要它们

    • 堆h[i]只能存放数据，不能存放是第几个数字，所以需要ph[k] = i来指明，第k个数字在h[]中对应的i是多少
    • 在执行交换操作的时候，可以直接交换数字,swap(h[a],h[b])
    • 但是对于ph[k_1] = a和ph[k_2] = b来说，a和b是它们存放的值，不 能通过值来找下标，也就是找不k_1,k_2是多少
    • 于是引入hp[a] = k_2，hp[b] = k_2，则可以实现反向的操作

    例如： 

    h[a] = 10, h[b] = 20 swap: h[a] = 20,h [b] = 10
    hp[a] = 1 ,hp[b] = 2 swap:hp[a] = 2 ,hp[b] = 1
    ph[1] = a ,ph[2] = b swap:ph[1] = b ,ph[2] = a

    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. }
    85.

     哈希表

    模拟散列表

    算法 - 哈希表_NO.-LL的博客-CSDN博客

    拉链法：

    1. //拉链法
    2. #include 
    3. #include 
    4. using namespace std;
    5. const int N = 100003;//取大于1e5的第一个质数
    6. int h[N],e[N],ne[N],idx;//开一个h槽,邻接表，h[]表示每个链表头节点，e[]表示x值，ne[]下一个节点下标
    7. int n;
    8. void insert(int x)
    9. {
    10.     int k = (x % N + N) % N;//c++中如果是负数,那他取模也是负的,加N再%N就一定是一个正数
    11.     e[idx] = x;
    12.     ne[idx] = h[k];    //相当于创建单链表
    13.     h[k] = idx++;
    14. }
    15. bool find(int x)
    16. {
    17.     int k = (x % N + N) % N;
    18.     for(int i = h[k];i != -1;i = ne[i])    //遍历链表
    19.     {
    20.         if(e[i] == x) return true;
    21.     }
    22.     return false;
    23. }
    24. int main()
    25. {
    26.     cin >> n;
    27.     memset(h,-1,sizeof h);//先将槽清空，用-1表示
    28.     while(n--)
    29.     {
    30.         string op;
    31.         int x;
    32.         cin >> op >> x;
    33.         if(op == "I")
    34.         {
    35.             insert(x);
    36.         }
    37.         else
    38.         {
    39.             if(find(x))
    40.             {
    41.                 puts("Yes");
    42.             }
    43.             else
    44.             {
    45.                 puts("No");
    46.             }
    47.         }
    48.     }
    49.     return 0;
    50. }

    开放选址法

    1. #include 
    2. #include 
    3. using namespace std;
    4.  
    5. const int N=1e6+9; //开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了（我开了10倍）
    6.                   //开成质数取模时减小冲突概率
    7. const int null=0x3f3f3f3f;    //比1e9大的数（在数据范围找不到的数）
    8. int h[N],n;
    9.  
    10. int find(int x)
    11. {
    12. 	int t=(x%N+N)%N;
    13. 	while(h[t]!=null&&h[t]!=x)  //如果位置不空并且不是x（不是自己）
    14. 	{
    15. 		t++;    //就找下一个位置
    16. 		if(t==N) t=0;    //找到最后一个时再从0开找
    17. 	}
    18. 	return  t;    //如果这个位置是空的, 则返回的是他应该存储的位置
    19. }
    20. int main()
    21. {
    22. 	cin>>n;
    23. 	memset(h,0x3f,sizeof h);    //将每个值变为0x3f3f3f3f（以字节赋值 int4字节）
    24. 	
    25. 	while(n--)
    26. 	{
    27. 		string op;
    28. 		int x;
    29. 		cin>>op>>x;
    30. 		if(op=="I")
    31. 		{
    32. 			h[find(x)]=x;
    33. 		}
    34. 		else
    35. 		{
    36. 			if(h[find(x)]==null) puts("No");
    37. 			else puts("Yes");
    38. 		}
    39. 	}
    40. 	
    41.     return 0;
    42. }

    字符串哈希

    设 h[i]前i个字符的hash值；

     为什么是h[l-1]? 由题意得，在abcdef中2 4为bcde，那么就是h[4]-h[2-1];
    为什么是P^(r-l+1)?  ABCDE 与 ABC 的前三个字符值是一样，只差两位，乘上 P^2 把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。而P^2==p[3]==p[r-l+1](p从0次幂开始）

    1. #include
    2. using namespace std;
    3.  
    4. typedef unsigned long long ull;
    5. const int N=1e5+10,P=131;    //或者P=13331
    6. ull h[N],p[N];    //非常刚好的免去了取模的操作
    7.  
    8. ull find(int l,int r)
    9. {
    10.     return h[r]-h[l-1]*p[r-l+1];    //部分求和
    11. }
    12.  
    13. int main()
    14. {
    15.     int n,m;
    16.     cin>>n>>m;
    17.     string x;
    18.     cin>>x;
    19.     
    20.     p[0]=1;    //p^0==1
    21.     h[0]=0;    //hash表从1开始有值，处理边界
    22.     for(int i=0;i
    23.     {
    24.         p[i+1]=p[i]*P;
    25.         h[i+1]=h[i]*P+x[i];    //前缀和
    26.     }
    27.     
    28.     while(m--)
    29.     {
    30.         int l1,r1,l2,r2;
    31.         cin>>l1>>r1>>l2>>r2;
    32.         if(find(l1,r1)==find(l2,r2)) puts("Yes");
    33.         else puts("No");
    34.         
    35.     }
    36.     return 0;
    37. }


     

  • 相关阅读:
    链动2+1模式系统，是如何成为人、货、场资源流动加速器？
    算法设计与分析 | 输油管道
    Linux进程优先级与环境变量初识
    《canvas》之第7章 变形操作
    Llama 2 70B 问答 - 由人工神经网络训练的程序，与使用编程语言和数学算法编写的程序之间有何区别？
    微前端 - micro-app
    数据库连接池的概念和原理
    AI推介-大语言模型LLMs论文速览（arXiv方向）：2024.01.10-2024.01.20
    热忱与专业齐飞 | 微软最有价值专家项目，广纳微软技术贡献者！
    Linux 多线程多进程
  • 原文地址：https://blog.csdn.net/qq_61386381/article/details/126545392