2020-2021:teams:i_dont_know_png:multi2020-nowcoder-9
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-9 [2020/08/08 23:48] nikkukun add CEIJK. |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-9 [2020/08/10 22:44] (当前版本) qxforever |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| ===== B - Groundhog and Apple Tree ===== | ===== B - Groundhog and Apple Tree ===== | ||
| - | Solved by . | + | Solved by qxforever. |
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| + | |||
| + | 给一棵 $n$ 个点的树，第一次经过一个点可以回复 $a_i$ 点血量，经过一条边消耗 $w_i$ 点血量，休息一次恢复 $1$ 点血量。初始在 1 号点，hp 为 0。问按某种 dfs 序访问所有点再回到 1 号点最少需要休息几次。 $\sum n \le 10^6$ | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | |||
| + | 考虑 dp，设 $f_i$ 为在 $i$ 号点 hp 为 $0$ 时遍历 $i$ 的子树需要的休息次数，$g_i$ 为 $i$ 的子树的 点权 $-$ 边权。休息次数可以转化为访问过程中 hp 最小值的相反数。 | ||
| + | |||
| + | 对于儿子 $j$ ，将最多花费 $f_j+w+\max(w-f_j-g_j,0)$ 点 hp，回复 $g_j-2w$ 点 hp ，记为 $(u_j,v_j)$，问题在于如何决策访问儿子的顺序。将儿子分为访问过后 hp 增加的和不增加的两组。 | ||
| + | |||
| + | 首先访问 $v\ge 0$ 的儿子，我们按照 $u$ 递增的顺序访问，维护 hp 的最小值。因为每次访问后 hp 都会增加，因此这样的顺序是最优的。 | ||
| + | |||
| + | 对于 $v< 0$ ，我们需要按照 $u+v$ 递减的顺序访问。简单证明如下：设两点 $(u_1,v_1)$，$(u_2,v_2)$，当前 hp 为 $c$ 。若在不休息的情况下只能先访问 1 后访问 2，有 $u_2\le c+v_1$，$u_1 > c+v_2$，即 $u_2+v_2\le c < u_1+v_1$ 。一个例子是 hp 为 $6$ ，两对为 $(5,-3),(4,-1)$。 | ||
| + | |||
| + | 时间复杂度 $O(n\log n)$ | ||
| 行 48: | 行 60: | ||
| \begin{aligned} | \begin{aligned} | ||
| E \left[ \left( \sum_{i=1}^m s_i p_i \right)^2 \right] | E \left[ \left( \sum_{i=1}^m s_i p_i \right)^2 \right] | ||
| - | &= E \left[ \sum_{i=1}^m ( s_i p_i)^2 + 2\sum_{i \neq j} s_i p_i \cdot s_j p_j \right] \\ | + | &= E \left[ \sum_{i=1}^m ( s_i p_i)^2 + \sum_{i \neq j} s_i p_i \cdot s_j p_j \right] \\ |
| &= \sum_{i=1}^m E \left(s_i^2 \cdot p_i \right) + \sum_{i \neq j} E \left( s_i s_j \cdot p_i p_j \right) | &= \sum_{i=1}^m E \left(s_i^2 \cdot p_i \right) + \sum_{i \neq j} E \left( s_i s_j \cdot p_i p_j \right) | ||
| \end{aligned} | \end{aligned} | ||
| 行 107: | 行 119: | ||
| ===== F - Groundhog Looking Dowdy ===== | ===== F - Groundhog Looking Dowdy ===== | ||
| - | Solved by . | + | Solved by qxforever. |
| ==== 题目描述 ==== | ==== 题目描述 ==== | ||
| + | |||
| + | $n$ 天，每天有 $k_i$ 件衣服穿，每种衣服有不同的邋遢值。问 $n$ 天邋遢值的差最小是多少。 | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | |||
| + | 将所有衣服按邋遢值排序，从前往后枚举衣服，双指针保证区间内有不同的 $n$ 天的衣服，取个 $\min$ 即可。 | ||
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-9.1596901711.txt.gz · 最后更改: 2020/08/08 23:48 由 nikkukun
