数据结构--算法篇

发布于:2025-03-15 ⋅ 阅读:(9) ⋅ 点赞:(0)

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;
			else
			cout<<'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;
		else
		cout<<"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;
}

网站公告

今日签到

点亮在社区的每一天
去签到