竞赛讨论区 > 【每日一题之暑假特别计划】7月8日精讲—Alliances
头像
是瑶瑶呀
编辑于 2020-07-11 16:35
+ 关注

【每日一题之暑假特别计划】7月8日精讲—Alliances


活动时间:7月7日起至9月1日
活动内容:写当日题解,活动时间内一共写满30篇每日一题的题解
活动奖励:即可额外获得牛客T恤一件
活动目的:滴滴滴~想充实的过完这个暑假嘛~快来写每日一题~每天都要进步喔~提升自己的同时还有超多福利喔~


每日一题交流群,群内定期有福利发放,群号:659028468

今日每日一题预告
题号 NC13950
名称 Alliances
来源 牛客练习赛2
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

先任意找一个点作为根,要知道帮派控制的路径肯定需要知道LCA——使用LCA找到这些帮派占领的最高点(共同的LCA),帮派进行联盟的时候用他们分别的LCA再求LCA。此时首都有三个情况:
1.不是这个LCA的子孙,此时所求的距离就是它到这个LCA的距离;
2.如果首都是直接被占领的城市,他和某个帮派(直接)占领的城市求LCA就会是他自己(也就是说他的某个儿子被占领了),但是我们肯定不能去枚举帮派占领的城市,我们考虑去帮派(直接)占领的城市里面找一个最有可能是首都儿子的城市,显然是dfs序(就是dfs的顺序)中它右边第一个被占领的城市;
3.如果首都是LCA的子孙但是没有被占领,可以把dfs序中他左边和右边离他最近的两个点拿出来和首都求LCA,这两个LCA里面一定有一个是离它最近的。(情况2其实可以合并在3里面处理)
在DFS序上找离一个点最近的左边和右边的点需要用到二分。

活动奖励:

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

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

.牛币兑换中心

牛客博客开通方式

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

提醒:更新昨天题解!
看完邓老师的题解,记得自己去做题提高呀~

全部评论

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

本文相关内容

等你来战

查看全部

热门推荐