【题解】牛客挑战赛43

A

容易证明 $x + y \ge x\ \mathrm{or}\ y$ ，所以一定每个数单独一段最优。

输出所有数的和即可。

B

可以发现删数一定是从小往大删的。

设最后一个被删的数是 $x$ ，则需要满足剩下的小于 $x$ 的数不超过 $m$ 个。

枚举剩下的集合还剩 $k$ 个元素，则需要将 $n - k$ 个删除的元素插入到留下的第 $m + 1$ 个元素之前。那么能插的空位一共有 $\min(m + 1, k + 1)$ 个。使用组合数计算答案即可。

C

把式子看做平面上有 $n^2$ 个点 $(A_i, A_j)$ ，需要找一个点使得到其它点的切比雪夫距离之和最小。

我们使用将切比雪夫距离转成曼哈顿距离的方法，将每个点 $(A_i, A_j)$ 变成 $(A_i + A_j, A_i - A_j)$ ，然后两点间的切比雪夫距离就变成了两点间的曼哈顿距离的一半。这样两维就可以独立考虑，将答案相加。接下来以第一维为例。

我们要数轴上找一个点，满足其到 $n^2$ 个点距离之和最小。容易证明可以选择从小到大第 $\lfloor \frac{n^2}{2} \rfloor + 1$ 个数。我们二分一下这个数的大小，然后 two pointers 扫一下求出小于这个值的数的个数。这样就能确定第 $\lfloor \frac{n^2}{2} \rfloor + 1$ 个数。

求出了这个数后，我们同样可以使用 two pointers 求出所有点到这个点的距离和。这样就解决了一维的问题。

对两位都用以上方法做一遍，就可以在 $O(n \log v)$ 的复杂度内解决此题。

D

我们对于数组 $A$ 的一位 $A_i$ ，写出它的 egf。

假设涉及到 $A_i$ 的操作总共有 $X$ 个，其中有 $Y$ 个是将其赋值为 $0$ 的。则最后一次操作的方案有 $Y$ 种，而最后一次操作之前的每次操作的方案有 $X$ 种。

那么生成函数就是 $Y \times \sum_{i=1}^n \frac{X^{i-1}x^i}{i!} = Y \times \frac{e^{Xx} - 1}{X}$ 。如果初始 $A_i = 0$ ，还要再加上 $1$ 。

我们将每一位的生成函数分治乘起来，并且以 $\sum_{i} V_i e^{ix}$ 的形式维护多项式。容易发现这样的形式的乘法和普通多项式的乘法的规则一样。而由于 $\sum X = m$ ，最终得到的多项式是 $m + 1$ 项的。

最后统计答案，对于每一项 $V_i e^{ix}$ ，我们求出 $x^k$ 项的系数乘上 $k!$ ，即 $V_i \times i^k$ ，再将这些系数相加即可。

这样就在 $O(m \log^2 m)$ 的复杂度内解决了此题。

E

当一个小球沿着一条线段走完之后，其后的路线仅与这一条线段有关，而可以忽略小球原先的信息。这启发我们建立线段与线段之间的转移关系：当一个球从这条线段的下端点出发，我们想知道是否会遇到下一条线段，下一条线段是哪条，以及是否会在下一条线段上停止。如果不会停止，视为两条线段间的一条有向边。这个关系形成了一个森林的结构。

问题转化为给定一些坐标，问从这些坐标出发的每个小球是否会遇到一条线段，是哪条，以及是否会在下一条线段上停止。容易发现每个询问小球遇到第一条线段前的情况也是这个问题的模式，可以一起进行处理。

将问题分为两部分，第一步求遇到的线段可以将两种斜率的线段分别计算，转换坐标把线段变成水平的，离线扫描线即可。第二步求是否会在线段上停止，旋转平面把线段变成竖直和水平的，同样也是离线扫描线。总复杂度 $O((n+m)\log (n+m))$ 。