基础算法篇(4)(蓝桥杯常考点)—数据结构（进阶）_青蓝题库数据结构答案

前言

这期将会讲到基础算法篇里面的数据结构（进阶），主要包括单调栈，单调队列，并查集，扩展域并查集，带权并查集，字符串哈希，Trie树。

数据结构(进阶）正文

单调栈

里面存储的单增或者单减的栈

应用:

1.寻找当前元素左侧，离它最近，并且比它大的元素在哪

2.寻找当前元素左侧，离它最近，并且比它小的元素在哪

3.寻找当前元素右侧，离它最近，并且比它大的元素在哪

4.寻找当前元素右侧，离它最近，并且比它小的元素在哪

寻找当前元素左侧，离它最近，并且比它大的元素在哪int a[N]里面存数（已存好）ret里面存的答案stackst;//维护一个单调递减的栈,里面存的是下标for(int i = 1;i<=n;i++){//栈里面小于等于a[i]的元素全部出栈 while(st.size()&&a[st.top()]=1;i--)

寻找当前元素左侧，离它最近，并且比它小的元素在哪int a[N]里面存数（已存好）ret里面存的答案stackst;//维护一个单调递增的栈，里面存的是下标for(i=1;i=a[i])st.pop();//这里的符号是跟上面的唯一区别//此时栈顶元素存在，栈顶元素就是所求结果if(st.size()) ret[i]=st.top();st.push(i); }寻找当前元素右侧，离它最近，并且比它小的元素在哪把上面改为for(int i=n;i>=1;i--)即可//n次逆遍历可以记一下是这个

总结:找左侧，正遍历；找右侧，逆遍历；比它大，单调减；比它小，单调增。//构造___栈例题: 洛谷 P1901 发射站

洛谷 P1901 发射站

单调队列

是一个存单调元素的双端队列

应用:解决滑动窗口内的最大值最小值问题

(前面基础算法的滑动窗口不是用来求其中的最值的)

洛谷 P1886 滑动窗⼝ /【模板】单调队列

例题：洛谷 P1886 滑动窗⼝ /【模板】单调队列int a[N]里面存的元素(已存好)窗口内最大值:从左往右遍历元素，维护一个单调递减的双端队列当前元素进队之后，注意维护队列内的元素在大小为k的窗口内此时队头元素就是最大值代码：dequeq;//存下标for(int i = 1;i<=n;i++){ while(q.size()&&a[q.back()]k) q.pop_front();if(i>=k)cout<<a[q.front()]<<\" \"; }窗口内最小值:从左往右遍历元素，维护一个单调递增的双端队列当前元素进队之后，注意维护队列的元素在大小为k的窗口内此时队头元素就是最小值

并查集

并查集是一种用于维护元素所属集合的数据结构，用双亲表示法来实现

应用eg:维护连通块的信息

相关的一些概念:

查询操作:查找元素x属于哪一个集合，一般会在每个集合中选取一个元素作为代码,查询的是这个集合中的代表元素

合并操作:将元素x所在的集合与元素y所在的集合合并成一个元素

(注意:合并的是元素所属的集合，而并非单单两个元素)

判断操作:判断元素x和y是否在同一个集合

洛谷 P1551 亲戚

并查集的实现:例题：洛谷 P1551 亲戚1.初始化:让元素自己指向自己即可int fa[N];一般并查集用fa来表示for(int i=1;i<=n;i++) fa[i] = i;2.查询操作:就是一直向上\"找爸爸\"(这个find可以多次使用)int find(int x)//查询x所在集合的代表元素是谁return fa[x] == x?x:find(fa[x]);//是x就返回x，不是就find(fa[x])3.合并操作:(重复合并不会出错)让元素x所在集合的代表元素指向元素y所在集合的代表元素void un(int x,int y){ int fx = find(x); int fy = find(y); fa[fx] = fy; }4.判断操作看看两者所在集合的总代表元素是否相同bool issame(int x,int y){ return find(x) == find(y); }

扩展域并查集

元素之间存在多种关系比如:朋友和敌人 而不像上面只存在:亲戚这样一种关系的话，就要用扩展域并查集

和普通并查集的区别:将每个元素拆分成多个域，每个域代表⼀种状态或者关系

洛谷 P1892 [BOI2003] 团伙

例题:洛谷 P1892 [BOI2003] 团伙这里只写不同点:find和un与上面的写法一模一样//两种关系，所以N*2：x的母敌人是x+nint fa[N*2];//初始化:for(int i=1;i<=n*2;i++) fa[i]=i;while(m--)//m是题目中的\"m个关系\"{ if(op == \'F\') un(x,y); else//敌人，读取的是y和x是敌人关系 {//存法:这俩都得写，少一个都不行 un(x,y+n);//这两是朋友关系 un(y,x+n);//这两是朋友关系 }}

带权并查集

概念:就是在普通并查集的基础上，为每个结点增加一个权值。这个权值可以表示当前结点与父结点之间的信息(因为find那我们用的路径压缩，因为最终这个权值是当前结点相对于根节点的信息)

洛谷 P1196 [NOI2002] 银河英雄传说

带权并查集的一些操作:(这里的d[N]以到父结点的距离为例)例题:洛谷 P1196 [NOI2002] 银河英雄传说新加了一个d[N]1.初始化:多初始化个d[i]即可2.查询操作:(对这种代码来说，一个结点只能进行一次这种find操作!)int find(int x){ if(fa[x]==x) return x; int t = find(fa[x]);//这一步要先搞 d[x]+=d[fa[x]];//不为距离时可能会变为其他return fa[x] = t;//完成路径压缩}3.合并操作://x所在集合与y所在集合合并，x与y之间的权值是wvoid un (int x,int y, int w){ int fx = find(x),fy = find(y);if(fx!=fy) { fa[fx] = fy; d[fx]= d[y]+w-d[x]; //可能会变，这里是拿距离举例的 } }4.查询操作://查询y与x之间的距离int query(int x,int y){ int fx = find(x),fy = find(y);//如果不在同一个集合中，说明距离未知(具体返回什么要看题意） if(fx!=fy)return 0x3f3f3f3f;return d[y]-d[x];}

字符串哈希

一般利用前缀和思想去预处理字符串汇总每个前缀的哈希值

（使用前提:需要多次询问一个字符串的子串的哈希值）

核心思想:把字符串映射成P进制数字

P一般选择13331或者131

字符串哈希的作用:

字符串哈希一般用于判断两个字符串及其各子串是否相等

(和字典树的区别是这个字符串哈希侧重于判断功能)

洛谷 P10468 兔⼦与兔⼦

例题:洛谷 P10468 兔⼦与兔⼦前缀字符串哈希模板:typedef unsigned lon long ULL;P = 13331;int len;string s;//一般都要搞一下s = \' \'+s;来让i从1开始搞ULL f[N];//前缀哈希数组ULL p[N];//记录P的i次方－>p[i]为P的i次方//处理前缀哈希数组以及P的i次方数组void init_hash(){ f[0] = 0;p[0] = 1; for(int i = 1;i<=len;i++) { f[i]=f[i-1]*P+s[i]; p[i]=p[i-1]*P; } }//快速求得任意区间的哈希值ULL get_hash(int l,int r){ return f[r]-f[l-1]*p[r-l+1]; }如果题目只是简单的求单个字符串的哈希值:ULL gethash(){ ULL ret = 0; for(int i =1;i<=len;i++) { ret = ret*p+s[i]; } return ret; }

Trie树（又叫字典树或前缀树）

是一种能够快速插入和查询字符串的数据结构

理解:我们可以把字典树想象成一颗多叉树，每一条边代表一个字符，从根节点到某个节点的路径就代表了一个字符串

作用:

1.查询某个单词是否出现过，并且出现几次

2.查询有多少个单词是以某个字符串为前缀

3.查询所有以某个前缀开头的单词

字典树的实现:默认需要存的全是小写字母1.准备工作 int tree[N][26],p[N],e[N];//N一般令为所有字符串中一共有多少个字符// p[i]表示第i个被开辟的点被经过了多少次，//e[i]表示以第i个被开辟的点为结尾的有多少个int idx;2.插入字符串void insert(string&s){ int cur = 0;//从根节点开始 p[cur]++;//这个格子经过一次 for(auto ch:s) {//这个path的表达式常改!!!依据题意改 int path = ch - \'a\'; //如果没有路 if(tree[cur][path] == 0) tree[cur][path]= ++idx; cur = tree[cur][path]; p[cur]++ } e[cur]++;}3.查询字符串出现的次数:int find(string&s){ int cur = 0; for(auto ch:s) { int path = ch - \'a\'; if(tree[cur][path] == 0) return 0; cur = tree[cur][path]; } return e[cur]; }4.查询有多少个单词以字符串s为前缀: int find_pre(string&s){ int cur = 0; for(auto ch:s) { int path = ch-\'a\'; if(tree[cur][path] == 0) return 0; cur = tree[cur][path]; } return p[cur]; }例题:洛谷 P2580 于是他错误的点名开始了

洛谷 P2580 于是他错误的点名开始了