2020-2021:teams:hotpot:200523-200529
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200523-200529 [2020/05/29 17:33] lotk |
2020-2021:teams:hotpot:200523-200529 [2020/05/29 18:06] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 37: | 行 37: | ||
| 题解：这题我们采取贪心的思想，我们按照区间左端点排序加入区间，在已经有 $k$ 个重叠的情况下，如果新加入第 $k+1$ 个区间，显然我们要弹出区间右端点最大的区间，同时在读入新的区间时，将右端点小于当前区间左端点的区间弹出，用平衡树来维护这种关系即可。 | 题解：这题我们采取贪心的思想，我们按照区间左端点排序加入区间，在已经有 $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.1590744836.txt.gz · 最后更改: 2020/05/29 17:33 由 lotk
