2020-2021:teams:legal_string:组队训练比赛记录:contest1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest1 [2020/05/15 20:27] lgwza |
2020-2021:teams:legal_string:组队训练比赛记录:contest1 [2021/07/11 10:01] (当前版本) jxm2001 ↷ 页面2020-2021:teams:legal_string:contest1被移动至2020-2021:teams:legal_string:组队训练比赛记录:contest1 |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| ===== B. Bonuses on a Line ===== | ===== B. Bonuses on a Line ===== | ||
| - | ===题意===：数轴上有 $n$ 份奖金，每份奖金的坐标为 $x_i$ ，总共有 $t$ 秒的时间，每秒可走 $1$ 的距离。初始在原点 $0$ 位置，问最多能获得多少份奖金？ | + | === 题意 === |
| - | ===题解===：先向某一方向跑，然后再折返跑向另一方向。例如先向负方向跑，在每份奖金处，利用二分查找，找到能够折返跑到正方向的奖金的最大份数即可。 | + | 数轴上有 $n$ 份奖金，每份奖金的坐标为 $x_i$ ，总共有 $t$ 秒的时间，每秒可走 $1$ 的距离。初始在原点 $0$ 位置，问最多能获得多少份奖金？ |
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 先向某一方向跑，然后再折返跑向另一方向。例如先向负方向跑，在每份奖金处，利用二分查找，找到能够折返跑到正方向的奖金的最大份数即可。 | ||
| 时间复杂度 $O\left(n\log n\right)$ | 时间复杂度 $O\left(n\log n\right)$ | ||
| 行 69: | 行 73: | ||
| ===题意=== | ===题意=== | ||
| - | 在直角坐标系中给定$n$整点$\left(-10^8\le x_i,y_i\le 10^8\right)$，可以得到$\frac{n\times \left(n-1\right)}{2}$个点对，将所有点对的哈密顿距离排序，要求输出第k大的哈密顿距离$\left(2\le n\le 100000,1\le k\le \frac{n\times \left(n+1\right)}{2}\right)$ | + | 在直角坐标系中给定$n$整点$\left(-10^8\le x_i,y_i\le 10^8\right)$，可以得到$\frac{n\times \left(n-1\right)}{2}$个点对，将所有点对的哈密顿距离排序，要求输出第k大的哈密顿距离$\left(2\le n\le 100000,1\le k\le \frac{n\times \left(n-1\right)}{2}\right)$ |
| ===题解=== | ===题解=== | ||
| 行 179: | 行 183: | ||
| ===== E. Fluctuations of Mana ===== | ===== E. Fluctuations of Mana ===== | ||
| + | 签到题 | ||
| ===== F. Moving Target ===== | ===== F. Moving Target ===== | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest1.1589545663.txt.gz · 最后更改: 2020/05/15 20:27 由 lgwza
