noip 2022 vp 寄

· · 个人记录

话说 @kinnikinnick233 为啥还没写他的 noip 游记。

17:05 过 A。

然后发现 B 根本不会做。遂跳。事实证明这个选择是正确的。

C 同样不会做。骗了个链的情况的 10pts。此时 17:17。花了半个小时推树的情况的 dp 式子然而因为我并不会树形 dp 所以我并没有推出来。

D 发现 a,b 均随机时单调栈的期望元素个数是 \Theta(\log n) 的，于是可以骗到 36pts。然而我写挂了，然后我就被叫去吃饭了，吃完刷了一个小时的知乎。

刷完知乎看了眼群，发现 @fast_photon 已经会了 t2 的 30pts 和 t3（的假做法），感到非常惊恐，于是又重构了一下代码，然后过了。此时 21:05。

100+0+10+36=146