比赛链接

Solved by qxforever.

给 $n$ 个数，分为三组，使三组和的 max-min 最小。$n\le 400$ ，$a_i \le 30$

考虑 dp，设 $f_{i,j,k}$ 表示前 $i$ 个数，第二组减第一组为 $j$ ，第三组减第一组为 $k$ 是否可行。设两组差的范围为 $m$ ，那么时间和空间复杂度均为 $O(n\times m^2)$ 。猜想在 random_shuffle 下，$m$ 的范围不必很大也能找到最优解。

在实现中，考虑空间限制，取 $m=750$ ，单次计算耗时 ~ 300ms 。考虑时间限制，随机 $8$ 次取最优通过了本题。

Solved by Potassium.

有 $n$ 个容积分别为 $a_1,a_2,\ldots,a_n$ 的水桶，通过以下三种操作获取恰好 $A$ 容量的水，求方案。

1. 装满某个水桶；
2. 清空某个水桶；
3. 把一个水桶 $i$ 的水倒到另一个 $j$ 里，直到 $j$ 水桶满了或 $i$ 水桶空了。

注意到所有三操作都可以让 $j$ 变为容积最大的水桶进行多次操作，故实质上是模意义下的完全背包。对余数 BFS 一下就可以了。

Solved by nikkukun.

水题不表。

Solved by nikkukun & Potassium.

给 $5 \times 10^5$ 个数对 $(x,y)$ ，和 $5 \times 10^5$ 个数对 $(a,b)$ 。 对于每个 $(a,b)$ 找出 $ax+by$ 最小值。

把 $(x,y)$ 抽象成一堆点，对于每个 $(a,b)$ 即是寻找 $(a,b)\cdot (x,y)$ 的最小值，向量点积即为投影相乘，故维护一个凸包，在上面二分一下或者极角排完序指针维护即可。

Upsolved by Potassium.

给定一棵边权 $1$ 的树，将其中一条长度不超过 $k$ 的简单路全变成边权 $0$，使得最长简单路径变短幅度最大，如果相同幅度，修改边个数越少越好，求方案。$1\le k,n\le 5000$。

枚举一端，以它作为根节点进行树形 DP。DP 过程中需要统计出子树 $p$ 到根节点的链全变为 $0$ 后最长链的长度，故对于每个节点 $p$ 需要维护“离叶子的最远距离”和“$1-p$ 路径旁边延伸出的最长边长度”，需要画图进行仔细分类讨论。

由于是枚举一端，每次操作完后要重新初始化。没初始化导致赛后过题。