NOIP 2024游记
yuntianshen · · 生活·游记
我是蒟蒻，第一次参加NOIP有什么需要注意的吗？
Day-1
打了一场板子赛。差两道题 ak 遗憾离场。 晚上10：00回家，收拾了下包，发现只需要带手机和衣服就行了（？） 早早睡觉，不能像 CSP 前夕那样了（前情提要：CSP 前夕熬夜玩电脑被父母抓了，再次提醒后人不要模仿）
Day0
早上8点来到学校，非常兴奋啊，看了点板子，觉得自己至少肯定能切一道题，中午提前去食堂吃顿大餐，坐校车去火车站，上车玩了一个小时手机，睡了一个小时到了，坐地铁去华科，转校内巴士去酒店，3点到武汉差不多5点30才入住酒店。休息了一会儿下楼吃饭，出去在校园内逛了逛，买了点饮料回酒店打了三个小时音游，把主线所有有 AT 难度的曲子都开了，然后清了 BA 日常，舒舒服服洗个澡，10：34 睡觉。
Day1
早6：10起床，收拾行李，吃早饭赶往考场，进考场之前一直在看树剖 LCA 模板（），正常进场，开题。
T1 仔细读题，好似是一个贪心！想到把无法交换的数字两边放上分割线隔成多个区间，显然连续的可交换数字构成的区间是可以任意排的，而且对于两个区间，肯定是调整较长的去适配较短的，因为无论较短的怎么调整，其产生的贡献都不可能逾越它本身0和1的数量限制。那么我们从前往后遍历区间，每次从两个串中取当前最靠前的区间，用较长的去适配较短的，把较长的已经用于适配的部分切掉（更新长度以及0与1的数量），把剩下的部分继续向后匹配即可。问题是，预处理过程和匹配过程要考虑的情况太多了，这导致我对自己的想法不自信， 所以只写了两个特殊性质。赛后问了同队 dalao ，我的思路竟然是对的！后悔晚了。
打完特殊性质时间：9：20
T2 一看就很麻烦，先跳过吧（）；
T3 倒是读懂了题目，对原图每个边建一个新点，有相同邻接点的边产生的新点之间建无向边，问最终能产生多少种生成树，可是我不会写啊（）；
T4 啊？我押对了？考前 40 min 一直在看的 LCA 竟然真的考了？？？仔细读题，题目是要我求区间内大于等于 k 的子区间的 LCA 中深度最大的一个。一开始糊了个暴力，枚举区间长度，枚举起点，枚举每一位，显然既复杂又错误。再仔细研读样例解释，欸，他每一次比较都选择长度刚好为 k 的区间啊，为啥？突然发现在一次询问中如果我们只考虑长度为 k 的区间一定是不劣的，因为多考虑一个点就有可能导致 LCA 向上挪动，深度就变小了！所以直接考虑每个长度为 k 的子区间就行了！我很高兴的用 15 分钟甩了一个树剖 LCA 模板上去，然后发现如果利用多个点最浅 LCA 覆盖的特性去找时间复杂度仍然爆表。但是已经没时间了，暴力糊上去加特殊性质拿20分吧！
最后一道题都没切，40 + 0 + 4 + 20 = 64 / 400遗憾离场。
赛后反思
赛后出来问了 @xxseven 大佬关于 T1 的思路，发现我是对的，但是我想不到实现的方法所以以为错了，后悔莫及啊！下次有这种情况我一定直接先把思路对应代码敲出来，不要理所当然对或者不对，让数据说话！这里也警示后人，不要因为解法看上去难实现就放弃，相信自己，先写了再说，说不定就过了大样例呢！
T2 最后读了题，还是没怎么懂，只能想到约束成链，在某个地方不成立的情况是不合法的，其他的都没想到。
T3 比较好理解，但是我是真的想不出来，赛后再学习解法吧。
T4 其实是非常可惜的，赛后我在搜索相似题目的时候才知道区间 LCA 有一个结论是区间内总的 LCA 求出来是等价于区间内 DFS 序最大的点和最小的点的 LCA 的。要是我之前就学习了这个结论和 DFS 序求 LCA 的方法，一切会不会不一样呢？听说有的 dalao 还用线段树合并写了这道题。
NOIP 2024，yuntianshen得分40 + 0 + 4 + 20 = 64，遗憾离场。
明年打完我也就该退役了，我这 OI 生涯真是短啊！ 加把劲，明年再战，争取省队吧。