竞赛讨论区 > 【每日一题】4月8日题目精讲 树 贪心
头像
王清楚
编辑于 2020-04-08 17:01
+ 关注

【每日一题】4月8日题目精讲 树 贪心

题号 NC13249
名称 黑白树
来源 美团2017年CodeM大赛-初赛B轮
戳我进入往期每日一题汇总贴~
注:如果你在题库做题时遇到了喜欢的题目,欢迎推荐~ 点击查看详情

看到树想一边搜一边处理大概率都是可以的(也有例外,比如昨天那个题就根本和这棵树的样子没什么关系。)首先,我们可以很容易的知道:由于每个点都是向上覆盖的,所以凡是不能被下面的点覆盖上的点都必须要选,而能被子孙节点覆盖的点就一定不选了吗?不一定,反例如图1
图1
叶子节点6一定得选,这个时候5和4都在他的覆盖范围内,如果都不选,3没被覆盖,要选,2要选1要选,一共选了4个点,但是事实上我们选6和5就行了。

(知道了这个贪心策略不对之后我们要去考虑哪里不对,知其然并且知其所以然,了解一个想法为什么错和了解一个想法为什么对是一样的重要,也许你就已经能把这个问题解决了。)

我们还是看上图:当我们按照能覆盖上就不选的方法从下往上选的时候,发现了3没有被下方的点覆盖,我们要做的事情其实是找个点(可能是自己可能是下方的点)覆盖了它,而不仅仅是选择它,在这个例子中显然选择5比选择3更好——这两种选择都能满足覆盖3,但是选择5能到覆盖更上方的点。也就说说,我们真正的策略应该是,当一个点没有被下方已经选了的点覆盖到的时候,我们选择一个它或者它下方的能向上覆盖的最远的点。另外,其实我们也并不关心这个点选的哪个,只需要知道往上能覆盖多远就行了,这个值其实可以直接维护到k数组里面,即我认为由于图中5号点的存在,在dfs返回上方的过程中,我们就可以认为k[4]值是9,k[3]是8(选6来替代选3/4)……

我们用一个f[x]表示在x的子树都被覆盖的当前选择下,最远能往x的上方覆盖多远,f[x] = max(f[son] - 1) ,son是x的儿子。(如果这个点还没选,那么它不会用来更新f的值的,即dfs(4)的时候f[4]是等于0的)

如果一个点所有的儿子都不能向上覆盖到它了,那就在找个点及其子树里面选一个能往上覆盖最远的把它覆盖了,选择的点数+1,且f值被k值更新,如果子树还能覆盖到它,就不用在这里选了(在考虑子树被覆盖的问题的时候就已经选过了。)
代码可戳我查看~

看完邓老师的题解,记得自己去做题提高呀~
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目4月15日中午12:00之前写的题解有获得牛币资格~

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

(33) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