牛客挑战赛 72 题解

A

直接枚举 判断即可。

B

由于被排除前 的人再也不可能进入，可以直接暴力维护当前前 大的分数。也可以采取维护有序表的数据结构，当元素个数超过 时就弹出最低的分数。

另外需要考虑存储的精度，由于保证了小数位数，可以读取字符串转为整数或者对字符串手写比较大小解决。

C

考虑树形 DP， 表示 子树内的点在路径中构成 个连通块，合并子树时需要考虑连接一些连通块。

注意到我们只关心能连接出的连通块的最小和最大的个数，这是容易构造的。暴力枚举连接出的连通块个数即可。

时间复杂度 。

D

脑筋急转弯题。首先特判答案 的情况，从而 中在区间 中没出现的恰为 和 两段。

运用可持久化线段树即可维护。时间复杂度 。

E

显然对于化简结果 ，我们要求 除了 以外没有其他的约数是完全平方数，即 。

我们直接枚举 ，有

接下来，容易证明 只有 种取值。按 分类讨论即可。

考虑如何求 的前缀和，有经典结论

先不考虑 的前缀和如何求解。设阈值 ，对 ，我们线性筛预处理；对 ，用 的整除分块计算。通过一个积分我们可以说明后者的总复杂度：

可以平衡到 。

然后考虑我们所需的 前缀和，是所有的 位置。

设阈值 ， 的部分用线性筛， 的部分用杜教筛。通过一个积分我们可以说明后者的总复杂度：

也可以平衡到 。

事实上， 的做法在卡常后也可以通过。

F

称一个满足 且 的位置 是一个极大值。

考虑暴力 DP，设 是具有 个极大值且分别有：

• ；
• ；
• ；
• 

的排列个数。

进一步注意到 。因此我们只需要维护 。

经过讨论可以得到递推式

注意到形式类似，设 ，再讨论初值，可得

考虑作下标变换，设 ，则

考虑使用 GF，设 ，则有

类似一阶线性微分方程的解法，我们考虑合并右侧的两项。 令 ，容易验证

做基变换换元，设 ，其中 ，有

根据 Taylor 公式，我们知道

记作 。以下令 ，则我们要求

其中第二个等号使用了另类 Lagrange 反演。

考虑先求

于是复杂度为 。