数据结构--算法篇
- 1 单调栈
- 1.1 什么是单调栈
- 1.2 发射站
- 1.3 代码
- 2.单调队列
- 2.1 滑动窗口 /【模板】单调队列
- 2.2 代码
- 2.3 质量检测
- 2.4 代码
- 3、并查集
- 3.1 双亲表⽰法
- 3.2 并查集的概念
- 3.3 并查集的实现
- 3.4 亲戚
- 代码
- 4. 扩展域并查集
- 4.1 团伙
- 代码
- 5、带权并查集
- 5.1 食物链
- 代码
- 5.2 银河英雄传说
- 代码
- 6 字符串哈希
- 6.1 字符串哈希(模版)
- 代码
- 6.2 兔子与兔子
- 代码
- 7.trie树
- 7.1 字典树(模版)
- 代码
1 单调栈
1.1 什么是单调栈
单调栈,顾名思义,就是具有单调性的栈。它依旧是⼀个栈结构,只不过⾥⾯存储的数据是递增或者
递减的。这种结构是很容易实现的(如下⾯的代码),但重点是维护⼀个单调栈的意义是什么?
单调栈解决的问题
单调栈能帮助我们解决以下四个问题:
• 寻找当前元素左侧,离它最近,并且⽐它⼤的元素在哪;
• 寻找当前元素左侧,离它最近,并且⽐它⼩的元素在哪;
• 寻找当前元素右侧,离它最近,并且⽐它⼤的元素在哪;
• 寻找当前元素右侧,离它最近,并且⽐它⼩的元素在哪。
虽然是四个问题,但是原理是⼀致的。因此,只要解决⼀个,举⼀反三就可以解决剩下的⼏个。
1.2 发射站
https://www.luogu.com.cn/problem/P1901
1.3 代码
2.单调队列
单调队列,顾名思义,就是存储的元素要么单调递增要么单调递减的队列。注意,这⾥的队列和普通的队列不⼀样,是⼀个双端队列。
⼀般⽤于解决滑动窗⼝内最⼤值最⼩值问题,以及优化动态规划。
2.1 滑动窗口 /【模板】单调队列
2.2 代码
2.3 质量检测
https://www.luogu.com.cn/problem/P2251
2.4 代码
3、并查集
3.1 双亲表⽰法
接下来要学习到的并查集,本质上就是⽤双亲表⽰法实现的森林。因此,我们先认识⼀下双亲表⽰
法。
在学习树这个数据结构的时,讲到树的存储⽅式有很多种:孩⼦表⽰法,双亲表⽰法、孩⼦双亲表⽰
法以及孩⼦兄弟表⽰法等。对⼀棵树⽽⾔,除了根节点外,其余每个结点⼀定有且仅有⼀个双亲,双
亲表⽰法就是根据这个特点存储树的,也就是把每个结点的双亲存下来。因此,我们可以采⽤数组来
存储每个结点的⽗亲结点的编号,这就实现了双亲表⽰法(so easy)。
但是,在实现并查集的时,我们⼀般让根节点⾃⼰指向⾃⼰。因此,上述存储就变成:
3.2 并查集的概念
在有些问题中,我们需要维护若⼲个集合,并且基于这些集合要频繁执⾏下⾯的操作:
• 查询操作:查找元素 x 属于哪⼀个集合。⼀般会在每个集合中选取⼀个元素作为代表,查询的是
这个集合中的代表元素;
• 合并操作:将元素 x 所在的集合与元素 y 所在的集合合并成⼀个集合;(注意,合并的是元素所
在的集合,不是这两个元素!)
• 判断操作:判断元素 x 和 y 是否在同⼀个集合。
并查集(Union Find):是⼀种⽤于维护元素所属集合的数据结构,实现为⼀个森林,其中每棵树表
⽰⼀个集合,树中的节点表⽰对应集合中的元素,根节点来代表整个集合。
3.3 并查集的实现
#include<iostream>
using namespace std;const int N=2e5+10;
int n,k;
int f[N];int find(int x)
{if(f[x]==x) return x;return f[x]=find(f[x]);
}int main()
{cin>>n>>k;for(int i=1;i<=n;i++) f[i]=i;while(k--){int z,x,y;cin>>z>>x>>y;if(z==1){int xx=find(x),yy=find(y);f[xx]=yy;}else{if(find(x)==find(y))cout<<'Y'<<endl;elsecout<<'N'<<endl;}}return 0;
}
3.4 亲戚
https://www.luogu.com.cn/problem/P1551
代码
#include<iostream>
using namespace std;int n,m,p;
const int N=5010;
int f[N];int find(int x)
{if(f[x]==x) return x;return f[x]=find(f[x]);
}int main()
{cin>>n>>m>>p;for(int i=1;i<=n;i++) f[i]=i;while(m--){int x,y; cin>>x>>y;int xx=find(x),yy=find(y);f[yy]=xx;}while(p--){int x,y; cin>>x>>y;if(find(x)==find(y))cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0;
}
4. 扩展域并查集
4.1 团伙
https://www.luogu.com.cn/problem/P1892
代码
#include<iostream>
using namespace std;int n,m;
const int N=1e3+10;
int f[N*2];int find(int x)
{if(f[x]==x) return x;return f[x]=find(f[x]);
}void uni(int x,int y)
{int xx=find(x),yy=find(y);f[yy]=xx;
}int main()
{cin>>n>>m;for(int i=1;i<=2*n;i++) f[i]=i;while(m--){char ch;int x,y;cin>>ch>>x>>y;if(ch=='E'){uni(x,y+n);uni(y,x+n);}else{uni(x,y);}}int ret=0;for(int i=1;i<=n;i++){if(f[i]==i) ret++;}cout<<ret;return 0;
}
5、带权并查集
5.1 食物链
代码
#include <iostream>
using namespace std;int n,k;
const int N=5e4+10;
int f[N],d[N]; int find(int x)
{if(f[x]==x) return x;int t=find(f[x]);d[x]+=d[f[x]];return f[x]=t;
}void uni(int x,int y,int w)
{int fx=find(x),fy=find(y);if(fx!=fy){f[fx]=fy;d[fx]=d[y]+w-d[x];}
}int main()
{cin>>n>>k;for(int i=1;i<=n;i++) f[i]=i;int ret=0;while(k--){int op,x,y; cin>>op>>x>>y;int fx=find(x),fy=find(y);if(x>n||y>n) ret++;else if(op==1){if(fx==fy&&((d[y]-d[x])%3+3)%3!=0) ret++;else uni(x,y,0);}else{if(fx==fy&&((d[y]-d[x])%3+3)%3!=1) ret++;else uni(x,y,2);}}cout<<ret;return 0;
}
5.2 银河英雄传说
https://www.luogu.com.cn/problem/P1196
代码
#include<iostream>
#include<cmath>
using namespace std;const int N=3e4+10;
int f[N],d[N],cnt[N];
int t;int find(int x)
{if(f[x]==x) return x;int t=find(f[x]);d[x]+=d[f[x]];return f[x]=t;
}void uni(int x,int y)
{int fx=find(x),fy=find(y);if(fx!=fy){f[fx]=fy;d[fx]=cnt[fy];cnt[fy]+=cnt[fx];}
}void quary(int x,int y)
{int fx=find(x),fy=find(y);if(fx!=fy) cout<<-1<<endl;else{cout<<abs(d[x]-d[y])-1<<endl;}
}int main()
{for(int i=1;i<=N;i++){f[i]=i;cnt[i]=1;}cin>>t;while(t--){char op; int x,y;cin>>op>>x>>y;if(op=='M'){uni(x,y);}else{quary(x,y);}}return 0;
}
6 字符串哈希
6.1 字符串哈希(模版)
代码
#include<iostream>
#include<algorithm>
using namespace std;typedef unsigned long long ULL;
const int N=1e4+10;
int n;
ULL p[N];
int k=131;ULL gethash(string &s)
{ULL ret=0;for(int i=1;i<=s.size();i++){ret=ret*k+s[i-1];}return ret;
}int main()
{cin>>n;for(int i=1;i<=n;i++){string s; cin>>s;p[i]=gethash(s);}sort(p+1,p+1+n);int ret=1;for(int i=2;i<=n;i++)if(p[i]!=p[i-1]) ret++;cout<<ret;return 0;}
6.2 兔子与兔子
https://www.luogu.com.cn/problem/P10468
代码
#include<iostream>
using namespace std;const int N=1e6+10;
typedef unsigned long long ULL;
ULL f[N],p[N];
int m,n;
int k=131;
string s;void init_hash()
{p[0]=1;for(int i=1;i<=n;i++){f[i]=f[i-1]*k+s[i];p[i]=p[i-1]*k;}
}ULL gethash(int l,int r)
{return f[r]-f[l-1]*p[(r-l+1)];
}int main()
{cin>>s;cin>>m;n=s.size();s=" "+s;init_hash();while(m--){int l1,r1,l2,r2; cin>>l1>>r1>>l2>>r2;ULL x=gethash(l1,r1),y=gethash(l2,r2);if(x==y) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;}
7.trie树
7.1 字典树(模版)
https://www.luogu.com.cn/problem/P8306
代码
#include<iostream>
using namespace std;const int N=3e6+10;
int tree[N][62];
int p[N];
int n,q,indx;int get_num(char ch)
{if(ch>='a'&&ch<='z') return ch-'a';else if(ch>='A'&&ch<='Z') return ch-'A'+26;else return ch-'0'+52;
}void insert(string &s)
{int cur=0;p[cur]++;for(auto &c: s){int path=get_num(c);if(tree[cur][path]==0) tree[cur][path]=++indx;cur=tree[cur][path];p[cur]++;}
}int find(string &s)
{int cur=0;for(auto &c: s){int path=get_num(c);if(tree[cur][path]==0) return 0;cur=tree[cur][path];}return p[cur];
}int main()
{int T; cin>>T;while(T--){for(int i=0;i<=indx;i++)for(int j=0;j<62;j++)tree[i][j]=0;for(int i=0;i<=indx;i++) p[i]=0;indx=0;cin>>n>>q;while(n--){string s; cin>>s;insert(s);}while(q--){string s; cin>>s;cout<<find(s)<<endl;}}return 0;
}