UOJ Logo oscar的博客

博客

Moorhsum Round #3题解(极简略版)

2018-05-26 19:13:52 By oscar

A. 枚举约数,复杂度分析:调和级数

B.

27分做法:

考虑暴力dijkstra

枚举每个未使用的点,找到全局最小值,拿这个点更新其余所有点。注意存边需要一组一组存/使用邻接矩阵,否则会MLE,复杂度$O(n^2)$

56分做法:

不会正解怎么办?线段树优化建图就可以得到很多分

由于公差相等,只需要用两棵线段树优化建图,再暴力跑一遍dijkstra即可。复杂度$O(n\log^2n)$,可以通过subtask3

100分做法:

观察到subtask2的暴力做法需要支持的操作只有以下三种:

1.区间对等差数列取min

2.查询全局最小值及其位置

3.删除一个点

于是可以用线段树进行维护,每个节点上存一个一次函数,修改时若新一次函数在整个区间内都比当前节点上存的一次函数小则直接替换,若新一次函数在整个区间内都比当前节点上存的一次函数大则return, 否则向两边递归。复杂度证明留作练习(逃 否则算出两个一次函数的交点,用只对当前节点所代表的区间少于一半位置有作用的那条一次函数向下递归。可以证明每次向下传的区间至少会减短一半,所以每次将一个一次函数加到一个节点上耗时$O(\log n)$,而区间对等差数列取min至多将一次函数加到$O(\log n)$个节点上,所以单次操作总复杂度$O(\log^2n)$

呜呜呜上面划掉的部分可能是错的但我不会卡。。 已经卡掉了

删除节点操作只需额外维护每个节点上最左和最右的未被删除位置即可

复杂度$O(nlog^2n)$

好像数据造弱了,没卡n=5000时的spfa

C. 枚举答案,对时间分治或LCT维护连通性(建议大家思考一下subtask4线性做法

对时间分治配合可撤销并查集略微好写一点,且实际速度吊打LCT,复杂度$O(n\log^2n)$

数据没有特意卡不按秩合并的并查集,大家可以考虑去hack

LCT做法是维护以删除时间为权值的最大生成树,复杂度$O(n\log n)$

好像数据造弱了,没卡掉单旋LCT(虽然没人写)

彩蛋1:最后一题为什么那么水

——本来是道二合一,但是由于某验题人把std插掉了,就只剩了一半,于是简单到爆炸

此博客会缓慢更新,最新部分将设为粗体

咕咕咕

Moorhsum Round #3

2018-05-18 10:44:56 By oscar

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

比赛一共包含三道题目,理论上记Rating。

比赛时间

北京时间 2018 年 5 月 26 日 13:05 ~ 18:05

出题阵容

题目提供者:三道题均由oscar提供

验题人:jjikkollppeehs_moorhsumhshs595

比赛难度

出题人认为,比赛难度低于Moorhsum Round #1

温馨提示

1.题目按代码难度升序排列

2.比赛很可能是IOI赛制+subtask评测

3.由于出题人比较毒瘤,每题数据组数40~85不等,可能无法即时反馈测评结果。如果无法及时看到测评结果,有本事你来打我呀,请耐心等待。

4.我也不知道Moorhsum Round #2跑哪去了

5.newbiedmy并不参赛,本次比赛是涨rating的好机会!

6.公正爱国法治自由法治自由法治富强和谐诚信富强文明诚信平等文明友善敬业法治法治法治法治法治法治文明诚信自由公正友善平等公正平等法治敬业公正公正公正和谐文明诚信自由公正诚信自由公正平等法治自由文诚信平等公正文明公正文明法治和谐文明友善敬业法治自由公正友善敬业公正友善敬业公正诚信文明法治和谐文明友善敬业法治自由法治平等公正自由公正友善敬业法治平等公正和谐公正诚信平等公正自由公正平等文明友善爱国公正民主法治和谐法治富强法治爱国(为啥是蓝色的?)

2017-11-15 16:54:14 By oscar
此人很懒,什么博客也没留下。
oscar Avatar