NOI 2025 退役游记

趣事

碎碎念

事实就是这样吧，那些平时看似水平远不如我的人一个一个都 Au 了，而我却在队线外数名。去年看着学长们也是这样，甚至有点为此打抱不平。而今年这样的人，却变成了我。

此时的大家应该都在嘉年华狂欢，而我却在宿舍一个人痛哭着。五年了，这么多年来的努力终究还是在一念之间化为一片灰烬。还是非常难以接受。或许，这就是命运吧。

以前我总觉得自己讨厌矿井，恨它吞掉了自己的青春。但现在才知道，我已同它融为一体了。恨也罢，爱也罢，它就是我的青春了。

——《地火》，刘慈欣

胡校来送考了。说了一些话，感觉很有道理。

要来了？

看了 T1，感觉是送的。20 min 写完了。

看 T2，最开始看错题了，看成必须 a_i\leq a_{i+1} 然后发现很水。显然过不了小样例，于是发现了正确的题面，发现还是很水，容易做到 O(n^2\log n)，感觉不太能跑满？花了点时间写完了，交到 selfeval 上直接过了。

看 T3，打算先想特殊性质，先观察样例发现结果都是 2 的次幂，然后推了一些东西发现其实答案很简洁，可以用 O(nh\log n) 的时间 hash 之后用 map 维护。然后推广到一般情况，发现换成 xor hash 就可以。写了，拿了 80 分。

还剩 2.5h，开始想 T2 正解，有一个颜色段均摊，需要对两条链做均摊，感觉不太好做。过了很久之后才发现直接树剖+线段树+set 就可以，不过常数巨大且代码难写，只剩 1h 了就没写。

做了充分多的检查与卡常，实际得分 280 没挂。

上午去社会实践。纯梦游。

下午感觉精神不佳，于是翘了电影睡觉。

晚上出去走了走。然后回来听胡校讲话。在宿舍里唱了春日影。

看 T1，发现答案容易被表达，写了个暴力验证发现对了，然后随手写了个线段树优化就过了。

看 T2，不知道考场上在想什么，想要先容斥一步，再做一车计算和化简得到了一个式子，可以做到 O(3^nn)，获得 36 分。

继续想 B 性质，发现可以用一步子集和自己卷自己做到 O(2^nn^2)，总共获得了 48 分。

T3 只会 O(qn\log n)，35 分。

总共 100+280+183=563。Ag 了。差 5 分。

实际上，只用把 D2T2 B 性质中的子集和换成或卷积就可以获得 68 分（这一步是容易的），但是考场上就是没想到。