洛谷7月月赛题解

## A.Divided Prime 由于保证了任何一个数字在 $b$ 中的出现次数不大于在 $a$ 中的出现次数。 那么对于每个 $b$ 中的数字，我们只需要将其在 $a$ 中删去即可。 然后考虑如何判断 $a$ 剩下的数字是否为质数。 我们只需要检查每个数字由几个质数组成即可。 在判断质数时，发现当前已经有两个或以上的质数了需要马上退出，否则有可能会造成TLE。 值得一提的是，由 $0$ 个质数组成的数字（即 $1$ ）也不是质数。 复杂度 $O(n\ log\ n + \sqrt a_i )$ ## B. River Jumping 首先我们考虑最靠近开头和最靠近结尾的两块岩石，如果他们离开头/结尾的距离小于 $S$，那么这块岩石将不可能被跳到，从而导致无解。 对于三个连续的岩石 $i,i+1,i+2$，如果$w_{i+2}-w_i<S$ ，由于我们只能来回一次，且每次跳到其中的一个石头上时必然不可能跳到另一个石头上，所以这种情况也会导致无解。 那么有解时我们只需要贪心地能跳就选择一个距离不小于 $S$ 的且最近的跳就可以了。 时间复杂度 $O(N)$ ## C. True Vegetable 如果一边被减一边填补，因为情况较多，决策难以判断。 如果直接二分时间，因为某个位置的难度可能一时被减去较多，不满足二分性质。 令被减去的时间为时间点，考虑二分被减的时间点，然后将难度先减去要减的值，因为减难度的冷却时间不小于需要加的数量，被减的数量可以用相同数量的时间填补，所以当一个时间点可以达到目标时，下一个时间点必然也能达到目标。 然后在时间点上计算出需要的时间。二分时间点，在减去所有生效的操作后，我们可以贪心地从左到右地考虑，当位置 $i$ 小于 $1$ 时，考虑贪心地将 $[i,i+K-1]$ 这个区间加 $1$，可以使需要的回合数尽量小。当确定小B有哪些操作生效时，这样就可以求出满足条件的准确最小时间，若这个时间小于下个时间点，那么check()就是有效的。 时间复杂度 $O(N\ log\ N)$ ## D. Beautiful Pair 我们考虑用分治的思想来解决这个问题。假设我们在计算区间$[l,r]$数对的数量，其中这个区间的最左端的最大值的位置为$mx$，那么我们可以先考虑处理$[l,mx-1]$区间数对的数量和$[mx+1,r]$区间数对的数量。 对于一个区间$[l,r]$，当我们确定了$a_l$时，只需要求$[mx+1,r]$中数字不大于$\frac {a_{mx}}{a_l}$的即是以$l$为左端点答案的对数（因为我们分区间是以最左端的最大值区分的），当确定了$a_r$时同理。此时我们可以枚举小的区间，然后确定另一边要查询的区间以及查询的值，记录下后离线查询。 可以证明，所有查询的区间数量不超过$n\ log\ n$个。考虑当进行一次长度为$len$的枚举时，那么此时被分开的区间长度必然大于$2\times len$，那么对于任意一个数字，它被枚举的次数必然不超过$log\ n$，每被枚举一次会形成一个询问区间，所以询问区间不超过$n\ log\ n$个。 考虑如果选定一个端点，那么可行的右端点的数量可以用树状数组查询。（查询 $[l,r]$ 中小于 $x$ 的数字数量可以用 $[1,r]$ 中小于 $x$ 的数字数量减去 $[1,l-1]$ 中小于 $x$ 的数字数量） 询问一个区间$[l,r]$小于等于$x$的数字数量可以用树状数组解决，用$[1,r]$中的小于等于$x$的数字数量减去$[1,l-1]$中的小于等于$x$的数字数量即为答案。 ## E. Added Sequence 考虑最大的$f(i,j)=| \sum_{p=i}^j a_p |$本质是什么 换为前缀和的形式 $f(i,j)=|pre_j - pre_i|$ 将绝对值拆掉 $$f(i,j)=\left\{\begin{matrix} pre_j-pre_i & if\ pre_{j}>pre_{i}\\ pre_i-pre_j & if\ pre_{j} \le pre_{i} \end{matrix}\right.$$ 所以$\max_{1 \le i \le j \le n} f(i,j)$ $=\max pre_i - \min pre_j$ 如果给整个数组加上 $x$，那么 $pre'_i=pre_i+ix$ 那么当我们确定了整个数组加上的数字$x$，我们就能确定每个位置的前缀和，考虑如何求出最大的前缀和和最小的前缀和。 这个是个一次函数的形式，我们可以将前面的 $n+1$ 个一次函数加入坐标系，维护一个下凸包表示整个数组加上$x$时最大的前缀和，维护一个上凸包表示最小的前缀和。 这个是样例的图，其中紫色的为5条一次函数，黄色的为下凸包，红色的为下凸包。那么当我们要求整个数组加上$h$的答案时，$x$坐标为$h$的下凸包的$y$坐标减去$x$坐标为$h$的上凸包的$y$坐标得到的差即为询问的答案。  那么我们维护凸包，记下凸包上每条线段两端的位置后，我们可以二分横坐标$h$是在哪个线段上，求出相应的$y$值。 最后上凸包的值-下凸包的值即为答案。 时间复杂度为$O(n\ log\ n)$