2020-2021:teams:i_dont_know_png:multi2020-nowcoder-9
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-9 [2020/08/08 23:36] nikkukun add CDK |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-9 [2020/08/10 22:44] (当前版本) qxforever |
||
|---|---|---|---|
| 行 6: | 行 6: | ||
| - | ===== A - ===== | + | ===== A - Groundhog and 2-Power Representation ===== |
| Solved by . | Solved by . | ||
| 行 14: | 行 14: | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== B - Groundhog and Apple Tree ===== | ||
| + | |||
| + | 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)$ | ||
| 行 36: | 行 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} | ||
| 行 56: | 行 80: | ||
| - | ===== D - Groundhog Chasing Death ===== | + | ===== E - Groundhog Chasing Death ===== |
| Solved by nikkukun. | Solved by nikkukun. | ||
| 行 85: | 行 109: | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== F - Groundhog Looking Dowdy ===== | ||
| + | |||
| + | Solved by qxforever. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | $n$ 天，每天有 $k_i$ 件衣服穿，每种衣服有不同的邋遢值。问 $n$ 天邋遢值的差最小是多少。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 将所有衣服按邋遢值排序，从前往后枚举衣服，双指针保证区间内有不同的 $n$ 天的衣服，取个 $\min$ 即可。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== I - The Crime-solving Plan of Groundhog ===== | ||
| + | |||
| + | Solved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给 $n$ 个数，分成两个部分，每部分没有前导零且是正数，最小化这两个数的乘积并输出。$\sum n \leq 10^6$，所有数都是 $[0, 9]$。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 猜测答案是一位数与剩余能组成的最小的数的乘积，枚举一位数是什么即可。实际上一位数只能是最小的数，可以不枚举。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ===== J - The Escape Plan of Groundhog ===== | ||
| + | |||
| + | Solved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一个 $n \times m$ 的 $01$ 矩阵 $a_{n \times m}$，统计满足条件的子矩阵： | ||
| + | |||
| + | - 子矩阵的四边都是 $1$ | ||
| + | - 除了四边之外，子矩阵的 $0$ 和 $1$ 数量差不超过 $1$ | ||
| + | - 子矩阵长和宽不小于 $1$ | ||
| + | |||
| + | $n, m \leq 500$。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 一般这种题都是枚举一维的上下两个边界，剩下一维做前缀和处理。对于剩下这维，实际是对依次考虑每个满足全 $1$ 的左边界，寻找有多少全 $1$ 的右边界满足 $[a_{ij} = 1] - [a_{ij} = 0]$ 的前缀和与它的前缀和差不超过 $1$，这里用类似双指针的方法移动就可以维护相关信息。 | ||
| + | |||
| + | 总时间复杂度 $O(n^3)$。 | ||
| 行 112: | 行 198: | ||
| - 做题之前一定要先按题意把样例算一下，避免读错题或者是写错算法的情况发生； | - 做题之前一定要先按题意把样例算一下，避免读错题或者是写错算法的情况发生； | ||
| - 如果某个算法渐进意义明显超时了，那就不要加优化多次提交了，考虑能不能把复杂度降低一个等级； | - 如果某个算法渐进意义明显超时了，那就不要加优化多次提交了，考虑能不能把复杂度降低一个等级； | ||
| - | - 数量级很大的时候，不要用 ''map<int, vector<int>>''，会卡爆。 | + | - 数量级很大的时候，不要用 ''map<int, vector<int> >''，会卡爆。 |
| ==== qxforever ==== | ==== qxforever ==== | ||
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-9.1596900987.txt.gz · 最后更改: 2020/08/08 23:36 由 nikkukun
