20200201

2020-02-01 14:57:00


考场心路历程

T1看了看,决定跳过。

T2首先打了一个DP。

T2那么大的数据,显然是一个 $\Theta(n\ log\ n)$的解法。

考虑T2的贪心。我们显然不可以sort。但是我们发现前 $i$天必须至少有 $(i+1)/2$天买入股票。然后开一个堆,记录当前应当卖出的那支股票。

然后对拍,发现正确。但是在考场上实现的时候,出现莫名WA。最后通过快读解决。

T3对于前四十分,我们发现可以使用 $\Theta(n^2log\ n)$的解法,即随机根节点,枚举任意两点,在计算LCA时顺带计算最大左边界和最小右边界,最后再判断合法性。

这是考场上的解法,但是出现了实现上的问题。最后订正成功。

T3 假正解

最后对于T3我们发现,对于每一个节点,跑一个DFS。实践证明当数据随机时,搭配可行性剪枝,该解法非常优秀。最后没有使用任何编译优化地通过了。在出题人恶意的情况下,可能到达 $\Theta(n^2)$。这个之后再说。



18:26 喝了点亦可赛艇的东西之后,回到电脑前,尝试给出T2的证明。

T2 贪心证明

首先,我们显然会有 $n/2$笔进账和 $n/2$笔出账。进账不可能比出账多,而如果出账远大于进账,那干嘛不随便选几个改为进账呢?毕竟卖出股票不可能还要倒贴钱。所以,我们得出进账出账数量相等的结论。更重要的是我在XJOI上验证过n为偶数2333

那么我们不妨设我们一旦有股票我们就保证卖出。这样一来,我们首先能够保证我们的推论正确。

由于我们可能不能在最合适的时机卖出股票,我们选择在可以反悔时反悔。

根据我们的推论,奇数天必买,偶数天必卖。

如果我们在奇数天的时候发现,我们的要买的股票价格太贵。我们可以选择之前某一天贱卖的股票换。即,撤销之前的卖出操作,而改为买进;同时,将本次买进的操作改为卖出。

这样,对于任意时刻,我们达成的都是当前条件下的最优策略,因为我们有足够的时间反悔。想象一下,如果我们没有充分的时间反悔。假如有一天的股票(股A)应当卖出,而非买入;而相对应的有另外一天的股票(股B)应当买入,而非卖出。那么只要B在A的前面,我们的算法都能够反悔。当然,除非有一只股C,当股B与股C交换时能比与股C交换创造更多收益。这个时候当然优先选择股C,否则创造的收益反而更少。

T1正解

根据某篇博客的思想,我们首先学习一个概念:最大权闭合子图。

大意是对于一张图,每一个点都有一个点权。要求每一个点的后继都在这一张子图内。并要求所选点的和尽可能大。 图片来源见水印

显然,这类问题存在的意义在于有负点。

我们可以用连ST的方式求其最小割。

图片来源见水印

证明比较简单,不做赘述。