2020-2021:teams:hotpot:200829-200904
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200829-200904 [2020/09/04 12:50] 喝西北风 |
2020-2021:teams:hotpot:200829-200904 [2020/09/04 14:47] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 12: | 行 12: | ||
| =====比赛===== | =====比赛===== | ||
| + | |||
| + | 2020.8.30 [[codeforces666div1|Codeforces Round #666]] ''prob:2/2/5'' ''rank:778'' | ||
| =====题目===== | =====题目===== | ||
| - | 无 | + | 本周无 |
| ======陶吟翔====== | ======陶吟翔====== | ||
| 行 26: | 行 28: | ||
| 2020.8.29 [[abc177|Atcoder Beginner Contest 177]] ''prob:5/6/6'' ''rank:638'' | 2020.8.29 [[abc177|Atcoder Beginner Contest 177]] ''prob:5/6/6'' ''rank:638'' | ||
| + | |||
| + | 2020.8.30 [[codeforces666div1|Codeforces Round #666]] ''prob:2/2/5'' ''rank:845'' | ||
| =====题目===== | =====题目===== | ||
| + | |||
| + | 2020 TCO Algo Round 2B - DIV1 第二题 | ||
| + | |||
| + | 2020 TCO South America Qualifier - DIV1 第二题 | ||
| + | |||
| + | 2020 TCO Algo Round 3A - DIV1 第一题 | ||
| + | |||
| + | 2020 TCO South Asia Qualifier - DIV1 第一题、第二题、第三题 | ||
| ======郭衍培====== | ======郭衍培====== | ||
| =====专题===== | =====专题===== | ||
| + | |||
| + | 本周无 | ||
| =====比赛===== | =====比赛===== | ||
| + | |||
| + | 2020.8.29 [[abc177|Atcoder Beginner Contest 177]] ''prob:5/5/6'' ''rank:1223'' | ||
| + | |||
| + | 2020.8.30 [[codeforces666div1|Codeforces Round #666]] ''prob:2/3/5'' ''rank:886'' | ||
| =====题目===== | =====题目===== | ||
| + | |||
| + | 本周无 | ||
| ======本周推荐====== | ======本周推荐====== | ||
| 林星涵：[[后缀数组|后缀数组]] | 林星涵：[[后缀数组|后缀数组]] | ||
| + | |||
| + | 推荐理由：经典的后缀结构工具，用途十分广泛 | ||
| 陶吟翔： | 陶吟翔： | ||
| - | 题目大意： | + | 题目大意：有一个$(H+1) \times W$的矩形，你可以从第一行任意一个点出发，只能向下或向右走，但是对于每一行$i$，这一行的第$A_i$到$B_i$个格子不能向下走，问对于$2$到$H+1$，到达这些行最短走几格，如果不能走到输出-1 |
| - | 数据范围： | + | 数据范围：$1 \le H,W \le 2 \times 10^5$ |
| - | 解题思路： | + | 解题思路：首先走到第$i$行肯定要向下走$i-1$，所以我们考虑最小化往右走的次数，在一开始所有格子的开始和结束位置都是自己，因为可以从任意一个格子开始，往右走最小步数是0，但是对于第$i$行的区间$[A_i,B_i]$，里面所有格子的结束位置是$B_i+1$，因为这些格子不能往下走，而我们发现，一但很多个格子的结束位置相同，我们就不用考虑远的那些，直接考虑最后面那个就行了，所以我们用一个set维护格子，一但有格子结束位置一样我们就删到只剩最后一个，然后每次找向右走步数最少的格子输出，如果格子都被删光了就无法走到，输出-1。关于找到向右走步数最少的格子，可以用一个multiset来存目前剩余的格子的值，输出时直接调用multiset的最小值即可 |
| - | 推荐理由： | + | 推荐理由：首先对于最小化向右走的次数和删去不必要的格子考察了做题者的观察能力，同时set和multiset的维护方式考察了做题者的语言运用能力 |
| 郭衍培： | 郭衍培： | ||
2020-2021/teams/hotpot/200829-200904.1599195026.txt.gz · 最后更改: 2020/09/04 12:50 由 喝西北风
