NOIP 2024 游记

· · 生活·游记

Day -2

跟着信息组去团建，说是团建其实就是去烈士公园玩。puck 说有一个神秘嘉宾到访，原来是 lzl。主要娱乐活动就是在公园暴走，jzy 买了一个充气锤子，就用它砸 ytxy。

中途在年嘉湖划船，puck 出钱给我们（zbz, yjw, ben, bryce, kcr）租了一个六人火烈鸟，在中途放《See you Again》和《My Heart Will Go On》。

给大家表演 xzy 糟糕的船技！

在飞机上看中国机长，在轮船上听我心永恒，在汽车上玩速度与激情。

然后 lzl 题意一起玩“激情跳跃“（循环版过山车），kcr 既然还能在玩的时候玩 《荒野乱斗》 《匡爷乱斗》，不过到了后面就玩不了了。

下午摆，感冒严重了一些，右手手臂也有些酸痛，赢！

晚上继续摆。

Day -1

上午背诵了 SAM，感觉没什么用？然后看了看 tarjan 系列。其余时间接着摆。

下午看了看之前 xyd 十六连测的题目。

晚上看了看以前写的做题总结。

Day 0

7:40 左右就到了一中门口，问门卫能不能进去，门卫：考试的不能进。md 我就是一中的，早知道穿校服了。

进去以后发现考场就是我以前训练的机房，赢！顺利进入考场后按照黑板上的密码解压考试包，看了看样例数据，感觉有一个 query 看起来是树上查询？但不知道查询什么。

建好文件夹和代码文件，等待题目密码。

8:30 开考，先看 T1，读完题感觉并不简单啊，可怕，然后就去看 T2, T3, T4，T2 T3 都是神秘计数，先天性畏惧，T4 是树上神秘查询，感觉不是很会，不会要爆 0 了吧。

算了，认真看 T1，猜测特殊性质的意图，特殊性质 A 就是啥也不交换，看看特殊性质 B，相当于给字符串分段了，分段了，分段了……

等下，对于整个可交换段，我们可以任意交换顺序，也就是说，我们不难想到贪心策略，如果相同直接跳过，否则找到某一个字符串后合法的一个位置与其交换。发现这玩意应该是对的，因为一个字符最多贡献 1 的答案。写了一下，调了一会儿，过样例了，现在 45 分钟过去了。

T2，T3，T4 中猜测哪道题最简单，感觉看起来应该是 T2，就去看 T2，感觉一眼一个 O(n) dp，设 f(i,0/1) 表示一个点 i 尚未确定 / 已经确定的方案数，用刷表法转移容易。可以拿到 65 分。

我们发现，对于没有赋值的点，转移是一定的，对于已经赋值的点，转移也是一定的，而没有赋值的点是 $O(m)$ 段的。想到一个经典问题：小兔子一次可以跳一步或两步，但有些位置不能到达，求方案数。这个问题我们是分段矩阵乘法，那么这道题应该也可以。 转移矩阵推起来挺简单的，简单写了一下，就过了，现在是 $10:15$。 看 T3，研究了一下题意，感觉要做出这道题先需要研究一下 $k=1$ 的情况，然后剩下的就是容斥了。虽然这个容斥看起来好复杂。 注意到每次我们将选出的边中某一个点当根，那么每次都相当于一棵子树，已经确定了根的一条出边被连，求方案数，注意到根的所有出边是被一条链穿起来的，简单 dp 一下即可。 然后看链，感觉手玩了一下答案应该是 $1$。然后是菊花。 菊花首先有一个显然的公式 $k(n-2)!$，但好像是错的。 想了一会儿，发现可能算重，答案要减去 $\binom{k}{2}(n-3)!$。这样就可以过样例了。 去看 T4，首先由于 LCA 深度不增，将大于等于号改为等于号，$5000$ 直接 $O(n^2)$ 维护区间 LCA，特殊性质 B 换线段树维护即可。 最后罚坐，没有任何进展，知道下考。 下考后问了一圈同学，100 + 100 + 40 + 32 感觉考的还可以？ 但愿别挂。