First, and Last —— NOIP 2024 游记

· · 生活·游记

NOIP2024 游记

过去几年参加 NOI 这类的比赛，看到正式题目总是会有一种庄重感 —— 因为平日里那些再普通不过的训练和模拟赛，转眼间就变成了正式的，决定命运的比赛。efz 机房作为考场也会给我类似的感觉。

只不过这次回来就不再如此了。现在的我只是觉得，在经历过 OI 的那么多风浪之后，一个老练的税收重新返回故乡的小河，一切都会显得那么平静。而我仿佛也置身于考场焦灼的气氛之外，虽说时间和空间上和大家同处，但却又有种疏远感。

拿到考题的我做了一个决定，去用一些之前没用过的策略和方法。我在正赛中从来没有忽略过部分分，从来不会不打暴力和对拍。不过这次既是最后一次 OI 赛制的正赛，那不妨便尝试地有趣一些。若是因此而挂分没有 400 的话，那也算是给我的旅程添上了一个滑稽的小尾巴。

我先看了看 T1 和 T2。T1 看到题就想了一个贪心，但是感觉贪心的证明并不显然。然后再看了眼 T2，发现比 T1 更简单。于是我就开始写 T1 了。我很快地写完了代码，但是却无法通过大样例 —— 我开始怀疑贪心的正确性。10 分钟后，我发现我将所有数组的类型都开成了 char，也确实幽默了。T2 倒是没什么小插曲。

也是在这个时间节点，我突然冒出了前文所叙的感受。我顿时感受到，就为了这些瞬间的情绪，或许从北京到上海的来回也是值得了。

然后是 T3。拿到 T3 的我其实没什么头绪，但是简单思考了一下 k=1 就发现了答案是 \prod (\deg-1)!，然后想了一下 k 大就可以直接容斥。那正解也大概就是把这个容斥改成 DP 了。我迅速写了一个 2^k 的暴力验证结论正确性，然后开始编 DP。可能是因为有些生疏了吧，DP 的一些细节写错了很多地方，也是浪费了挺多时间。不过从我想到如何 2^kn 的时候我已经确信这题能够通过了。只不过留给 T4 的时间就只有 110 分钟了。

T4 在我拿到题的时候我就看了眼，就大概会了一个双 log 的做法。但是当我真正开始想的时候发现我的做法问题确实有些多，并且双 log 也肯定过不了。我此时想到了我 NOI D2T2 时 —— 因为确实这两题有一定的相似之处，都是树上启发式合并一类的东西（虽说我最后也没用到启发式合并）。然后我就花了半个多小时的时间去编新的做法。我发现对于链，建出笛卡尔树之后，只需要先在笛卡尔树上从两个端点往上倍增，然后最后再离线用线段树处理区间包含的情况就可以了。然后我觉得树只需要套一个启发式合并就行了，直到我写了代码发现启发式合并我要两个 log。我又想了一会儿，编了一个我从来没见过的在树上做区间分裂的做法，然后在剩下的一个小时内编写 + 调试通过，应该总共一百五十行吧。最后还剩十分钟，也是有些心惊胆战了。

我通过所有样例的刹那，也是重新回到了去年那时的激动。当时也差不多是这个时候样例全部通过的。

比赛结束后，一如既往地响起了各种地讨论。坐在我旁边地是一些 sfls 的初中选手 —— 应该和四五年前的我差不多吧。有发挥失常的，有两三百分的。作为一个看客的我，虽说也想和他们一起说上一句，但或许也是这层疏远感告诉我我不应该多嘴。

因为我也只是悄悄回到了四五年前的我的身旁罢了。

于是对着那时的我，我又重新悄声道

坚持下来了呢，到最后。

简要题解

注：上文最后一句话引用自 LoveLive μ's 第二季最终话，穗乃果面对曾经的天台说的话。我觉得意境十分相像。

T1

设两个字符串分别为 s,t，交换位置限制字符串为 p 和 q。从前往后贪心，考虑用四个 set 维护每个字符串的 0/1 的位置集合。然后扫的时候，如果 s_i\neq t_i 就考虑把 s 后面可以换过来的给换过来，s 不行就换 t，t 不行就不管了。

证明略。考虑按照题目给定的 p,q 分段后就可以感性证明。

T2

式子懒得算了。大水题，注意到相邻两个限制之间基本怎么填写都合法，不合法的情况只有从左侧一直不断往后限制直到最后边，随便列个式子就好了。

T3

考虑 k=1 时答案是 \prod (\deg -1)!，原理是考虑以钦定的根为根，那么每个节点的周围都可以随便重排。然后考虑容斥，即一种连边方案对于多个根都成立。一个根实际上限制的条件是一个 "定向"，即一定从一边进来，另一侧出去。所以可以感性地明白对于一个点，如果其有 1 个方向有钦定的根那么贡献就是 (\deg -1)!，两个方向有根就是 (\deg -2)!，三个就不合法。于是 DP 一下就可以了。

T4

首先考虑链的情况。建立笛卡尔树后，可以发现：对于问询 l,r,k，我们只需要先从 l 往上倍增到一个笛卡尔树上区间 [x,y] 使得 y-l+1\ge k 来更新答案；然后再从 r 往上倍增到区间 [x,y] 使得 r-x+1\ge k 来更新答案；然后再处理被 [l,r] 包含的长度 \ge k 的区间，那么这个可以离线，然后 k 从大到小扫，然后用线段树维护。然后考虑树的情况，考虑也建出这样一棵辅助区间树，区间 [x,y] 的儿子 [x',y'] 满足极大且 lca[x,y]\neq lca[x',y']（这玩意儿其实就是启发式合并的时候的极长连续段，所有极长连续段最后形成的区间树）。那么求辅助树就直接递归，每次二分当前节点的右端点即可。