====== 2015-2016 Petrozavodsk Winter Training Camp, Saratov SU Contest ====== [[https://codeforces.com/group/azDPdoF24f/contest/288496 | 比赛链接]] ===== A - Three Servers ===== 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$ 次取最优通过了本题。 ===== F - Empty Vessels ===== Solved by Potassium. ==== 题目描述 ==== 有 $n$ 个容积分别为 $a_1,a_2,...,a_n$ 的水桶,通过以下三种操作获取恰好 $A$ 容量的水,求方案。 - 装满某个水桶; - 清空某个水桶; - 把一个水桶 $i$ 的水倒到另一个 $j$ 里,直到 $j$ 水桶满了或 $i$ 水桶空了。 ==== 解题思路 ==== 注意到所有三操作都可以让 $j$ 变为容积最大的水桶进行多次操作,故实质上是模意义下的完全背包。对余数 BFS 一下就可以了。 ===== G. Maximum Product ===== Solved by nikkukun. 水题不表。 ===== H - Biathlon 2.0 ===== 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)$ 的最小值,向量点积即为投影相乘,故维护一个凸包,在上面二分一下或者极角排完序指针维护即可。 ===== K - Toll Roads ===== Upsolved by Potassium. ==== 题目描述 ==== 给定一棵边权 $1$ 的树,将其中一条长度不超过 $k$ 的简单路全变成边权 $0$,使得最长简单路径变短幅度最大,如果相同幅度,修改边个数越少越好,求方案。$1\le k,n\le 5000$。 ==== 解题思路 ==== 枚举一端,以它作为根节点进行树形 DP。DP 过程中需要统计出子树 $p$ 到根节点的链全变为 $0$ 后最长链的长度,故对于每个节点 $p$ 需要维护“离叶子的最远距离”和“$1-p$ 路径旁边延伸出的最长边长度”,需要画图进行仔细分类讨论。 由于是枚举一端,每次操作完后要重新初始化。没初始化导致赛后过题。