2020-2021:teams:hotpot:2020nowcoder4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder4 [2020/07/24 12:52] misakatao 更新 |
2020-2021:teams:hotpot:2020nowcoder4 [2020/07/24 15:09] (当前版本) lotk |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| =====题解===== | =====题解===== | ||
| - | ====A - ==== | + | ====A - Ancient Distance==== |
| - | ===solved by === | + | ===solved by lxh=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 我们定义远古距离为其到其最近的有标记的祖先的距离（自己有标记则为0）。现在依次给 $1~n$ 个点，问在树上有这么多标记了的点时，最大的远古距离最小是多少。 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | 点数 $n \le 2e5 $ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 正面想这个问题不太好解决，我们不妨反过来想，由于答案的单调性让问题变为当最大远古距离为 $k$ 时，最少需要多少个点，这样我们就可以通过在最深的点处向上爬 $k$ 层再将整个子树去掉的方法贪心（需要借助线段树和dfn序维护），最后从 $1~n$ 扫一遍处理出每个的答案。 | ||
| ====B - ==== | ====B - ==== | ||
| 行 113: | 行 119: | ||
| =====Replay===== | =====Replay===== | ||
| - | 第一小时： | + | 第一小时：三人发现F很简单，于是tyx直接过了F，gyp开始想B并快速通过，之后开始想H，tyx和lxh开始想E，gyp的H不通过 |
| - | 第二小时： | + | 第二小时：gyp发现了H题的问题通过了H，lxh开始写E，gyp开始想D |
| - | 第三小时： | + | 第三小时：lxh的E没通过，gyp开始写E但是也没有通过，tyx看了CDJ以后开始想J |
| - | 第四小时： | + | 第四小时：gyp写完D以后一直WA，找到了几个错误以后还是不对，tyx想不出J和lxh一起想A |
| - | 第五小时： | + | 第五小时：tyx和lxh一起想出了A并且通过，gyp一直在改D但是始终没有通过 |
| =====总结===== | =====总结===== | ||
| - | * | + | * 在提交之前一定要注意题目的条件，否则就会罚时++ |
2020-2021/teams/hotpot/2020nowcoder4.1595566348.txt.gz · 最后更改: 2020/07/24 12:52 由 misakatao
