这场比赛题目中人物的首字母和下发文件是一样的w
不过大家忙着做题可能并不会注意到这一点..?
获取名额
from peehs_moorhsum，题解 by peehs_moorhsum
正如公告所说，这是本场最困难的题目QwQ
算法一
仿照样例模拟
时间复杂度：$O(n^3)$
期望得分：20分。
算法二
稍微优化一下算法一
时间复杂度：$O(n^2)$
期望得分：40分
算法三
我会多项式插值！
套个板子可以直接解决l = 1, r = n的部分分
加个线段树，能对其余部分做到 $O(nlog^3n)$
但常数过大，只能得到60分。
算法四
我们注意到，答案 = $1$ - (1 - $a_l$ / $x$ ) ... (1 - $a_r$ / $x$ )
因此我们只需计算出 $1$ - (1 - $a_l$ / $x$ ) ... (1 - $a_r$ / $x$ )
暴力模拟即可。
期望得分：40分
算法五
如何优化计算 $1$ - (1 - $a_l$ / $x$ ) ... (1 - $a_r$ / $x$ ) 呢？
事实上，如果 $a_i$ / $x$ 比较大，则乘积很快会收敛于0
我们每次找到最大的 $a_i$ / $x$，进行乘积；当乘积小于 1 / $10^6$ 时直接输出
但很遗憾，由于数据很强，这样也只能得到40分。
算法六
在算法5的基础上，我们来解决 $a_i$ / $x$ 比较小的部分
我们对ln(1 - $a_i$ / $x$) 泰勒展开，记录 $a_i$ 的若干次方的前缀和
即可得到较小部分的ln值，即为t
exp(t) * 较大部分的贡献即为答案。
事实上，由于x > max($a_i$) ，我们将 $x$ 代换为 $x$ / max( $a_i$ ), $a_i$ 代换为max( $a_i$ )，就可以省去高精度。
渐进复杂度：$O(n * log^2 n)$
事实上，这一算法的常数很小，能够通过本题。
期望得分：100分
省选练习
from peehs_moorhsum，题解 by peehs_moorhsum
对于我这种不善于数据结构的选手来说，这题应该算挺难的？
但这是唯一有人考场通过的题目QwQ
果然我还是菜啊~(>_<)~
算法一
模拟即可
时间复杂度：$O(n^2)$
期望得分：50 ~ 80分
算法二
对于修改少的点，可以用一些set维护每种值出现的位置。
时间复杂度：$O(nlogn)$
结合算法一，可以获得80分。
算法三
分块，每一块有一个懒标记
并用一个unordered_map 记录懒标记更新前每一块中每种值最早的出现位置
时间复杂度：$O(n*sqrt(n))$
期望得分：100分
（如果常数过大可能只有90QwQ）
学校杀
from peehs_moorhsum，题解 by peehs_moorhsum
非常抱歉这题最开始题面出锅了。。。多了两处数据中不存在的限制
不过应该没什么影响？
这题的思路应该是最显然的了..然而细节确实有些多
算法一
按照题目搜索
时间复杂度：$O(q * 2^q)$
期望得分：0分
算法二
事实上，我们可以把所有选手按分数排序
从大到小枚举每位选手
若其所在学校和省队的名额都没满，就将其加入省队
每轮结束后输出新加入的选手即可
时间复杂度：$O(q^2)$ 或 $O(q^2logq)$
期望得分：30分
算法三
对于a = k的点，用一个堆记录省队中选手的最小值和省队外选手的最大值
结合算法二，可以获得50分
算法四
用n个堆，记录每所学校进入省队选手的最小分
用n个堆，记录每所学校未进入省队选手的最大分
用一个堆，记录省队选手的最小分
用一个堆，记录所有名额未满学校的省队外第一名的最大分
分类讨论即可。
时间复杂度: $O(qlogq)$
期望得分：100分
最后，感谢验题人 wzj52501
