NOIP2024 游记

· · 生活·游记

CSP 316，全省 rk100+，压线去 WC。模拟赛过题都是其他人的子集。感觉省队快没啥希望了。不过考前最后一场模拟赛 AK 了，总算是增加了一点信心。

lzy 也考 NOIP，考前一晚跟他 duel 了 4 把，输了 3 把/ll。果然姜还是老的辣/bx/bx/bx。wzy 也考 NOIP，不过据他说考 2.5h 要去 CMO 查分申诉，但是后面因为一些原因还是考完了整场考试。

进考场，编辑器用的是自己配的 CP Editor。

8:27 开考。T1 看起来不是前几年 NOIP 那种一眼题，在草稿纸上乱画，发现按连续段贪看起来挺对。直接开写，居然写了 100+ 行，还因为变量名写错挂了一遍大样例。拍上大概是 8:55。感觉 T1 是 ARC A 级别的贪心。

T2 一眼计算相邻两个的取值方案再全部乘起来，不过一开始没想清楚，漏了式子中的 \times (v - 1)。感觉 T2 是 ARC B 级别的计数，可能略小于 T1。拍上大概是 9:25。

先看 T3，感觉是神秘题。然后看 T4 发现是 DS，想到去年 NOIP，以为 T4 会 < T3 所以先弃掉 T3。很快想到了一个（我以为是）O((n + q) \log^3) 的 set 启发式合并找连续段然后三维偏序的做法，但是感觉没啥前途可能连 10^5 都过不去，想了好久不会别的做法。这时候 10:10，T3 T4 还一题不会，有点慌。先回去看 T3。

T3 想了一会 k = 1 会了，想了一会菊花会了，想了一会 k = 2 就是直接容斥也会了。发现合法的边集大概一定是形成一条链，直接容斥枚举子集就可以做 O(n 2^k)。发现枚举子集太蠢了，直接树形 DP 就可以了。遂开写，大概 11:00 过了全部大样例，感觉大样例很有强度且自己不会写暴力就没拍。

继续看 T4，2h T4 你能秒我？感觉干想也想不出什么东西，决定先把那个我以为是 \log^3 的做法写了。先写了前半部分的 set 启发式合并，发现连续段个数很少只有 O(n) 个，但是我不会证。不管了，直接赌 CCF 的数据和大样例是同一个 gen，把后半部分的三维偏序写了，大样例只跑 1.3s。大样例看起来比较满就没卡常，拍上后大概是 11:35。

最后坐牢 80min。

出场发现我们学校其他人都没 AK？lzy 会 T4 单 log 但是没写完。群里有人说 T4 支配对是 O(n) 个，那我就是 \log^2 的了。好像后面的三维偏序可以拆成 O(1) 个二维偏序，感觉不是很牛。但是要做 \log 可能前面不能用 set 启发式合并。

回家把代码复现了一下，在云斗和洛谷上全过了，希望在 CCF 那别挂分，别卡我的 set 启发式合并。