2020-2021:teams:hotpot:2020nowcoder9
|
2020-2021:teams:hotpot:2020nowcoder9 [2020/08/14 12:20] misakatao 创建 |
2020-2021:teams:hotpot:2020nowcoder9 [2020/08/14 13:01] (当前版本) lotk |
||
|---|---|---|---|
| 行 120: | 行 120: | ||
| ===题解=== | ===题解=== | ||
| - | ====K - ==== | + | ====K - The Flee Plan of Groundhog==== |
| - | ===solved by === | + | ===solved by lxh=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 在一棵树上，一个每秒走一条边的人，从 $1$ 点开始往 $n$ 点先走 $t$ 秒，之后第二个人开始从 $n$ 点以两条边每秒的速度开始追它，问最晚几秒被追到。 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $ 1 \le n \le 1e5 $ | ||
| + | |||
| + | ps:每秒钟开始可以认为是第一个人先走。 | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 首先，我们不难通过朴素爬树处理出第一个人的初始位置。 | ||
| + | |||
| + | 之后，我们不难发现，第一个人不想被追到，只需要到某点的时间小于第二个人，于是我们做两遍最短路统计答案即可。 | ||
| =====Replay===== | =====Replay===== | ||
2020-2021/teams/hotpot/2020nowcoder9.1597378827.txt.gz · 最后更改: 2020/08/14 12:20 由 misakatao
