牛客练习赛 66 题解

前几天在考试，稍微发晚了点，请见谅。

A

我们可以求出最大的整数 满足 ，然后分别判断 和 即可。

只有一次询问，且数据范围只有 ，暴力枚举或二分皆可。

时间复杂度 或 。

代码链接

B

考虑从 开始 BFS，则第一层扩展到的点 一定满足 ；第二层扩展到的点 一定满足 ，可以得到 ；第三层的点 一定满足 ，而这些点一定在第一层已经被扩展到，所以第三层不存在点。

综上，我们可以发现只有三种情况：

1. ，最短路为 。
2. 且存在 满足 ，则最短路为 。
3. 其他情况一定不连通。

直接用桶记录所有出现过的权值即可判断第二种情况。

时间复杂度 。

代码链接

关于此题的 IO：被卡常确实是出题人想得不够周到，本意并不想卡常。不过有一说一牛客评测机波动确实大……

C

由于 有性质 ，所以我们可以将 数组进行差分得到数组 ，特别地，。那么有 。

对 数组整体加 会使得 加 而其他数不变。

令 ，则我们要求最大的 以及在 最大时最小的 。

只要让 整除 即可。

时间复杂度 （对一个数组整体求 是 的）。

代码链接

D

转化后题目即为求使得所有 为质数幂次的最小的 。相当于每个数都只能有最多一个质因子的幂次大于 中对应质因子的幂次。

考虑依次加入每个质因子，用 表示只考虑已加入的质因子时， 集合中的数已经有一个质因子幂次大于 中对应质因子的幂次时最小的 。

转移考虑枚举当前质因子的次数进行转移，直接判断每个数是否会被覆盖即可。

时间复杂度 ，其中 表示不同质因子的次数之和， 表示高精度的复杂度。

代码链接

E

我们可以使用二分加 ST 表求出每个位置左边第一个比他大的和第二个比他大的，以及右边第一个比他小的和第二个比他小的，分别记为 。

考虑一个区间 是 Sao 的需要满足的条件有：

考虑将第一个条件差分，即满足 和条件 2 的方案数，减去满足 和条件 2 的方案数。

那么我们只要从前往后枚举 ，就可以去掉第一个条件，第二个条件只需要用树状数组进行区间加操作即可。

当然也有其他很多方法，这里介绍的只是其中一种。

时间复杂度 ，常数较大。

代码链接

F

建出序列的一棵笛卡尔树，对于相同的数我们强制标号小的更小。我们可以通过预处理卡特兰数来求出笛卡尔树上每个子树的答案。

现在我们只需要求出 到区间中最小值第一次出现的位置的方案数、区间中最小值最后一次出现的位置到 的方案数，以及中间部分的方案数、最小值出现的次数即可。

中间部分的方案数和最小值的出现次数可以通过树上差分很简单的求出，而区间中最小值最后一次出现的位置到 的方案数可以将序列翻转转化成 到区间中最小值第一次出现的位置的方案数。

现在只需要求出 到区间中最小值第一次出现的位置的方案数即可。

考虑一个暴力做法，我们将 的右子树加入答案，然后从 不断往上跳直到父亲为 的 LCA，若当前 是左子树，则将右子树加入答案。

这个跳的过程可以简单地使用倍增预处理。

时间复杂度 ，常数较大，细节其实不是很多。

代码链接