【每日一题】3月31日题目精讲 树上倍增 ST表

题号 NC13331
名称 城市网络
首先给大家道个歉,最开始这题数据有点问题,把什么暴力都放过去了……现在数据锅已修,请之前使用暴力,最坏可能达到O(nq)的算法的同学去重测一下呀!真的十分抱歉!

我们来先说说大家都喜闻乐见的暴力,因为题目说保证 v 在 u 前往根的最短路径上,所以只要一遍dfs维护出每个点的父亲,然后每次顺着父亲一路走上去就可以了,这个的复杂度最坏情况是O(nq)的(退化成一条链的情况),是过不了的(出题人一般是不可能放这种复杂度过去的,但是赛场上如果你没有别的办法的时候其实试一下也未尝不可,毕竟没ac不亏,ac了血赚。)

-------------------------------------------以下是讲倍增的分割线--------------------------------

本题用到的方法是树上倍增,在分析本题解法之前我们先来讲讲倍增这个算法思想:

倍增和分治是对称的算法思想,分治的意思是“分而治之”,是将一个大问题分解成若干个小问题,然后解决了小问题再将小问题的解合并为大问题的解,而倍增直接从小问题出发,层层合并成大问题的解(个人看来,一定程度上,你也可以认为倍增是分治的合并过程)。

倍增的最基础应用应该是ST表,这里也顺便介绍给大家:
ST 表(Sparse Table)实际上是一种动态规划的方法,或者说简单一点,是用统计的思想来解决问题,它主要用于求解区间最大/最下值问题(也可也用来求和或者其他的东西)。以求区间最大值为例,它的基本思想是:用维护从从i开始长度为的区间的最大值,例如 表示的是以1开始长度为2的区间的最大值,表达的是以1开始长度为4的区间的最大值。我们可以看到 每增加1,区间的长度乘以二,于是两个相邻区间合并就可以得到当前这个长度的区间的最大值了,也就是说,这样的时间复杂度我们就可以维护出f数组。


知道了f数组我们怎么来求任意区间[l,r]的最大值呢?也很简单,我们用两个长度刚好大于(r-l+1)/2的区间拼起来就好了(一个左边界是l,一个右边界是r)

参考代码
void rmp_st(int n) //预处理ST表,数组中有n个元素
{
    for(int i = 1; i <= n; i++) f[i][0] = a[i];
    int m = (int)(log((double)n) / log(2.0));
    for(int j = 1; j <= m; j++)//先循环j再循环i,因为必须要把长度为1的区间都算出来了才能求长度为2的
    for(int i = 1; i+(1<<j)-1 <= n; i++)
        f[i][j] = min(f[i][j-1], f[i+(1<<(j-12))][j-1]);
}
int rmp_find(int l, int r)  //求区间 l 到 r 之间的最值
{
    int k = (int)(log(1.0 * (r-l+1)) / log(2.0));
    return min(f[l][k], f[r-(1<<k)+1][k]);
}
------------------------------------------------以下是本题题解的分界线-------------------------------------------------

做题的第一步是好好读题,而在读题过程中你需要将题目的信息转化成对你解题有用的信息,比如所“假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀(价值更高,即严格大于),那么你就会选择购入。”这句话实际上是说明你买到的珠宝的价值是递增的,而且请注意,不是求最长上升子序列哪一种,而是只要递增了就要选,而这个递增呢就会告诉你,如果你在A城市买了珠宝,那么从A往上走下一次在哪里卖珠宝或者你从A往上走x个城市能买到几个珠宝和你是从哪里走到A的并没有关系,而当我们从A 往上走的时候,A上方比他小的点也是没有意义的。

考虑用表示从i往上走,能买珠宝的第个点是哪个,显然,如果我们知道每个的值, 那么 ( 往上的第个点再往上个点)。那么怎么求呢?肯定不能暴力,因为暴力最坏情况可能会让你每次都跑到根(构造一条链,从根到叶子价值递增)。这个其实也可也倍增着跳——如果 的父亲fa比 大那自不必说,当i的父亲fa比 小,那么我们可以看fa的父亲向上走(k从大到小枚举)个能买进的点的权值(即),如果这个点权限比 点权值小,说明还需要往上走,就跳到f[fa] [k]上并把跳跃的长度减少一半(如果还是刚刚的跳跃高度,从f[fa] [k]往上跳长度,实际上就是从fa跳,相当于就是跳到了);如果这个点的权值比 大,说明跳多了,就只是把跳跃长度减少一半再看。

注意我这里说的跳跃长度都是按照能买东西的点的个数计数,相当于我的f数组其实是对原树进行了重建,每个点往上走1步都的连向的它能到的第一个比他大的点(这样理解也许会容易很多——即我们对原树进行变形,每个点都连向它上方第一个能买东西的点,构成一个新的森林,于是问题就变成了,从u走到自己上方深度不小于dep[v]的点需要经过多少个点)。

