NOIP没过黄题记

· · 生活·游记

Day -inf

得知考试前一天放假，太牛了。

Day 1

又没睡好。

开考之前发现有一车人电脑时间有问题。美丽的 lrd 女士不知道为啥换了一台电脑。

上来 T1 就是我们考过的原题，但是想不起来，很急。然后发现按性价比贪，最后几个特殊处理就是对的，打完过后写了个对拍。拍了一万多组，我就不信还能挂。

开 T2，发现不合法当且仅当把最后的两个 1 或者一个 1 换成一个 2 更优，然后很自然的想到枚举第一个 1 和换成的 2。然后大力分讨，发现会了，但是 10 点 50 才写完。

测大样例发现怎么要跑 1.3 秒，我不是纯 O(n^2) 的吗。卡了很久常发现考点的机子限频，只能跑到 2.2GHz，什么【】【】。

看 T3，记录 f_{i,j,k} 表示以 i 为根的子树，\operatorname{mex}(s_i) 等于 j，有 k 个点的权值会往上贡献，最大的 mex 之和。转移优化一下就是 O(n^3) 的，能拿 48 分。

看 T4，发现我会 eps 分，然后决定写假算。对每个左端点取单调队列里前 3 个区间，对每个右端点也取单调队列里前 3 个区间。针对每个 sub 改改似乎可以过 40 分，不过大样例除了最后两个直接过穿了，很有希望啊。

预计 100+100+48+[40,60]=[288,308]。还可以。

发现初中的同学只有我一个上 200。今年 NOIP 怎么变成 NOIplus 了啊。

和 zjx 吃肯德基，然后去看《疯狂动物城2》，好看。

回家颓废。

Day inf

T1 对拍没拍 m 小的，我还是人吗。T3 还因为数组越界挂了 8 分。不过 T4 跑了 65，算是因祸得福了。

最后 90+100+40+65=295，CQ 算上初中高三排 rk20，实力。