2020-2021:teams:i_dont_know_png:saratovsu2015

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:saratovsu2015 [2020/07/28 17:45]
qxforever [解题思路]
+++ 2020-2021:teams:i_dont_know_png:saratovsu2015 [2020/08/15 18:09] (当前版本)
nikkukun add G
@@ 行 3: / 行 3: @@
 [[https://codeforces.com/group/azDPdoF24f/contest/288496 | 比赛链接]]
-===== A  - Three Servers  =====
+===== A - Three Servers =====
 Solved by qxforever.
@@ 行 16: / 行 16: @@
 在实现中，考虑空间限制，取 $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$ 路径旁边延伸出的最长边长度”，需要画图进行仔细分类讨论。
+由于是枚举一端，每次操作完后要重新初始化。没初始化导致赛后过题。

2020-2021/teams/i_dont_know_png/saratovsu2015.1595929523.txt.gz · 最后更改: 2020/07/28 17:45 由 qxforever