20200201

## 考场心路历程 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的方式求其最小割。  证明比较简单，不做赘述。