「JOISC 2019 Day4」蛋糕拼接 3

若现在已经选出了若干元素,为了使其价值尽量大,一种最优方案是按 $C$ 排序放置,这样后面那项就只有:

$$ 2\times (\max C_i-\min C_i) $$

考虑枚举 $\max C_i$ 是谁,可以发现 $\min C_i$ 的选择是单调的,也就是越大的 $\max C_i$ 不会选择更小的 $\min C_i$。直接决策单调性,套个主席树就行了。复杂度 $\mathcal{O}(n\log^2 n)$。

「JOISC 2019 Day4」合并

显然可以转变为:没有一个子树内颜色是“封闭”的。首先可以找出所有断后不合法的边,断掉后得到若干连通块,缩点之后再将边连回来,这样的树与原来等价,可以看作每个点颜色不同。

操作次数下界是叶子个数除 $2$ 上取整。

「JOISC 2019 Day4」矿物

首先可以使用 $2n$ 次操作,将元素划分为两个集合 $A,B$。

然后考虑朴素的二分,对每个 $B$ 可以用 $\log$ 次确定对应的 $A$。套一个整体二分,但这样过不了。

考虑不从 $0.5n$ 处二分,设这个常数是 $p$,实际上操作次数是:

$$ F(n)=(1+p)n+F(pn)+F((1-p)n) $$

不知道怎么解出 $p=\dfrac{3-\sqrt{5}}{2}$ 的时候最优,注意 query 操作不能撤销,不然常数就爆炸了,正确的做法是在整体二分的时候,记录一下当前区间的 $A$ 元素是全部都在集合中,还是全都不在集合中。

标签: none

添加新评论