【题解】牛客练习赛72

A

考虑造一张图,让每个位置 的所有倍数连有向边,那么 连了一条边的话就表示第 个杯子里的数要比第 个杯子里的数小。

然后事实上,我们只需要考虑图中最长的链就可以了,假如这条链存在合法的放数字方案,那么其他的点一定也存在合法的放数字方案,而最长的链显然是

所以只需要判断 是否比 大即可。

B

一个区间的愉悦值其实就是颜色段数。

考虑尺取法,因为颜色段数是有显然的单调性的,当 固定时, 增大,颜色段数一定不会减小。

预处理出 数组, 表示左端点为 时,右端点至少取到哪里,可以使区间内颜色段数不少于 ,每次询问 时,只需要判断 是否不小于 即可。

不过也可以用前缀和来做,实现也很简单。

C

假如将每个位置 看作平面直角坐标系上的一个点 ,那么可以发现,在操作完后,所有点会被削成一个下凸包的形状。原因比较显然,对于所有还没贴到下凸包上的点,总存在一个点是可以操作的。

那么求出所有点的下凸包,对于凸包上两个相邻的点,他们之间的点的纵坐标形成了一个等差数列,随便求一求就可以了。

最后要输出到小数点后 位是唬你的,假装要卡精度的样子qwq,事实上你发现整个求和过程中的除法只有求等差数列时的除以 ,也就是说答案的小数点后只可能是 ,判一下就好了。

然而事实上似乎没卡掉,应该输出到30位qwq

D

比较套路的推式子:先考虑拆开 ,根据定义,如果 不互质那么 一定为 ,假如互质那么又因为是积性函数,所以可以拆成 ,于是有:

,代入得:

,代入得:

于是利用 就可以做除法分块了。

注意到 的两个参数满足 ,所以只有 是有效的,预处理时间复杂度就是 ,总时间复杂度

E

标程做法

先考虑在序列上的问题,要怎么处理单次询问:令 表示以扑克 的 正面/反面 数字作为顺子的结尾,最长的顺子长度,转移比较显然,如果 ,那么 初值为 。其中 表示第 张扑克 正面/反面 上的数字。

由于保证了正反两面的数字不同,所以转移可以改一下:假如存在 ,那么 ,否则

在考虑进阶版本,如果每次询问序列上的一个区间要怎么做?

一个比较显然的技巧,假如 ,那么交换 ,然后就不需要讨论扑克翻面的情况了,问题变成了在两个序列上分别求区间最长顺子,下面就说其中一个序列的做法:令 表示以 结尾的最长顺子长度,先去掉头尾的顺子,然后中间部分求一下 就可以了,可以用 表之类的东西。

再回到树上问题,树上不是很好处理,考虑轻重链剖分,那么每条重链就是一个序列问题。询问的时候,找到 路径上要经过的所有重链,令 表示经过的上一个序列的最后一张牌上的两个数字, 表示以这个数字结尾的最长顺子,从一条重链转移到另一条重链时,只需要用到这些信息,即看一下上一条重链的末尾与当前重链的起点是否能合并,如果能,再看以 这条重链的起点 为起点的顺子最长能不能延伸到重链的末尾,如果能,那么让 直接加上重链长度即可,否则直接变成 重链末尾

然后还要算一下每条重链内的答案,那么这就是序列上每次询问一个区间内的最长顺子,用上面的做法搞就好了。

然后代码就巨长……

验题人做法

验题人日常吊打出题人。

他使用了一个实现起来更方便的做法,大部分思路是类似的,但是用了一个方便的转化:考虑序列上的一个顺子,令每个位置上的数与位置编号做差,那么做差后一段连续的相同的数就对应原来一个顺子。

放到树上,就是令 ~ 这一段的数加上深度, ~ 这一段减去深度,然后可以用倍增来更方便地维护。

F

询问有两种情况: 是祖先与子孙的关系; 无关系,即他们的子树不相交。如果是前者的关系,那么子孙其实是没用的,问题变成询问祖先子树内有多少种颜色,随便怎么样都能做。

考虑后者,答案有三个组成部分:只在 子树内出现过的颜色+只在 子树内出现过的颜色+分别在 子树内都有一部分的颜色。前两个是和上面相同的问题,只需要处理第三个部分。

考虑一种颜色 对所有询问的贡献,令 为 最深的 包含了所有颜色为 的节点 的两个节点,即颜色 只在 的子树内出现过,且 各占一部分,显然这样的两个点可能不存在,如果存在那么一定是唯一的。

表示 ,对于一个询问 ,假如 分别在 ~ ~ 路径上(不包括 ),那么颜色 就可以对 产生贡献。

对于每个颜色求出这样一对链,那么接下来要求的就是每组询问在多少对链上,这个可以用树上差分 树状数组来实现。而求这一对链,我是构造了这种颜色的虚树,然后直接看根节点是否只有恰好两个儿子。我个人觉得这样比较方便,验题人的方法是:令 表示颜色为 所有点中, 序最小和最大的两个,然后考虑从这两个点往上倍增。这部分就看个人喜欢了。

全部评论
Orz前排
点赞 回复
分享
发布于 2020-11-07 22:08

相关推荐

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