NOIP 2024 游记

迟到的游记 QAQ

（NOIP 之后完全忘了这回事，查分之后看有人发才想起来，然后第一版还没保存丢了。乐。）

Day 0 啥都没干，睡大觉。

不允许携带（非无色透明的）饮料和零食。不懂。

但我不认为不可以携带在矿泉水瓶内的雪碧入场 XD

但我先调了一圈电脑设置（Dev-Cpp 配色，CMD 字体，键盘灵敏度，etc.），实际上是 8:30 才解压。

考场在 Windows 下提供了 Sublime Text, VS Code, Dev-Cpp, Git Bash, GCC 14.3.0，还有 NOI Linux 虚拟机。

好评，跟回家了一样。

神秘贪心（？）

我一开始糊了一个对于每个无限制连续段统一贪心的解。也许是对的，但是有巨量细节，在写 40min 后越写越觉得这不像 A，遂破防。重新开始观察，略加感性地证明出了直接从左到右对于每个位置贪心是正确的。代码实现上直接以 $00\to11\to01\to10$ 的顺序贪心了。大样例过了，扔掉。做了将近 1h。感觉后面时间不大够，放弃对拍。

首先判掉矛盾的一元限制，然后按一元限制把序列分段，反面计数二元限制……没了？

OS: 怎么这个 B 比 A 还简单？我做 A 的时候是不是没睡醒（后来发现 A 确实比 B 难。乐。）

过大样例，不拍扔掉。

手玩了一下，发现貌似只要求每个点的邻边在新树上呈链，且指向根的边是链顶。

于是……答案是 $k\prod_u(deg_u-1)!$ ？

这不对吧？这是 C？

瞪了一会，没发现问题。遂写，果然没过小样例 XD

样例指出了一个重复计数的情况。某点周围的边形成的链其实可以在根在不同子树的时候仍然相同。

于是考虑容斥。对每个关键边的非空子集 $S$，计数有 $f(S)$ 棵树满足从 $S$ 中任一条边出发都有可能搜出这棵树，答案即为 $\sum(-1)^{|S|-1} f(S)$。又可以发现：

于是貌似可以为每个点设计 $O(1)$ 个状态树形 DP 了。

然而这里是游记，不是题解，DP 细节不再赘述。

写了大约半小时，挂在 traverse4.in 的第 $2,3,4,7,8$ 个测试点。不懂。

发现状态设计出问题。流汗。

加了点状态处理某个情况，于是过了。

改完之后貌似 f[u][0] 永远贡献不到答案上。但是它都过了再动它干嘛 XD

$12$ 个大样例，好评。心安理得地不对拍跑路。

首先看到 $\text{dep}_{\text{LCA}^*(l,r)}=\min_{i=l}^{r-1} \text{dep}_{\text{LCA}(i,i+1)}$。于是令 $a_i=\text{dep}_{\text{LCA}(i,i+1)}$，问题转为给定 $a$ 数组，多次询问 $a$ 的某区间内所有（长为 $k$ 的子区间的最小值）的最大值。

（赛后我听说这是 CF484E. Sign on Fence，但是我赛前并未做过。遗憾。）

花了 10min 转成了三维偏序。大概是对于每个 $i$ 求出一个极长的 $[l,r]$ 使得 $i\in[l,r],\min_{j=l}^ra_j=a_i$，然后每次询问分别在 $l,r,r-l$ 上有一个限制，求所有满足限制的 $(l,r,i)$ 中最大的 $a_i$。

看起来可以进行亿点点转化变成若干个二维偏序的并，毕竟限制里面只有两个变量。在尝试了 20min 后没做出来，扔掉，开始写三维偏序。

结束前 30min 艰难完成调试。query4.in 跑了 3.4s？完蛋啦！

貌似是因为我 vector 传来传去太多了。不写数组导致的。

但是这个时候我不可能再去更改代码底层结构了。开始在表层卡常（快读，CDQ 里面剪枝、去重，etc.）。

此时 query4.in 用时 3.0s。彻底完蛋了。

还剩 20min 的时候把 B 性质写了。由于我已经把 $a$ 数组拿到了，$k=r-l+1$ 时就是一个 RMQ 板子。

由于刚才的特判，query4.in 用时增加到 3.3s。流汗。

最后 10min，检查 checker.exe 运行结果，所有题的文件 IO，代码的调试信息是否删去，检查数据范围与代码中的所有数组，上 Linux 编译，通读代码全文。一道题都没时间拍 qwq。

最终估分 $100+100+100+60=360$。

出考场便看到 Otomachi_Una，此人说自己烂完了，在我与另一位同学的追问下，他说自己 C 写的 $O(n\log n)$，D 写的 $O(n\log^2 n)$，在考场机器的运行时间都在时限附近。ak 了还说自己烂，无语了。

DaiRuiChen007 同学在 D 题找到了正确的二维偏序做法，但是没有做出 C。估分 376。

Disjoint_cat 说一直在冲 C，结果没冲出来，D 没时间写暴力。估分 264。为他默哀。

家长说在考点附近找到了一家好吃的牛肉火锅。欣然前往。

我 ak 了？？？这不对吧？？？

此时 Otomachi_Una 在我旁边。他也 ak 了。

我拿到代码后在本机与洛谷进行了测试。本机上 query4.in 运行时间 1.5s，洛谷上最慢测试点不超过 1.7s。Otomachi_Una 的代码在他的机器与洛谷上也跑得飞快。强烈谴责 GDF 的机器。

白写性质 B 了。愤怒。

Daniel_lele 说如果他的最终得分比估分 (352) 高就在 CTT 与群友【数据删除】。他的得分是 396。于是他在 CTT Day2 的晚上与 Graygoo 进行了【数据删除】。本人当时在旁边，Otomachi_Una 与另几位同学拍了照。此事在《轻舟已过万重山，NOIP2024 和 CTT2024 郑煦翔家长群领跑全国！》 一文中亦有记载。

同校的同学中有一位打错了文件名，有一位由于 lambda 表达式返回类型推导不正确在 NOI Linux 上 CE 了。好惨。

谦虚谨慎，砥砺前行。