AHOI 2025 游记
一个蒟蒻 OIer 的省选游记。
2025.1
牢潘问我要不要去打省选。
我要去，毕竟又可以出去玩了。反正我这种菜鸡，去的作用就是拉低分数线。
没有丝毫准备，开学以来没写过 20 道题。天天摸鱼，打 generals，水 B 站，把省选忘到脑后了。
2.27
啊？后天有省选？明天下午试机？
那太棒了，正好明天下午不上学。/hsh
2.28
上了半天学，大概 14:00 左右出门去芜湖，自驾。
到安师大附中，在门口等了 40min 才进去试机。
什么鬼键盘，空格必须使劲按，对我这种马蜂的人太不友好了。
旁边是位大佬，跟我说他 noip 写了线段树放到回收站里，第二天还在。
于是我写了个线段树，放回收站里了。
发现 Purslane 坐我前面 /bx /bx /bx
3.1
Day 1，准备好打 3 题暴力了，昨天放回收站里的东西没了。
开题了，把三道题从头到尾看了一遍。
T1，什么玩意，不会。
T2，6s 的时限，一眼数据结构，不会。
T3，好不容易弄懂了题目，不会。
此时 Purslane 把自己的椅子坐翻了。
于是我突然会写了 T1，的特殊性质 A，的 n 方写法。
那就写呗，中间 Purslane 去了两趟厕所，我才写好，期望得分 40。
去看 T2，好多特殊性质啊，好像都挺好写，先写个 namespace 把数据点 1~5 写了。剩下的待会写。
去看 T3，特殊性质一个不会，写了个最简单的暴力。
回过头来看 T1，特殊性质优化成线性很简单，一开始没有往这上面想，在想正解。
想了一会想出了很多性质，但还是不会写，便放弃了，因为我当时觉得以我的实力，正解是想不出来的，而且还有很多部分分没有写，于是我去写部分分了。
过了一会把 T1 特殊性质 A 的线性搞出来了，然后去看 T2。
之前觉得 T2 的特殊性质都很好写，但是细细一想发现我一个都不会，甚至特殊性质 ABC 在一起我都不会。
再回头看 T1，想特殊性质 B，想不出来，结束了，应该是 60 + 20 + 8 = 88。
我问旁边的那位大佬 T1，他跟我说了做法，他还说他最后 10min 想到了 T2 正解。
Purslane 说他爆了。
中午吃面，下午在酒店待着，晚上打 generals。
3.2
Day 2，目标是拿 12 分，这样两天就有 100 分了。
开题，10min 内把三题看了一遍，T2 和 T3 的部分分一点头绪没有。T1 的部分分又感觉太简单了。
我感觉很奇怪啊，为什么会有这么简单的部分分？
不管了，反正也想不到正解，就先想部分分吧。想到一半，发现这很像某次 abc 的 f 题。
于是我想出了正解？！
粗略的想了一会，认为是一个区间赋值、单点查询的线段树，觉得很好写，30min 足矣。
于是开始写，写到一半，发现并非区间赋相等的值，而是区间赋一个等差序列。
那就改成在差分数组上区间赋值、查询区间和呗，也挺简单的，感觉 1h 足矣。
改到一半，发现如果要考虑被一个块影响到的其他块，需要二分，再加上线段树是双 log 的，容易被卡。那就写线段树二分呗，虽然没写过，但原理我懂，应该很快就好，1.5h 足矣。
写完了线段树二分，发现还需要给差分数组维护一个另类的带权区间和：
终于写好了我的屎山代码，接近 200 行，还有 2h，感觉能调出来，保险起见，快速写了个特殊性质 B，防止调不出来爆零。
样例 1 没过，查错查了好久，发现线段树 r - l + 1 写成 ((r - l) >> 1) + l 了，改了以后过了样例 1。
出去上个厕所，回来继续调。
只剩 1h 了，劳资今天非要把 T1 搞出来！所有或一无所有！
样例 5 有一个 WA，调了好久找不出问题。不太信任线段树二分，于是改回双 log，就不 WA 了。
但是每个 2e5 的大样例都段错误，于是无脑将线段树的 N << 2 改成了 N << 4，解决了。
后来发现段错误是因为另类的区间和查询写错了，改回来后，将线段树改回 N << 2，还是段错误，算了就 N << 4 吧。
然后跑了大样例，全过了，但是样例 4 跑了 2s 多，希望出题人不要卡啊。
此时只剩 15min，我已被 T1 整的汗流浃背、满面红光，T2T3 来不及了，把样例输进去走人。
结束了，旁边那位也不会线段树二分，写的双 log。他最后 10min 发现 T2 的特殊性质 C 是矩阵树定理，并给我科普了一下这个定理，还说矩阵优化一下 dp 可能就正解了/bx。
于是我 100 + 0 + 0，总共 60 + 20 + 8 + 100 + 0 + 0。
同机房大概有能进队的，本人也只能膜拜了。