网络规划设计师教材_知名企业文化_百度一下app下载安装_保定百度首页优化

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;
}