2025 noip 游记喵

· · 生活·游记

DAY -1

在家，tetr.io 打到了 4k 分，机心无敌了。

诶我怎么有点感冒？

DAY 1

诶我怎么有点发烧？

算了不管了先考试吧

开题，t1 是个签，考虑哪个会选超过 1 次即可，1 min 会了，写写写，饶是如此我依旧写了 20min。

开 t2，数数题？？？？？？我不会啊，跳了。

开 t3，一开始读错题了以为要求整棵树 mex，仔细读题之后发现不会，跳了。

开 t4，一眼出了一个 O(n(R-L)+nq\log n) 的离线分治做法，空间是 O(nq) 的，应该有一点点分，中途电脑莫名其妙死机了，获得加时。

大样例跑了 16s，卡不过去 qnq。

发现特殊性质都跑的挺快的，应该是有剪枝的缘故罢。

t4 预处理的的滑动窗口拆下贡献应该可以做到 O(nq\log n)，还有 2h，不一定写得完写完也不一定跑得过，先去看 t2。

感觉加一个 0 之后不合法状态一定前面任意中间一个 1 然后一些 2 然后又一个 1，调整方法去掉两头的 1 然后选中间的 2。

于是就可以枚举两头的值为 a_x 和 a_y，分别维护第一个大于等于 2a_x 和 a_x+a_y+1 的值，然后考虑一个组合意义：

显然是到左边的 2a_x 之前的数选 t 的话对前缀代价有 t 的贡献，2a_x-1 到 a_x+a_y+1 中必须取一个 2 在 a_x 到 a_y 性价比区间里成为被调整的数，剩下的取什么贡献和下面一样，a_x 到 a_x+a_y 中的数选 2 则有 0 的前缀贡献，选 1 则有 1 的前缀贡献。

而 a_y 到 a_x 这段区间已经被确定（中间的数必须全选 2 保证他们俩性价比区间中只有 1），<a_y 的可以任意取，于是两个组合数的差乘一个二的幂求和即是答案。

推出了这样一个有四个系数的组合式子，还可以平方计算，应该是正解了，然后调调调，发现小样例过了，大样例死活过不去，诶 wc 没时间了。

再见 oi，希望你我喜欢这 7 年来属于你的戏份。

甲流我*****，为什么非得当天发作啊。