咦,Day 2 怎么消失了

「JOISC 2019 Day3」指定城市

$E=1$ 的时候可以换根 $\text{dp}$;$E=2$ 的时候也可以树形 $\text{dp}$。

可以证明,当 $E>2$ 的时候,贡献是凸的,而且 $E$ 的方案一定包含 $E-1$。因此只需要在 $E=2$ 的基础上,把树类似长链剖分,每次取贡献最大的长链即可。

时间复杂度 $\mathcal{O}(n\log n)$。

「JOISC 2019 Day3」开关游戏

三个操作中前两个赋值看起来比较相似,易于证明存在一种最优方案可以先只赋值,后面只 $\text{flip}$。

把一个状态的 $01$ 交接点拿出来,则一个 $\text{flip}$ 恰好可以消去/增加两个交界点,因此最后计算两个状态的交界点的对称差,若剩下 $s$ 个,则最后还需要 $\left\lceil\dfrac{s}{2}\right\rceil$ 个 $\text{flip}$。

设 $\text{dp}_{i,0/1/2}$ 表示前 $i$ 个元素,最后一个元素被变成 $0/1$ 或者不变,对称差交界点个数的最小值。一次操作可以当作两个对称差交界点,也就是把 $\text{dp}$ 值 $+2$。

「JOISC 2019 Day3」穿越时空 Bitaro

首先把时刻 $i$ 的时间 $-i$,这样走一步可以看作不花费时间。

如果要经过一个点,有两个分段函数:$f(t)$ 表示 $t$ 时刻进入之后,什么时候会出来;$g(t)$ 表示 $t$ 时刻进入,需要花费多少代价。

$f(t)$ 的形式肯定是前后两段平,中间 $f(t)=t$;$g(t)$ 是前面平,后面一次函数。合并两段的时候,由于 $f(t)$ 是单调的,所以 $f'(f(t))$ 也是单调的,还是类似的形式;$g(t)$ 会加一个截距,但后面一次函数的形式保持不变。

因此可以线段树维护折线,$\mathcal{O}(n\log n)$。

标签: 线段树, dp, 贪心

添加新评论