2020.5.23 Nordic Collegiate Programming Contest 2015 prob:7/7/10 rank:1/29

本周无

本周无

Codeforces Round #645 (Div. 2) prob:4/5/6 rank:523

本周无

林星涵： 题目链接

题意：有n个区间，选择区间，使得在保证任意时刻不会有超过k个区间重合的情况下区间最多。

数据范围：$1 \le k < n \le 100000$

题解：这题我们采取贪心的思想，我们按照区间左端点排序加入区间，在已经有 $k$ 个重叠的情况下，如果新加入第 $k+1$ 个区间，显然我们要弹出区间右端点最大的区间，同时在读入新的区间时，将右端点小于当前区间左端点的区间弹出，用平衡树来维护这种关系即可。

陶吟翔：传送门

题目大意：在一个平面给出$n$点，再给出$p$圆，问有多少点没有被覆盖。（一个坐标上可以有多个点）

数据范围：$n \le 10^5,p \le 2 \times 10^4,r_{max} \le 100$

解题思路：这道题的点数较多，但是坐标范围不大，圆的半径也只有一百，所以我们可以每一个横坐标或者纵坐标开一个平衡树，然后每次处理到一个圆就按照范围对最多200棵平衡树进行操作，鉴于是要删除里面一个区间的点，可以考虑从直接使用splay删除一个区间里的数。（当然林佬的做法也很秒）

郭衍培：题目链接

给定长度为n的数列，保证后$\lfloor \frac n2 \rfloor$个数是相同的。求一个k，使得任意连续k个数的和都大于0，若不存在输出-1

显然，如果数列的总和大于0，则只需要取k=n即可。如果数列总和小于等于0，而后$\lfloor \frac n2 \rfloor$个数大于等于0，则一定不存在满足要求的k（否则取若干个连续k项加末尾若干个数，得到数列总和大于0）。 因此，只需解决数列总和小于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+k_i>n$，则$k_i$满足要求，否则不存在满足要求的解。