C/C++教程

CF797D Broken BST

本文主要是介绍CF797D Broken BST,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

洛谷题面

顺着树剖的推荐题目点进来的,没想到压根不是树剖,代码还很短 \(\verb!qwq!\)。

题目大意

给定一棵 \(\rm BST\),但是不保证这是一棵正确的 \(\rm BST\)。

请计算有多少节点不会被遍历到。

题目分析

在 \(\rm BST\) 中,节点 \(u\) 一定满足 \(val[ls(u)]<val[u],val[rs(u)]>val[u]\),根据这个性质,一个数能够被找到当且仅当 \(l<val[u]<r\)。

在 \(\rm dfs\) 过程中,我们使用 \(map\) 来映射每个节点是否被找到,最后查找就很方便。

于是就做完了。

代码

注意 dfs(rt,-1,1e9+1),因为 \(\rm dfs\) 中我们是 <>,所以这里应当满足 \(l\ge0-1,r\le10^9+1\)。

//2022/1/3

const int ma=1e5+5;

int a[ma],ls[ma],rs[ma];

bool have_fa[ma];

int n;

map<int,bool>mp;

inline void dfs(int now,int l,int r)
{
	if(now==-1)
	{
		return;
	}
	
	if(a[now]>l && a[now]<r)
	{
		mp[a[now]]=true;
	}
	
	dfs(ls[now],l,min(r,a[now]));
	
	dfs(rs[now],max(l,a[now]),r);
}

int main(void)
{
	n=read();
	
	for(register int i=1;i<=n;i++)
	{
		a[i]=read(),ls[i]=read(),rs[i]=read();
		
		if(ls[i]!=-1)
		{
			have_fa[ls[i]]=true;
		}
		
		if(rs[i]!=-1)
		{
			have_fa[rs[i]]=true;
		}
	}
	
	int rt;
	
	for(register int i=1;i<=n;i++)
	{
		if(have_fa[i]==false)
		{
			rt=i;
			
			break;
		}
	}
	
	dfs(rt,-1,1e9+1);
	
	int ans=0;
	
	for(register int i=1;i<=n;i++)
	{
		if(mp[a[i]]==false)
		{
			ans++;
		}
	}
	
	printf("%d\n",ans);
	
	return 0;
}
这篇关于CF797D Broken BST的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!