NOI2025 有机

· · 生活·游记

Day -2

下午抵达绍兴。在考场旁边的酒店待着，从这能看到考场。

晚上在下雨。

Day -1

上午在下雨。

报道，成功找到了书包中的午餐券，遂吃饭。

晚上可能在打 celeste，中间开了两把杀戮尖塔。

Day 0

开幕式。dzd 讲话感觉比 APIO 的时候有道理。

表演还行，中间有个抽象小品。

下午还在打 celeste。

晚上决定跑步。跑完回来被教练叫去叮嘱考前事项。

听歌。睡不着，到了 0 点才睡。

Day 1

篮球场咋这么热。

然后发现考场上发了个耳塞。之前训练的时候都没带过耳塞，但是感觉考场挺吵的所以就带了。隔音效果还不错。

看 T1。完了之后发现和 NOI 2019 D1T1 有点像。然后 8:18 过了。

然后看 T2。一开始读错题了，以为只能把右边的数减去左边的数。样例 1 直接过了，但是样例 2 挂了。遂发现实际上是一个从两边向中间操作的形式。考虑按每个这样的段转移，发现每个段里面只有一个非 0 的数，并且这个数的值是确定的，且位置是一段区间内的所有奇数/偶数位置。想了想发现做最优化够用了，在 9:00 获得了 40 分。

然后感觉计数也是不难的，打算先看一眼 T3。T3 先想 A 性质，发现答案是 2 的幂次，因此考虑统计有多少子树能给答案乘 2。注意到若 u 的两个儿子有一个是空的，则可以交换两个儿子；否则若存在 v 使得 v 的子树内颜色集合与 u 相同，可以同时将两棵子树的 dfs 序翻转，给答案乘 2。因此猜测答案的 2 的数量即为两者之和，写一发发现对了。拓展到一般情况也不难，首先应当把子树内颜色集合改成子树内仅出现一次的颜色集合，其次需要考虑子树等效于空结点/单个叶子，即子树内只有 \le 1 个结点仅出现一次的情况。此时该子树也是可以翻转的，也要贡献到答案中。这个时候打了个 O(n^2) 验证，10:00 的时候获得了 56 分。

想了想决定先打 T2，因为感觉 T2 好打。发现前面的结构其实已经不重不漏，直接把 \{\max,+\} 换成 \{+,\times \} 就能通过。然后回去把 T3 的做法改了改，把复杂度降到了 O(nh\log n)，其中 h 是树高。此时已经过去 3 个小时，总计获得了 280 分。

然后感觉这个分差不多了，于是开始慢慢思考 T3 正解。糊了个持久化线段树合并之类的做法，打出来发现假了，因为与 u 颜色集合相同的另一子树 v 不一定是所有 u 中颜色的 \text{lca}。但是注意到这玩意能过 A 性质，于是开始调，但是到结束也没调完。

出去听说有 100 个 280？ 后来教练说队线好像只有 230 多的样子。

Day 1.5

在 杜教筛 杜教授的建议下，改去了科技馆和绍兴城市规划馆。

下午回来了，安排是看电影。先投屏故障了一会，放了 10 分钟感觉不好看，就跑了。

晚上继续跑步。这回 23:00 就睡着了，

Day 2

但是早上 5:40 就醒了。

开题，T1感觉好做的，想了想实现，最后写了维护每相邻三个数构成的二进制数，8:40 通过了。

然后看 T2。先做 B 性质，推了推感觉是子集卷积，但是复杂度似乎过不去。然后发现推错了，改完以后是或卷积，加上 O(4^n) 有 68 分。因为考前对 D2T2 的预期是相对较难的（D1 区分度不高），因此感觉这个分差不多了，大不了再打打 A 性质或者 O(3^n) 就够了。感觉好写的，遂开 T3。

T3 直接会了 O(nq\log^2 n)。然后发现 check() 里面的线段树是不需要的，遂改成 O(nq\log n)。算了一下分数，100+68+35=203，感觉够了。但是不应该小看选手们，因此又想了想。感觉到一个貌似能过一些随机部分的做法，然后感觉有点难写，决定回去把 T2 打完，获得 68 分。顺便想了想 A 性质，发现不会。O(3^n) 做法也有点困难，于是抱着把目前的分数拿到手就行了的想法开始打 T3。在 12:40 获得了 40 分，通过了第 1\sim 7 号点和第 11 号点。然后摆了。

出去听说有 100 个 240？ 然后听说有 620 是送的，选手们实力咋这么强。但是好像队线没这么高的样子。

Day 3

文艺汇演。

金了。