NOOP 2024 游记

cdx123456 的模拟赛标题为 NOIP 赛拟模。

进场，A 一秒会了 $A=B$，想到了一个构造 $A=B$ 然后调整的做法，感觉很难写且不知道调整的具体方法就弃了。观察特殊性质有一个 $A,B$ 中至多一个 $0$，由此导出了一个能放就放的贪心，写了，过了所有大样例。

读错题了，以为 B 限制的两个端点是随便取的，完全没法做啊，跳了。

C 一看就是管理。

D 要求 LCA 啊，想到了 lxl 的那个区间数 LCA 的题，这玩意是否能支配对搞一下？

感觉 B 放个不可做题有点搞笑，回头看看发现限制是一条链，感觉可以对最右端点取值的集合 dp 啊！$n$ 是 $10^9$，矩阵快速幂一下就能做了，通过了所有大样例。

B 写完的的时候突然发现 D 确实可以支配对，有个三维偏序 $O(n\log^3 n)$ 的做法，发现 $n$ 是 $5\times 10^5$，写这个只有六十多分。支配对个数是 $O(\log n)$ 的，套任何一个 ds 都会死。很不好优化！

上了个厕所清醒了一下，越来越觉得这个支配对个数是线性的。使用广义线段树节点数证明，它确实是线性的！然后那个三维偏序状物好像也可以降维啊。

回到机房后含了个棒棒糖开始狂暴写代码，写了个线段树合并和二维偏序，过了所有样例，前途一片光明。

怎么就剩一个大讨分题了。

发现 C 相邻边建出来图每个点双都是一个完全图，导出了一个换根 dp 做法，是线性的！

吃了个士力架开始狂暴写代码，中间因为 dp 想错挂了好多次。直到比赛结束前 0.5h 还没调出来，丸辣！

写了个 $O(Tn^22^k)$，一下就过样例了，好像一分也没有啊！

最终套了个换根变成了 $O(Tn2^k)$，有 $48$ 分。在比赛结束前三分钟过了前五个样例。

出考场发现没有人过 D。我赢麻了兄弟。

D 题单 $\log$ 死了。大样例在 ys 大学的奇异搞笑巨型土豆电脑上跑了 2.2s 没当回事，结果真被 CCF 卡常了。

题单里见到了 C，20 min 速杀了。

不知道自己考场上究竟在干什么，没想清楚就开写了？？

你已经不止一次因为这个吃亏了，醒醒吧。