NOIP2024游记（真）

· · 生活·游记

前情提要：在考场上部分写的所有东西均不保证正确性。因为我吧一些错误的想法也写上去了。

2024.11.27

想打隔膜。

2024.11.28

打个沫。

2024.11.29

上午打个沫，下午去福州打个沫，晚上在福州打个沫。

晚饭有一个酸汤牛蛙挺好吃的，糖醋肉也好吃，剩下的没了。晚饭之后买奶茶，买了一堆吃的进考场。晚上嘎德摸。

2024.11.30

早上起床，没法打个沫了有点不爽，早上吃饭没啥好吃的生气呀，为啥我记得酒店原本有很多好吃的，结果啥都没有是不是我记错了。

接下来去师大附中，路过外国语，被工作人员拦下来说这边才是编程比赛，那边是美术比赛，啊呀。结果外国语是初中部考场，跟我们没关系啦！！！！！！！！！！！！！！！！！！！！！！终于成为高中生了有点爽，也是拿下了这个 NOIp 正式名额了呀。

然后路过一个十几多中学，到达了十多分钟。发现是去年胜选的学校哈哈。竟然是升级的学校？我都没看出来。拍照，发现背后一直显示防治艾滋病的宣传栏，导致排了很久。

进考场发现 307 考场有一半被熊猫驿站市里占领了，还贴心的用别的学校给我们个隔开了，没法抄别人代码很不爽，考前背了一下 flamingblade 的 ip 地址，准备考场上用（结果我并不知道怎么使用）。

下发压缩包，我开始看这个大样例，发现，第一个题 assign，没看懂输入了个啥，作废。第二个题 edit，连续输入了四个 01 串，有点神秘，作废。第三个题 traverse，有一颗树，哇塞，树论，我非常擅长，拿下了呀。第四个题 query，有一棵树，还有 q 次书上询问，哎呀，树论 + ds，哇，全是我非常擅长的，这把真的稳了呀。

发现压缩包里竟然有 pdf 文件，怎么直接把题面下发了？偷偷的打开这个文件，结果发现 pdf 还能射密码，无语死啦。

随机访问这个电脑，发现有一个软件叫 JiJidown，这不是下载 B 站视频的软件吗？打开下载列表，发现有一个秒速五厘米，一个声之形，总大小 3 个 G 多，电脑上还有老哥帮我下动画看，那这把稳了呀还有二次元加成。

剩下的时间全在打小恐龙，打了一个 1505 的高分，开始考试。

先阅览题面，发现！！！！！！！我擅长的那两个题分别是 t3 和 t4，真的稳了呀！！！话是这么说，还得先把前面两个水题做一做的对吧。第一个题 edit，首先 t 上连续 1 可以排序，然后顺着贪能匹配匹配，哎呀一边写过大样例，爽。

然后，第二个题 assign，有点像技术题，那就先推推式子，发现 n\le 10^9，那就对于钦定点之间计算一下，发现两个钦定点相邻好好好做，不相邻，只有成一条链才不合法，所以枚举链在哪断开，就变成 v^k(v-1)\sum_{i=1}^{k+1}v^i，不急先写 O(n) 暴力。两边的特判很好算。

写完了 O(n) 暴力，思考一下怎么优化，我之前见过一个很类似的 \sum_{i=1}^{k}v^i 这个样式的东西，反正都是很多次方求和，那个题是拉格朗日插值法，所以猜测这个题也需要拉格朗日插值法。那么我们先找一找多项式的次数。发现并没有什么数字特别小，给我们当多项式的次数，遂作废。只好推推式子，发现设这个玩意为 F(k)，得到递推式 F(k)=vF(k-1)+v，这个递推式是一个线性递推，可以用矩阵快速幂优化，所以得到 m\log n 的做法，足以通过本题。

第三个题 traverse，一看，dfs，哎呀！我考前看了一道很类似的题，NOI2023 深搜，然而那题我并没有看懂，说明这题我大概率是做不出来了，没关系，可以放掉，因为 NOI2023 深搜是全场最难的题目，我做不出来，别人也做不出来，况且这场的第四题是我特别擅长的题目，应该先做第四题。

第四个题 query，发现需要求区间 LCA 以通过 B 性质，这个问题很困难，所以优先考虑根号算法分块。发现只需要 \sqrt n 次合并区间信息，每次合并区间信息需要求 LCA，复杂度 n\sqrt n\log n，然后预处理块与块之间的 LCA，每个快前缀后缀 LCA，即可 O(n\sqrt n) 求解。接下来我发现只需要区间合并可以用线段树优化，即可做到 O(n\log^2 n)，发现无法再优化，初步猜测这题正解复杂度为 O(n\log^2 n)。

