【每日一题】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/f1629afe86e445e39f26f4b58bec96f5
1 回复
分享
发布于 2020-03-30 14:58
强上线段树:https://blog.nowcoder.net/n/63a0fe8e371e40f696298a3469f3eb75
1 回复
分享
发布于 2020-03-30 23:22
淘天集团
校招火热招聘中
官网直投
https://blog.nowcoder.net/n/f430b3bea40a4a5f9172efad31b8615f
1 回复
分享
发布于 2020-05-03 23:34
https://blog.nowcoder.net/n/016181498b0f446d8f88d4a766b5c7ed
点赞 回复
分享
发布于 2020-03-30 11:15
https://blog.nowcoder.net/n/2542725e86ba4014a9fd9812e37d738a
点赞 回复
分享
发布于 2020-03-30 12:06
https://blog.nowcoder.net/n/30530d8825cd44c087f7a2ebb88461af
点赞 回复
分享
发布于 2020-03-30 13:10
https://blog.nowcoder.net/n/c2fdec8e6f7846e4ab8a3f019065f4a9
点赞 回复
分享
发布于 2020-03-30 16:55
https://blog.nowcoder.net/n/081d20e4689641afb093327ef1e74b1e
点赞 回复
分享
发布于 2020-03-30 22:44
https://blog.nowcoder.net/n/b6baecca0a36491c8d36671923477fff
点赞 回复
分享
发布于 2020-03-30 23:22
https://blog.nowcoder.net/n/c5049fb278464f65ba864f9640441635
点赞 回复
分享
发布于 2020-03-31 00:22
https://blog.nowcoder.net/n/2e6637fd050a4f778ab0a1949557e304
点赞 回复
分享
发布于 2020-03-31 09:09
https://blog.nowcoder.net/n/cc20dc7ae91d4883b7b556a816ae352b 蒟蒻的学习题解
点赞 回复
分享
发布于 2020-03-31 11:42
https://blog.nowcoder.net/n/5a39d396968041ea87cff01e54edf445  给我这种不会ST表的人看的。 文中ST表的题解,后续补上这题的题解。
点赞 回复
分享
发布于 2020-03-31 18:02
https://blog.nowcoder.net/n/944cd019e6e147899a18fc971c4de162
点赞 回复
分享
发布于 2020-03-31 20:52
https://blog.nowcoder.net/n/970115deac7942b3a451a5f12630fb7c
点赞 回复
分享
发布于 2020-03-31 20:53
图解有个小错误~f[5][0]=4  无伤大雅~
点赞 回复
分享
发布于 2020-03-31 22:39
https://blog.nowcoder.net/n/47b7f09a50994b5eab6b44c671ecf333
点赞 回复
分享
发布于 2020-04-01 11:57
题目应该是有向图(至少查询应该是的)...代码这三句多余了..if (to == fa) continue;v[y].push_back(x);v[i].push_back(x);不知道说的对不对...
点赞 回复
分享
发布于 2020-04-02 01:12
https://blog.nowcoder.net/n/4baef88638d745ad8b04faaa4c5f5f61
点赞 回复
分享
发布于 2020-04-02 15:54
https://blog.nowcoder.net/n/50ab8a44f339434b873a19cc49b2f41b
点赞 回复
分享
发布于 2020-04-02 17:48

相关推荐

8 收藏 评论
分享
牛客网
牛客企业服务