2020-2021:teams:hotpot:200523-200529
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200523-200529 [2020/05/29 16:09] misakatao 更新 |
2020-2021:teams:hotpot:200523-200529 [2020/05/29 18:06] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| ====专题==== | ====专题==== | ||
| + | |||
| + | 本周无 | ||
| =====陶吟翔===== | =====陶吟翔===== | ||
| 行 17: | 行 19: | ||
| ====个人训练==== | ====个人训练==== | ||
| - | [[codeforces641div2|Codeforces Round #641 (Div. 2)]] ''prob:5/6'' ''rank:170'' | + | [[codeforces645div2|Codeforces Round #645 (Div. 2)]] ''prob:4/5/6'' ''rank:523'' |
| =====郭衍培===== | =====郭衍培===== | ||
| 行 27: | 行 29: | ||
| =====本周推荐===== | =====本周推荐===== | ||
| - | 林星涵： | + | 林星涵： [[https://nanti.jisuanke.com/t/A1389|题目链接]] |
| + | |||
| + | 题意：有n个区间，选择区间，使得在保证任意时刻不会有超过k个区间重合的情况下区间最多。 | ||
| + | |||
| + | 数据范围：$1 \le k < n \le 100000$ | ||
| + | |||
| + | 题解：这题我们采取贪心的思想，我们按照区间左端点排序加入区间，在已经有 $k$ 个重叠的情况下，如果新加入第 $k+1$ 个区间，显然我们要弹出区间右端点最大的区间，同时在读入新的区间时，将右端点小于当前区间左端点的区间弹出，用平衡树来维护这种关系即可。 | ||
| + | |||
| + | 陶吟翔：[[https://nanti.jisuanke.com/t/A1391|传送门]] | ||
| + | |||
| + | 题目大意：在一个平面给出$n$点，再给出$p$圆，问有多少点没有被覆盖。（一个坐标上可以有多个点） | ||
| + | |||
| + | 数据范围：$n \le 10^5,p \le 2 \times 10^4,r_{max} \le 100$ | ||
| - | 陶吟翔： | + | 解题思路：这道题的点数较多，但是坐标范围不大，圆的半径也只有一百，所以我们可以每一个横坐标或者纵坐标开一个平衡树，然后每次处理到一个圆就按照范围对最多200棵平衡树进行操作，鉴于是要删除里面一个区间的点，可以考虑从直接使用splay删除一个区间里的数。（当然林佬的做法也很秒） |
| 郭衍培：[[https://codeforces.com/contest/1358/problem/E|题目链接]] | 郭衍培：[[https://codeforces.com/contest/1358/problem/E|题目链接]] | ||
2020-2021/teams/hotpot/200523-200529.1590739778.txt.gz · 最后更改: 2020/05/29 16:09 由 misakatao
