NOIP2024 游记

Day 0 11/29

下午打了以前只写过一次的回滚莫队的模板，然后教练请全机房喝了奶茶，回家之后先玩了会原，舟和新入坑的碧蓝航线。睡前把回滚莫队的另一道模板历史的研究打了，然后把虽然写过很多遍但还是经常写错的平衡树模板给打了，结果一直拖到了 1130，然后还都没用上。

Day 1 11/30

早上 0630 就起床了，由于教练表示连着考 4.5h 会比较累，让我们带上巧克力之类的食物，于是我吃完早饭先去买了条士力架。到了考点学校门口碰见本机房的两个学长，然后就等教练过来，期间没有看到其他同学。不过一个学长的家长告诉我，这个考场不能把士力架带进机房，要吃得出来吃，感觉这样太麻烦了，我打算干脆不吃了。

等教练的时候我顺便去大门口拍了张照发朋友圈，学校的标志在秋季清晨的阳光下熠熠生辉，想起我上个学期还是这个集团的学生，今年年初我还曾在这里参加集团的 OI 冬令营，如今故地重游却已经改换门庭，又想起初学 OI 时的许多朋友都已经退役，颇有几分物是人非的味道，不由得产生一丝感慨。一个月前参加 CSP2024 时，心中虽有感慨，更多的却是对自己可能即将成为退役的一员的担忧。

教练来了之后拍了张合照，说了一些鼓励的话，我们便进入学校了。在机房门口才见到 skella_，没看到其他人。上厕所的路上碰到当年先我们所有人一步进入集团本部的 wdz，因为之前也不是很熟，就简单打了个招呼。看看时间才 0806，但是已经开始排队进场了。考虑到在门口待着也没什么好干的了，不如先进机房去坐着。

0827 公布了密码，压缩包密码是 Forget#2501，pdf 密码是 memory@2107，当时我是尝试记下来的，但是考完试就忘了这回事了，后来翻别人的游记才找出来的，又看了下 GD 迷惑代码大赏，结果发现有人直接写在注释里了，我怎么没想到。

按照往年题目来说，T3 往往比 T4 难，但是 T1 一直都是签到题，所以果断先想 T1。第一反应是：只要统计两个串里面同一段的 01 数量然后比较就可以了。然后就发现两个串的分段是不一样的。又过了十几分钟还没有想法，我已经非常紧张了，连忙去看后面三题，结果发现好像还是 T1 最简单。然后考虑从左到右遍历，对每一位考虑能不能通过交换使得它们产生贡献，发现交换可以产生 1 的贡献，如果不交换最多也只能产生 1 的贡献，所以可以无脑直接交换。然后又发现一个问题，交换了之后遍历到某个位置的值就会改变，于是又设了一个数组，表示本段后面交换了多少个 0/1，每次遇到的时候就取反一下。0907 的时候总算是过了大样例，心里总算是放松了一点，但是一想到 T1 一道签到题居然花了半个多小时，不知道比别人慢了多少。

写完 T1 之后又读了一下后面的题，感觉 T2 确实应该是第二简单的题，T3 看起来很不好做，应该是最难的。至于 T4，简洁的题面背后肯定是一道 DS 题无疑，看了下感觉也打不了多少部分分。于是接下来仍然先做 T2，T2 感觉一眼 DP，但是应该有些性质。从稳定性的角度出发，先在草稿纸上写了 O(nV) 的方程，设 dp_{i,j} 表示第 i 位的限制对的第一个数（下称第 i 位的值）是 j 的方案数，从后往前转移。然后准备先写一下，发现 j 其实是毫无必要的，只需要设 dp_{i,0/1} 表示第 i 位的值是否与可能存在的对第 i 位的限制相等就可以了。于是就写了这种 O(n) 的做法，结果发现过不了第二个大样例，然后发现做法假了，此时大约是 1000，于是我再去看了后面两题，思考了一下后两题的部分分怎么写。

