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$

题解：

陶吟翔：

郭衍培：题目链接

给定长度为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$满足要求，否则不存在满足要求的解。