UOJ Logo peehs_moorhsum的博客

博客

Moorhsum Round #1 题解

2018-05-05 21:45:25 By peehs_moorhsum

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

评论

he_____he
太强啦
oscar
http://zijian-lv.com/submission/1228 呜呜呜。。为啥我比赛没交这个暴力啊。。。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。