NOIP2024 游记

· · 生活·游记

赛前

考前只是打了几场 MX 的模拟赛，随便订了几个题。

并没有专门记板子，因为感觉没必要（实际上确实不需要）。

赛时

八点左右进了考场。

草稿纸发下来以后在上面默写了若干条注意事项。

拿到 down 的解压密码后开始观察大样例。注意到 edit 这题只有两个样例，鉴定为 T1。打开样例准备猜题意，看到了 4 个长为 n 的 01 串，但搞不懂是干啥用的，遂摆。

八点半正式开考，花了 10min 左右时间做了点准备工作，然后开 T1。

注意到直接贪就是对的，随便敲了点代码，15 min 过了大样例。此时是 09:08。

过完 T1 去完整看了遍后三题的题面。T2 是序列上计数；T3 是树上计数还带 k 个关键点，看着就抽象；T4 是树加数据结构。由此大致估计 \text{T}2<\text{T}4<\text{T}3。

开 T2。这个数据范围明显提示了做法与 m 有关，随便推一推发现直接拆成 m+1 段以后每段贡献是相互独立的。记 l 表示这段的长度，中间 m-1 段每段方案数是 v^{2l}-v^{l-1}(v-1)，两侧分别是 v^{2l}，全部乘起来就做完了。实现细节上要 unique 然后特判 ans=0 的情况。

写完代码一测发现 RE 了，二分了一下 RE 位置发现，我写的是预处理 pw[k] 表示 v^k，但是 n 可以达到 10^9 量级所以爆了。直接改成快速幂就过了。此时是 09:52。

还剩约 3h 时间，感觉比较充裕（然而搞到最后时间还是不够用）。

先开 T4，注意到 \ge k 的限制实际上就是 =k，花 20min 时间写了个 3 只 ST 表的暴力，能过 n,q \le 5000 和 k=r-l+1 的部分分，\text{32pts} 到手。此时是 10:22。

然后开始磕性质 A（树是一条链），想了 15min 发现完全不会做，于是回去开 T3。

T3 先考虑 k=1 的情况，发现一个结点相当于将所有与其相连的边在新图上两两连边，而由于是 dfs 树，这个完全图的生成树就必须是条链，简单推出答案是 \prod(e_x-1)!，其中 e_x 是结点 x 的度数。

接下来考虑 k=2 的情况，直接容斥，那么需要减去同时满足两条边限制的方案数，简单推一推发现这个贡献就是将两边之间最短路径上的点的方案数改成 (e_x-2)!，也就是乘上 \frac{1}{e_x-1}，从其中一条边开始跑 dfs 的同时维护贡献就完事了。写完代码过了前四个样例，此时是 11:32。

然后考虑了下 k=3，发现：当三边不在同一条链上时，方案数为 0；当三边在同一条链上时，容斥完的系数是 0。对于 k>3 同理。所以只用算 k \le 2 的情况！

沿用 k=2 的代码花 10min 改写成了一个 O(nk) 的算法，但是一测样例发现 WA 了。

当时觉得自己结论假了，但是重推了一遍发现没问题。又瞎试了几个其它系数，无一例外也是错的。

这时候忽然发现我样例五里只有两组是 WA 的，这时候我意识到我大概是写挂了而不是结论寄了。

仔细查了下代码发现，在 dfs 中，如果碰到关键边应当 continue，而我写了个 return……

改完就过样例五了。此时是 12:42。

写完想了下感觉改成换根 dp 状物就线性了？但此时已经只剩大约 15min 时间了，估摸了一下感觉写不完。

于是随便写了下链和菊花的部分分，加上暴力总共应该是 \text{76pts}。此时是 12:50。

然后检查了下文件名和数组大小就交卷跑路了。

考场估分：100+100+76+32=308。

赛后

出来交流了一下发现大家都说 T4 比 T3 简单是怎么回事呢？可能是我技能点点在计数方面导致的。

考后第二天晚上没花多久就把 T3 正解写完并一发过了。感觉这题如果是放在 CF 上我大概一个半小时内能切，但实际是 OI 比赛所以赛时求稳了，可惜没去冲正解。好在 \text{24pts} 的差距并不算太大。

Upd on 12/06/2024

出分了。没挂分。

考场代码也拿到了，遂根据记录在上文中补上了若干时间点。