然后考虑 A 性质，发现只需要求区间 \max，非常简单，可以用 ST 表做到 O(n\log n)，不再赘述。

接下来考虑正解，发现答案只需要求 LCA 深度，可以二分。于是我们考虑在线段树上的每个节点维护不同深度 LCA 下的颜色段信息，每个点只需要维护子树大小个信息，复杂度类似猫树，因为是静态，所以无所谓。建树的复杂度是 O(n\log^2 n)，总复杂度是 O(n\log^2 n)。写完了，发现忘记处理颜色段信息了，仔细思考，发现这个做法没法维护颜色段信息。

接下来考虑正解，我们对不同深度建树，一共 n 个线段树，每棵树维护区间最长同色段，这样建树复杂度为 O(n^2\log n)，单次查询 O(\log^2 n)，无法通过。接下来考虑用主席树优化多颗线段树的问题，需要做 n^2 次修改，这样建树复杂度为 O(n^2 \log n)，单次查询 O(\log^2 n)，无法通过。发现有很多信息不用修改，使用 dsu on tree，这样建树复杂度为 O(n\log^2 n)，单次查询 O(\log^2 n)，空间复杂度为 O(n\log^2 n)。

计算一下空间使用，线段树每个节点维护 8 个信息，需要 8 个 int，一共需要 5\times 10^5\times 20^2 个 int，每个 int 占用 4 bit 空间，总空间使用为 500000\times 20\times 20\times 8\times 4\div 8\div 1024\div 1024=762.9394531 MB，可以通过。

尝试使用 cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n"; 语句计算内存消耗，发现怎么开空间，内存消耗均为 500+eps MB，遂放弃。

码代码，中途尝试弃辽多次，未果，还是写完了，重新算内存，发现 10^7 的数组使用空间为 4.768371582MB，非常不符合常理，检查，发现一个 int 使用空间为 4B 而不是 4 bit，重新计算内存，总空间使用为 500000\times 20\times 20\times 8\times 4\div 1024\div 1024=6103.515625 MB，不可以通过。

将数组大小开成 5\times 10^5\times 50，总空间使用为 500000\times 50\times 8\times 4\div 1024\div 1024=762.9394531 MB，又可以通过了。测大样例，发现可以通过，时间消耗为 6s，相信 ccf 机子可以跑过去，预计估分 100 分（个鬼）。发现性质 A 时空消耗均为 n\log n，可以通过（？）。

第三个题 traverse，发现输出 1 可以得分，发现只有一个团可以得分，写出式子 (\frac{n(n-1)}{2}-\frac{(n-k) (n-k-1)}{2})(n-2)!，发现无法通过大样例，静态调试，未果。后来发现未将 n 减去 1，减一，可以通过大样例。

发现 k=1 不需要容斥，输出每个团大小减一的阶乘，可以通过大样例。

然后最后开始打小恐龙，多次没有打到开赛前的 1505 分，觉得是打完比赛 RP 归零了，非常开心，这把又稳了。发现左前方选手 康复中心（昵称）在使用玄学方法（双手合十），遂操控小恐龙在游戏过程中不断磕头，后来打到 2000 多分，发现磕头有效果，说明 RP 还在上升，比赛肯定非常顺利，开心。

然后单手操控小恐龙，并且尝试躲避地上的沙坑，发现打不进 200 分，比赛结束。

出考场发现大家都写了 query 的 n\log^2 n 做法，我想，这么困难的题，所有人都会做，非常不合理，遂猜测正解复杂度为 O(n\log n)，估分 308。

然后发现大家都在哭天喊地，我非常冷静，拿起麦当劳吃了起来，还喝了 H2Q（昵称）的一杯 ice 可乐。

吃完饭，和康复中心（昵称）和上厕所（昵称）讨论问题，发现他们都会 traverse 一题，猜测这道题目是一道 ad-hoc 性问题。发现上厕所（昵称）edit 一题做了很久，猜测这道题目是一道 ad-hoc 性问题。发现自己的 assign 一题做法较为复杂，但是复杂度正确，猜测这道题目是一道较为开放性问题。

离开十多分钟。回熊猫，在动车上打个沫。

晚上和康复中心（昵称），处级领导（昵称），先睡了（昵称），小时一个（昵称），已注册登录（昵称），SAM（昵称）等人吃饭，游戏。

半夜回到家，打开开门吗就来气（昵称），发现群友都在开麦聊天又点神秘，于是在语音里潜水打个沫。

2024.12.01

打个沫。