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插掉了,就只剩了一半,于是简单到爆炸

评论

fpdqwq
oscar有毒
function
所以C题输入的t是干什么用的
newbiedmy
考虑考虑开课了
newbiedmy
B题奇怪算法亲测能过
newbiedmy
A题结论不给证明的啊
HHzzkk
能细讲一下C按时间分治的套路吗QwQ
yww
oscar太强了 %%%
jjikkollp
oscar牛逼
CaiWeiHan
T2 题面说 $m \ge 1$ 但数据似乎有 $m = 0$ 的点是怎么回事呀qwq
newbiedmy
克拉克莱柯克兰

发表评论

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