这个oj突然来了很多神仙w

有没有时间把moorhsum round1做一做呀

代码量极小

但有的题直到现在只有验题人和出题人过了[委屈]

这场比赛题目中人物的首字母和下发文件是一样的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

Moorhsum Round #1 将于 5 月 5 日举行，欢迎校内外同学参加。

比赛一共包含三道题目，记Rating。

比赛时间

北京时间 2018 年 5 月 5 日 18:00 ~ 21:00

出题阵容

题目提供者：三道题均由peehs_moorhsum提供

验题人：wzj52501

比赛难度

验题人认为，比赛难度约为弱省省选

温馨提示：题目按难度降序排列

UPD：比赛已经结束！

恭喜获得前 5 名的选手！

1. AKEE
2. fpdqwq
3. he_____he
4. oscar
5. Caro23333