有了这个值之后我们要求从 u 往上走到 v 经过了多少点,也可也倍增去求了——即从 u 出发尝试往上跳 高度,如果已经跳过 v 了,就减小 k,如果没有跳到 v 的上方,就先跳上去再减小 k。 注意,因为f数组存的能买东西的点,很有可能v根本不在这里面,所有跳的时候是通过判断深度来判断是否结束的。

我手算了一组样例帮助大家理解,我记得是lrj的紫书里面说过,学习数据结构最好的办法就手画,希望大家能动起手来,多写写多画画。

还要最后一个问题,题目说“每次行程开始时,你手上有价值为 c 的珠宝”这个限制怎么办?很简单,在 u 点的下方接一个权值为 c 的点,然后从这个点开始往上走就可以了!

------------------------------------------------看过大家题解之后的补充-------------------------------------------------
9楼的@AROY 同学在题解里贴了一道题目,推荐大家去做一下~
【再贴一道ST表,理解倍增思想】
给你一个长为 n 的序列 a 和一个常数k
有 m 次询问,每次查询一个区间 [l,r] 内所有数最少分成多少个连续段,使得每段的和都 <= k
如果这一次查询无解,输出"Chtholly"

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

活动奖励:

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

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

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/30530d8825cd44c087f7a2ebb88461af
点赞 回复 分享
发布于 2020-03-30 13:10
https://blog.nowcoder.net/n/f430b3bea40a4a5f9172efad31b8615f
1 回复 分享
发布于 2020-05-03 23:34
强上线段树:https://blog.nowcoder.net/n/63a0fe8e371e40f696298a3469f3eb75
1 回复 分享
发布于 2020-03-30 23:22
正解:https://blog.nowcoder.net/n/f1629afe86e445e39f26f4b58bec96f5
1 回复 分享
发布于 2020-03-30 14:58
题解中ST表求解最大值好像错啦,原来初始化的时候是f[i][j] = min(f[i][j-1], f[i+(1<<j)][j-1]); 应该是f[i][j] = max(f[i][j-1], f[i+(1<<(j-1))][j-1]);  不知道这么迟了能不能看到QAQ
点赞 回复 分享
发布于 2020-07-03 19:18
https://blog.nowcoder.net/n/ec31faf3e0984a09990e113c74d24466
点赞 回复 分享
发布于 2020-06-26 15:17
https://blog.nowcoder.net/n/28396c4433864c66beaa50d35d325ac8
点赞 回复 分享
发布于 2020-05-03 16:48
https://blog.nowcoder.net/n/ef06f19245b147b1a5b9b9441238a423
点赞 回复 分享
发布于 2020-05-01 16:41
来份在线代码,提供v不在u到根的路径上的情况的思路 https://blog.nowcoder.net/n/8528cf017ee148a1b98e994cd110335a
点赞 回复 分享
发布于 2020-04-08 22:21
https://blog.nowcoder.net/n/63d2a8ddcfe245abbb016e498c2bc970
点赞 回复 分享
发布于 2020-04-07 01:16
https://blog.nowcoder.net/n/f2ab41d6afe54fb1a2ca78f81a922598
点赞 回复 分享
发布于 2020-04-05 10:53
https://blog.nowcoder.net/n/73ed26e79999479e97b1847579c64a64
点赞 回复 分享
发布于 2020-04-05 00:19
https://blog.nowcoder.net/n/bc3b7488aa474084b73ce50ee0c1fd50
点赞 回复 分享
发布于 2020-04-04 14:39
https://blog.nowcoder.net/n/0a6f81c2194944078dd3b6518fdb1bed
点赞 回复 分享
发布于 2020-04-02 20:44
https://blog.nowcoder.net/n/50ab8a44f339434b873a19cc49b2f41b
点赞 回复 分享
发布于 2020-04-02 17:48
https://blog.nowcoder.net/n/4baef88638d745ad8b04faaa4c5f5f61
点赞 回复 分享
发布于 2020-04-02 15:54
题目应该是有向图(至少查询应该是的)...代码这三句多余了..if (to == fa) continue;v[y].push_back(x);v[i].push_back(x);不知道说的对不对...
点赞 回复 分享
发布于 2020-04-02 01:12
https://blog.nowcoder.net/n/47b7f09a50994b5eab6b44c671ecf333
点赞 回复 分享
发布于 2020-04-01 11:57
图解有个小错误~f[5][0]=4  无伤大雅~
点赞 回复 分享
发布于 2020-03-31 22:39
https://blog.nowcoder.net/n/970115deac7942b3a451a5f12630fb7c
点赞 回复 分享
发布于 2020-03-31 20:53
https://blog.nowcoder.net/n/944cd019e6e147899a18fc971c4de162
点赞 回复 分享
发布于 2020-03-31 20:52

相关推荐

07-16 14:10
门头沟学院 Java
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
07-17 12:09
门头沟学院 Java
讲的口干舌燥,头都晕了怎么要讲这么长啊
码农索隆:没事,你口干舌燥,他不一定会看,
投递小鹏汽车等公司10个岗位
点赞 评论 收藏
分享
评论
8
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务