【题解】牛客练习赛72
A
考虑造一张图,让每个位置 向
的所有倍数连有向边,那么
向
连了一条边的话就表示第
个杯子里的数要比第
个杯子里的数小。
然后事实上,我们只需要考虑图中最长的链就可以了,假如这条链存在合法的放数字方案,那么其他的点一定也存在合法的放数字方案,而最长的链显然是 。
所以只需要判断 是否比
大即可。
B
一个区间的愉悦值其实就是颜色段数。
考虑尺取法,因为颜色段数是有显然的单调性的,当 固定时,
增大,颜色段数一定不会减小。
预处理出 数组,
表示左端点为
时,右端点至少取到哪里,可以使区间内颜色段数不少于
,每次询问
时,只需要判断
是否不小于
即可。
不过也可以用前缀和来做,实现也很简单。
C
假如将每个位置 看作平面直角坐标系上的一个点
,那么可以发现,在操作完后,所有点会被削成一个下凸包的形状。原因比较显然,对于所有还没贴到下凸包上的点,总存在一个点是可以操作的。
那么求出所有点的下凸包,对于凸包上两个相邻的点,他们之间的点的纵坐标形成了一个等差数列,随便求一求就可以了。
最后要输出到小数点后 位是唬你的,假装要卡精度的样子qwq,事实上你发现整个求和过程中的除法只有求等差数列时的除以
,也就是说答案的小数点后只可能是
或
,判一下就好了。
然而事实上似乎没卡掉,应该输出到30位qwq
D
比较套路的推式子:先考虑拆开 ,根据定义,如果
不互质那么
一定为
,假如互质那么又因为是积性函数,所以可以拆成
,于是有:
令 ,代入得:
令 ,代入得:
于是利用 就可以做除法分块了。
注意到 的两个参数满足
,所以只有
个
是有效的,预处理时间复杂度就是
,总时间复杂度
。
E
标程做法
先考虑在序列上的问题,要怎么处理单次询问:令 表示以扑克
的 正面/反面 数字作为顺子的结尾,最长的顺子长度,转移比较显然,如果
,那么
,
初值为
。其中
表示第
张扑克 正面/反面 上的数字。
由于保证了正反两面的数字不同,所以转移可以改一下:假如存在 ,那么
,否则
。
在考虑进阶版本,如果每次询问序列上的一个区间要怎么做?
一个比较显然的技巧,假如 或
,那么交换
,然后就不需要讨论扑克翻面的情况了,问题变成了在两个序列上分别求区间最长顺子,下面就说其中一个序列的做法:令
表示以
结尾的最长顺子长度,先去掉头尾的顺子,然后中间部分求一下
就可以了,可以用
表之类的东西。
再回到树上问题,树上不是很好处理,考虑轻重链剖分,那么每条重链就是一个序列问题。询问的时候,找到 到
路径上要经过的所有重链,令
表示经过的上一个序列的最后一张牌上的两个数字,
表示以这个数字结尾的最长顺子,从一条重链转移到另一条重链时,只需要用到这些信息,即看一下上一条重链的末尾与当前重链的起点是否能合并,如果能,再看以 这条重链的起点 为起点的顺子最长能不能延伸到重链的末尾,如果能,那么让
直接加上重链长度即可,否则直接变成
重链末尾
。
然后还要算一下每条重链内的答案,那么这就是序列上每次询问一个区间内的最长顺子,用上面的做法搞就好了。
然后代码就巨长……
验题人做法
验题人日常吊打出题人。
他使用了一个实现起来更方便的做法,大部分思路是类似的,但是用了一个方便的转化:考虑序列上的一个顺子,令每个位置上的数与位置编号做差,那么做差后一段连续的相同的数就对应原来一个顺子。
放到树上,就是令 ~
这一段的数加上深度,
~
这一段减去深度,然后可以用倍增来更方便地维护。
F
询问有两种情况: 是祖先与子孙的关系;
无关系,即他们的子树不相交。如果是前者的关系,那么子孙其实是没用的,问题变成询问祖先子树内有多少种颜色,随便怎么样都能做。
考虑后者,答案有三个组成部分:只在 子树内出现过的颜色+只在
子树内出现过的颜色+分别在
子树内都有一部分的颜色。前两个是和上面相同的问题,只需要处理第三个部分。
考虑一种颜色 对所有询问的贡献,令
为 最深的 包含了所有颜色为
的节点 的两个节点,即颜色
只在
的子树内出现过,且
各占一部分,显然这样的两个点可能不存在,如果存在那么一定是唯一的。
令 表示
的
,对于一个询问
,假如
分别在
~
,
~
路径上(不包括
),那么颜色
就可以对
产生贡献。
对于每个颜色求出这样一对链,那么接下来要求的就是每组询问在多少对链上,这个可以用树上差分 树状数组来实现。而求这一对链,我是构造了这种颜色的虚树,然后直接看根节点是否只有恰好两个儿子。我个人觉得这样比较方便,验题人的方法是:令
表示颜色为
所有点中,
序最小和最大的两个,然后考虑从这两个点往上倍增。这部分就看个人喜欢了。