每日总结2022.1.5(求先序排列、并查集)-创新互联

get到新知识,心情愉悦。

创新互联公司凭借专业的设计团队扎实的技术支持、优质高效的服务意识和丰厚的资源优势,提供专业的网站策划、成都做网站、网站设计、网站优化、软件开发、网站改版等服务,在成都10年的网站建设设计经验,为成都上千多家中小型企业策划设计了网站。

先看先序排列

P1030 [NOIP2001 普及组] 求先序排列https://www.luogu.com.cn/problem/P1030

题目描述

给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,且二叉树的节点个数 ≤8)。

输入格式

共两行,均为大写字母组成的字符串,表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串,表示一棵二叉树的先序。

输入输出样例

输入 #1复制

BADC
BDCA

输出 #1复制

ABCD
说明/提示

【题目来源】

NOIP 2001 普及组第三题

思路:在草稿纸上多次手工遍历,找出由中后序排列->先序排列的规律,先从后序最后一个字母(这就是根)开始A,在中序知道对应的字母,将中序分成俩部分,依据中序的俩部分,将后序分成俩部分,左边一部分是A的左子树,右边一部分是A的右子树。以此类推。。。先序为根左右,所以先把根输出,然后递归左半然后右半。

代码实现:

#includeusing namespace std;
void DLR(char *m,char *b,int l,int r,int i,int j)
{
	if(i==j)
	{
		printf("%c",b[j]);
		return;
	}
	for(int k=l;k<=r;k++)
	{
		if(m[k]==b[j])
		{
			printf("%c",b[j]);
			if(k-1>=l) DLR(m,b,l,k-1,i,i+(k-1-l));
			if(k+1<=r) DLR(m,b,k+1,r,j+k-r,j-1);
			break;
		}
	}
}
int main()
{
	char m[30];
	char b[30];
	cin>>m>>b;
	int len=strlen(m);
	DLR(m,b,0,len-1,0,len-1);
	return 0;
}
//ABEDFCHG
//AEFDBHGC

新知识:并查集P3367 【模板】并查集https://www.luogu.com.cn/problem/P3367

并查集,合并与查询,是一种树结构。原来判断两个对象之间的关系,有关系和没关系。无法得出具体关系。

通过数组parent[x]=x_father来模拟两个元素之间的结点与孩子的关系,x的结点是x_father。

比如如果要合并1和2所在的集合,就要把1和2所在的那棵树的根找出来(find),然后将一个根接在(connect)另一个根上面,一个为结点,一个为子树。

题目描述

如题,现在有一个并查集,你需要完成合并和查询操作。

输入格式

第一行包含两个整数N,M ,表示共有 N 个元素和 M 个操作。

接下来 MM 行,每行包含三个整数 Zi,Xi,Yi​ 。

当 Zi=1 时,将Xi​ 与Yi​ 所在的集合合并。

当 Zi​=2 时,输出 Xi​ 与Yi​ 是否在同一集合内,是的输出 Y;否则输出 N

输出格式

对于每一个 Zi​=2 的操作,都有一行输出,每行包含一个大写字母,为 Y或者 N

输入输出样例

输入 #1复制

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

输出 #1复制

N
Y
N
Y
说明/提示

对于30% 的数据,N≤10,M≤20。

对于 70% 的数据,N≤100,M≤103。

对于 100% 的数据,1≤N≤104,1≤M≤2×105,1≤Xi​,Yi​≤N,Zi​∈{1,2}。

代码实现:

#includeusing namespace std;

int find_root(int x,int *parent)
{
	int x_root=x;
	while(parent[x_root]!=0)
	{
		x_root=parent[x_root];
	}
	return x_root;
}

int connect(int x,int y,int *parent)
{
	int x_root=find_root(x,parent);
	int y_root=find_root(y,parent);
	if(x_root==y_root)
	{
		return 0;
	}
	else
	{
		parent[x_root]=y_root;
		return 1;
	}
}
int main()
{
	int parent[10000+5]={0};
	int Z,M,N;
	cin>>N>>M;
	int x,y;
	while(M--)
	{
		cin>>Z>>x>>y;
		if(Z==1) connect(x,y,parent);
		else
		{
			if(find_root(x,parent)==find_root(y,parent)&&find_root(x,parent)!=0)
			{
				printf("Y\n");
			}
			else
			{
				printf("N\n");
			}
		}
	}
	return 0;
}

由于这里在合并的时候总是,左边那个集合连上右边那个集合,会导致树的深度过长,在find的时候会花费额外的时间,以至于提交结果时间超限

所以要将深度小的接在深度长的上面,就需要多定义一个数组deep 来存储深度

#includeusing namespace std;

int find_root(int x,int *parent)
{
	int x_root=x;
	while(parent[x_root]!=0)
	{
		x_root=parent[x_root];
	}
	return x_root;
}

int connect(int x,int y,int *parent,int *deep)
{
	int x_root=find_root(x,parent);
	int y_root=find_root(y,parent);
	if(x_root==y_root)
	{
		return 0;
	}
	else
	{
		if(deep[x_root]>deep[y_root])
		{
			parent[y_root]=x_root;
		}
		else if(deep[y_root]>deep[x_root])
		{
			parent[x_root]=y_root;
		}
		else
		{
			parent[y_root]=x_root;
			deep[x_root]++;
		}
		return 1;
	}
}
int main()
{
	int parent[10000+5]={0};
	int deep[10000+5]={0};
	int Z,M,N;
	cin>>N>>M;
	int x,y;
	while(M--)
	{
		cin>>Z>>x>>y;
		if(Z==1) connect(x,y,parent,deep);
		else
		{
			if(find_root(x,parent)==find_root(y,parent)&&find_root(x,parent)!=0)
			{
				printf("Y\n");
			}
			else
			{
				printf("N\n");
			}
		}
	}
	return 0;
}

AC,不过谁能告诉我这个N有什么用????满脸疑惑

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


文章标题:每日总结2022.1.5(求先序排列、并查集)-创新互联
URL标题:http://myzitong.com/article/gcggp.html