考虑 T4 肯定需要一个高效的 LCA 求法，于是直接考虑用欧拉序来求，然后想了好一会才发现若干个点的 LCA 就是它们中第一次出现在欧拉序中的点和最后一次出现在欧拉序中的点的 LCA，所以就可以得到一个 O(q((r-l+1)-k+1)) 的做法，可以拿到 32pts。然后想出了链的情况的 O(q\log_2^2n) 的做法，但是很麻烦。T3 的做法我只想了一下 k=1 的暴搜，后面写的时候才发现复杂度是错的，不过正确性好像也假了。链的情况倒是很显然，但是只有 4pts。

回到 T2，发现方案数好像只和相邻两个限制有关，然后推了一下性质，得到了一个 O(m\log_2n) 的做法，调了一下过了第二个大样例，但是在第三个大样例挂了，本来我感觉省一没什么问题了，看到这个结果心里咯噔一下，赶紧检查。其实当时第一反应就是漏取模了，但是当时脑子一抽，觉得只要 #define int long long 就可以排除漏取模的问题，然后后面还手动构造了一组数据，其实也无济于事——第二组大样例的强度应该是够的，但是都没在这里出问题。眼看着已经 1200 了，后两题部分分还没写，感觉如果这里出问题的话 T2 会挂到 60pts，后两题再拿个 30\sim40pts 省一应该还是有的。

花了 40min 把后两题部分分写了，T4 链的情况最后没写，感觉太麻烦了。测过大样例，确认了 freopen 没问题，我抱着最后的希望看回 T2，然后在 1250 左右，我惊喜地发现竟然真的有个地方漏取模了，加上之后赶忙测了第三个大样例，顺利地通过了，我甚至还有点怀疑它是不是把输出文件输出到答案文件了。最后测了一次 T1 大样例，本来打算四道题都再测一遍的，可是工作人员已经要求停下了，我只好作罢。

1300 考完出来和 skella_ 聊了一下，然后刚好碰上之前约好要一块吃饭的 zfs，就一块往校门口走。在校门口遇到了以前的同学，也是在上个学期来到本部的 cyw 和 zczy，不过另外三个在本部的旧同学没来，他们说是看到我发的朋友圈乘着下课过来看我的。久别重逢自是有一番喜悦，只是可惜当时忘了拍合照。

中午和 zfs 吃饭，玩了会舟，然后接到教练的电话表示他们就在二楼吃饭，所以就上去聊了一下，听到说 T2 有什么 O(m) 做法，然后一学长笑道：“我看到 T2 的 O(m) 做法，点进去一看，‘先对 c 数组进行排序’。”大家都乐了。

估分 100+100+(4\sim 16)+32=236\sim248。

Day 7 12/06

从学校回来的路上发现我爸发了短信，已经出分了，最后分数是 100+100+4+32=236。本来感觉应该省一稳了，可是一看谷群发现大家都在说什么 ZJ 可能只有 150 个省一之类的话，讨论区也在说什么省一线 200 多。但是后面又看到有人说去除初中生的 ZJ 前 20\% 线是 220，结合 CCF 的通知说各省分数线会向全国线调整，感觉省一的机会还是挺大的。

结语

今年打出这个结果还是比较符合预期的，毕竟我平时的水平摆在那里，主要的问题在于：

1. 很空洞、宽泛、老生常谈地说，性质找得不够准、不够快，耽误了写后面部分分的时间。
2. T2 因为弱智原因调了太久，想到原因了却误判排除方法，浪费了很长时间。

接下来可能要跟 oyoham 和 da17_ 去 BJ 集训，不过接下来就要多花点时间在 whk 上了。

还有就是，看 GD 迷惑代码大赏的时候发现，9 号，Coverain，GD-0170 同学非常不虔诚，一点机神教信徒的修养都没有。不仅质疑万机之神还喊异形的口号，还指望机魂大悦。

\text{神必完整} \text{鸣大钟一次，推动杠杆，启动活塞和泵！} \text{鸣大钟两次，按下按钮，发动引擎，点燃涡轮，注入生命！} \text{鸣大钟三次，齐声歌颂，赞美万机之神！}

赞美万机之神/破碎之神/Omnissiah/Mekhane/WAN

写于 2024/12/8。