2020-2021:teams:hotpot:200523-200529
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:200523-200529 [2020/05/29 14:29] 喝西北风 |
2020-2021:teams:hotpot:200523-200529 [2020/05/29 18:06] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| ====专题==== | ====专题==== | ||
| + | |||
| + | 本周无 | ||
| =====陶吟翔===== | =====陶吟翔===== | ||
| 行 14: | 行 16: | ||
| 本周无 | 本周无 | ||
| + | |||
| + | ====个人训练==== | ||
| + | |||
| + | [[codeforces645div2|Codeforces Round #645 (Div. 2)]] ''prob:4/5/6'' ''rank:523'' | ||
| =====郭衍培===== | =====郭衍培===== | ||
| 行 23: | 行 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|题目链接]] | ||
| 行 33: | 行 51: | ||
| 显然，如果数列的总和大于0，则只需要取k=n即可。如果数列总和小于等于0，而后$\lfloor \frac n2 \rfloor$个数大于等于0，则一定不存在满足要求的k（否则取若干个连续k项加末尾若干个数，得到数列总和大于0）。 | 显然，如果数列的总和大于0，则只需要取k=n即可。如果数列总和小于等于0，而后$\lfloor \frac n2 \rfloor$个数大于等于0，则一定不存在满足要求的k（否则取若干个连续k项加末尾若干个数，得到数列总和大于0）。 | ||
| - | 因此，只需解决数列总和小于0，且最后$\lfloor \frac n2 \rfloor$个数小于0的情况。此时，显然有$k>\lfloor \frac n2 \rfloor$ | + | 因此，只需解决数列总和小于0，且最后$\lfloor \frac n2 \rfloor$个数小于0的情况。此时，显然有$k>\lfloor \frac n2 \rfloor$。 |
| - | 记录前$\lceil \frac n2 \rceil$个数的后缀和，并计算以i为起始，和为正的最大长度$l_i$。记录$k_m=\min_{i=1}^m{l_i}$，直到第i项，有$i+k_i>n$，则$k_i$满足要求，否则不存在满足要求的解。 | + | 记录前$\lceil \frac n2 \rceil$个数的后缀和，并计算以i为起始，和为正的最大长度$l_i$。记录$k_m=\min_{i=1}^m{l_i}$。若有$i+k_i>n$，则$k_i$满足要求，否则不存在满足要求的解。 |
2020-2021/teams/hotpot/200523-200529.1590733799.txt.gz · 最后更改: 2020/05/29 14:29 由 喝西北风
