船长的乱做记录 II

今天放假,结果大机房居然一个人都没来!也罢,思拨小教练把高版本Ubuntu全部刷没了,那就苟小机房乱做题呗。

博客也莫名上不去了,难受~

这天做了 2 题!

[SCOI2015]小凸玩矩阵

这道题很容易看出是个二分。

不过二分的判定条件,仔细想了想:\ge mid 的数 \ge k 个并不能保证 mid 恰好是第 k 大的,其实这很显然;而 \le mid 的数 \ge n – k + 1 个却是也可以的。因为题目要求的是第 k 大的数最小,所以某种程度上也代表了一个微妙的顺序。

[SDOI2015]寻宝游戏

显然题目求的是当前有宝藏的点(姑且称作黑点)构成虚树上所有边长之和的两倍。

一开始想了个HLD+乱搞维护虚树的做法,后来实在是懒得写于是去贺了一发。

我们把虚树上的点按dfs序排序排成环,那么答案就是相邻两个点距离和。

看来还需要更进一步的思考啊~

我也不记得这是哪天写的题了,一天写2题太难看了


于是我把今天的也写进去吧…

今天做了  4  题(加上XY的SB题)

早上打XY的xx分班赛,T1打表续了好久就不用说了,T2好容易写个正解然后测出来跟暴力一个分(后来他跟我说忘记说要取模了?玩我?),T3稍微有点意思。

T3

题意:一棵 n 个点的树,你要把树分为若干连通块,要求每个连通块的直径都不超过 D,求最少分几个连通块。

n\le 500

其实这个题很类似对树分块的过程,我们解决每棵子树里的子问题,把直径还小于 D 的连通块提到上面来,每个节点的子树对它有用的信息就是它提上来的部分最长链长度。

[HNOI2016]最小公倍数

这道题这个分块是真的想不到,因为它实在太暴力了。

丁老师说今年APIO第一题跟这个题很像,这么说来JB给我的题目我还没瞅过呢。

我们对于只有一个询问的情况,可以把 a,b 小于等于约束的边加入,并查集维护连通性,并维护对应的连通块内最大的 a,b 是否是给定的 a,b.

对于多组询问,我们考虑把边按 a 排序,询问按 b 排序,然后将 a 分块。我们对于边的每个块,回答 a 值在当前块所属的区间内的询问。回答这些询问前,我们暴力将之前所有的边按 b 排序,这样,我们回答这些询问前,之前块的 a,b 均能保证是小于等于询问的约束的。当然,当前块中可能也有一些边满足约束,我们直接暴力把他们加进来。当然这样操作之后并查集是需要还原的,不过清空所有太过分,因为之前块的信息加入其实是一直有用的,所有我们需要一个按秩合并的并查集,并且搞一个栈来记录历史信息以便撤销。

这个复杂度… O(n\sqrt{n}),这个 n 不是指任何 n,毛估估一下吧…

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注