CF797D Broken BST
2022/1/3 23:11:11
本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升
- 2024-05-08代码报错不用愁,CodeGeeX一键完成代码修复、错误解释的功能上线了!
- 2024-05-08今天开始程序员不用再发愁写commit message了,全部由CodeGeeX自动完成!