NOIP 2024 游记

Day 0

上午重新练习了 NOIP 2023，然后开始摆烂。

下午提前润去酒店，和 gls 一起吃饭并复习了一些基础的算法。

十点就睡了。

因为紧张，睡觉的时候辗转反侧，至少睁眼了 4 次。

Day 1

7：00 就起床了，吃完早饭到考场已经 8：00 了，遇到了 SFLS 的同学和炘子。

T1 以为会是萌萌题，仔细想了想按位贪心想不明白，然后换成连通块，贪心放剩余 01，和区间交集长度取 min，感觉很对，写完过了大样例，大概过去了半小时。

T2 一开始以为是什么 k-SAT 神秘题，结果发现限制只有相邻的，考虑一条链，然后 DP，转移枚举这条链的结尾，想不明白，发现 \(n\le 10^9\)，战术上厕所之后回来发现直接正解好像更简单，只要从上一个已确定的变量转移就行，系数大概是整体减空白一下，调了很久大样例发现多测没清干净，于是统一 memset 了，过了大样例，现在大概是 10：00。

又去上了个厕所，回来给 T2 写了个拍，拍的时候想 T3，T4，发现 T3 很难，考虑特殊性质，链直接输出 1 就行，菊花的话貌似 DFS 树只会是链，所以答案就是 \((n - 1)!k - \binom{k}{2}(n- 2)!\)，\(k = 1\) 貌似对每个团的答案合并一下就可以了。

感觉 T4 更可做一点，想到了性质 B 和 \(O(nq)\) 的做法，链好像有点困难，列出式子貌似直接二分答案，然后主席树 / 整体二分维护区间最大连续 1 子段即可，这是 \(O(n\log^2n)\) 的。

100 pts 感觉可以做线段树合并，然后启发式合并颜色，用线段树维护区间最大连续颜色相同子段，但是感觉很难写，注意到我现在 T3 有一定暴力分，为了求稳只写了暴力和特殊性质，测了大样例竟然爆栈了，不会开无限栈，于是写了特判链的 DFS，跑了 2.1s，感觉有点寄，但是没时间卡常了。

写了一个小时，这时候大概已经 12：00 了，一个小时写 T3 怎么输！（伏笔），想了半小时正解发现不会，直接写菊花把上式糊上去，竟然过不去大样例，调不出来，先把代码放虚拟机上编译一下，发现 T4 好像要特判 n = 1，赶紧加上，最后十分钟一直怀疑自己式子推错了，但是感觉对完了，检查一下就交了。

出来讨论人均 300pts，死棋了，bamboo12345 发现我的式子很对，但是 \(n\) 是边数，而我没有减一！！！破防了，在公园蒸完回家写游记。

估分 100 + 100 + 4 + [52, 64] = [256, 268].

感觉退役了……