NOI 2026

· · 生活·游记

Day 1

做T1，感受了一下发现会了一个做法，但是状态是 O(m^2 k) 的做法，感觉应该能 O(1) 转移。
但是被 t = 20 组多测诈骗了，于是没写继续思考更优的做法。
想了 ~30 min 之后，发现自己特殊性质都不会更优的做法，于是决定写上述做法。
先写了一个暴力验证一下正确性，大概是 O(n m^2 k)的，提交发现获得了 76p , 大为震撼。
前缀和优化一下发现轻松通过了，卡了一下常数就扔掉了，大概是 O(n m k)的，此时 1.5h。
做T2没啥想法，遂思考链的特殊性质，做了一会发现应该是前缀 / 后缀随机，其他暴力指向 y ，发现细节挺多。
写了一万年得到了一个 O(n ^ 3) 做法，交上去发现正确性没问题，发现都可以三分遂做到 O(n \log^2 n)，此时 10:30。
尝试推广到一般情况感受了一下，发现形式非常优美， 11:00 获得了 60p。
此时我意识到只需要把暴力改成三分，然后只需要支持邻域查询的数据结构即可通过此题，我选择了点分树。
由于我赛前没有写板子，导致我几乎是现场发明了一遍点分树，在 12:30 完成了代码并通过了大样例。
遗憾的是我发现他的耗时特别久，我写的点分树在重编号上需要一个哈希表，我尝试了 map 和 umap 都无法通过。
提交到 selfeval上获得了 60p , 和暴力一致。我完全不知道如何去掉哈希表（赛后发现是不困难的），在思考一会后选择了放弃。
最后 15min 我匆忙地去写了 T3 的暴力 , 会了一个问 1 \sim W 的做法，可以通过第一个子任务，由于我觉得他问的次数实在是太多了，于是没有让他跑最后两个子任务，但是赛后发现他可以在最后两个子任务获得 6p。
最后 Day 1获得了 100 + 60 + 10 分，赛后讲评发现许多选手 T2 和我的做法一致并获得了满分，T3不少人通过一些乱搞获得了非平凡分数。

Day 2

做T1,思考先二分之后如何判定，一开始我认为这是十分平凡的，但是开始写代码的时候发现完全不对。
于是我先思考了一下特殊性质，发现 k 是偶数的特殊性质看上去比较好做。尝试了很多做法，最后找到了一种比较有前途的做法并通过了对应测试点，此时 9 : 00。
发现奇数只需要多讨论了一下，冷静思考后发现平方是简单的，于是快速实现了一下 O(n ^ 2 \log n) 的做法，并在 selfeval 获得了 55p，此时 9 : 30。
然后我尝试用数据结构优化这个做法，两种情况中，第一种情况是好做的，可以简单做到线性，第二种情况思考很久之后也只会 O(n \log n)的做法。
加上外层的二分就是2 log , 由于 n = 1e6 , 我并不认为能通过，但最后还是实现了这个做法，发现他轻松跑过去了，获得了 100p , 此时 10:20。
做T2 ， 发现我忘记了 prufer 序列如何还原树，但是经过手玩之后还是会了 O(n ^ 2) 做法，获得了 20p , 此时 11：00。
观察了一下我做法的形式，发现可以做 a_i \le 1000 和 x \le 1000。
可以对值域暴力然后是一个二维偏序状物，我选择了 O(\sqrt n) \sim O(1) 的根号数据结构优化他，理论可以获得 52p。
由于细节不少写到了 12:00 , 发现调试不出来，到 12:30 时放弃了调试，决定先写完 T3 的暴力。
因为之前我看了一下 T3 , 误以为自己会一个 O(n ^ 4)的 做法，看上去能获得不少分，真正实现才发现全错了，不得不写指数级暴力。
在 12:50 在 selfeval 获得了 4分（ n \le 4 ），回去调试 T2 无果，最后1min 我对我T3代码测试了一个 n = 6 的样例,发现他很快跑出来但是结果不对，遂感觉可能 T3 要挂掉了。
出场报的 100 + 20 + 0 , 查分发现 T3 确实挂掉了，120 分。
查完分思考了一下，发现 T2 对值域暴力是完全没必要的，可以多一个限制变成三维偏序，然后使用一个数据结构就能做了。

Day ???

100 + (100 + 60 + 10) + (100 + 20 + 0) = 390 , 银线 394