省选联考 2020 游记

· · 个人记录

Upd 挂了三十五分

坐标 CQ，考 A 卷。

Day 1

上来花了两个小时打 t1 的 n^2 暴力，不知道自己怎么想的（当然中间去把 t2 30，t3 15 写了）

然后发现 n\log ^2 n 很好写就写了。最开始写的线段树，后来大概在 11:00 时换成了树状数组。之后发现稍微转化一下就能 O(n\log n) 就开写了。大约在 12:30 时过了自己的数据。跑了下极限数据，发现要 7s…… 加了快读快输就 2.5s 了。

12:50 时 发现要离散化，就匆忙加了个。还是很慌，不知写对否。极限数据要 2.8s。

期望得分 100+30+15=145。遗憾是没做出来 t2。我省选前一天才搬过一样的题啊啊啊啊啊啊

希望不要挂分（

Day 2

先把三题 30+10+50 暴力写了。写完大概十点了 。

然后去搞 t2。发现可以转化成区间加区间 xor 但是似乎是不可做的……然后发现树的特性很有用，可以直接继承重儿子信息，于是就转化成了全局加 1，全局 xor。这不就是 AGC044 的 Strange Dance 吗？从低位往高位建 Trie 树上面打个 xor 标记就能维护了。

写完调完大概十二点了，极限数据要 3s。加了快读快输，vector 换成邻接表就 1.4s 了。

然后试图搞 t1，没有成功。

期望得分 30+100+50=180。被吊着打 /kk