211016模拟赛

概述

今天的模拟赛还行。

期望 $100+0+40+52=192$，实际 $100+0+20+52=172$​。还算可以。

赛时

发现 T1、T3 都是期望，T2 看不懂，T4 是个树论。

手玩 T1 样例，发现了一些规律，写了个 $O(n^2)$ 暴力，然后写了个 $O(n\log n)$ 的线段树优化。

$n=10^6$，我意识到线段树常数有点大，但是我又不会树状数组。于是我卡了卡常，发现在我的机子上开 O2 要跑 $600\text{ms}$​，感觉能过，又快速写了个数据生成器对拍。没拍出来啥问题，好评。

去做 T4，有 $32$ 分比较白给，然后想了一个多小时搞出来了 $20$​​​​ 的部分分。发现我还是不会写树状数组，于是又搞了个线段树上去。写完之后发现数据非常好造，于是快乐对拍，把 bug 都搞掉了。

快结束了，T2 还是看不懂，快速推了 T3 $n=1$ 的式子，写完调完就溜了。最后几分钟又乱搞了 $20$ 分，不过似乎假了。

总结

对拍是非常有必要的。

一些简单的卡常技巧需要学会。

不能什么都线段树，树状数组也是有用的。

发现我不会期望，推式子能力也挺差的，老暴力选手了。。。。。