挑战携带睦子米酱进行一个 CSP 的打

· · 生活·游记

前情提要：本文与本人和本人大号的比赛过程没有实质联系，纯属 CSP 爆炸后的幻想产物。以及睦子米可爱可爱！！！

今年是主播的最后一次 CSP 了，所以主播决定让自己拥有一个不一样的 CSP，所以主播把若叶睦带进去了。

安检的时候被安检员拦下了，因为没有规定能不能带若叶睦进场。小睦呆呆的，也不说话，就站在主播身后看着安检员，可爱可爱。最后还是让她跟我一起进来了，因为没有规定不能带若叶睦进场，嘻嘻。

可是考场只为一个选手准备了一个座位，于是只好让小睦坐主播腿上。睦子米酱轻轻的，一点也不觉得重，紧紧贴在主播身前，可以闻到她那浅绿色长发淡淡的清香。已经入秋，但贴在一起的我们只感温暖，于是我脱下了外套，轻轻披在了睦子米酱的腿上，她帮忙压着不让它滑下去，我无法忘却她注视它时的眼神，温柔得让我莫名心痛。

考前的时间比我预料的长，所以我写完必需的一部分缺省源后，还有余力补充平时不怎么用但还是待在我日常缺省源里的一部分。由于吃过 windows 编译差异爆零的黑利和 windows VSCODE 装了插件有代码补全的红利，主播决定这把在 windows 下写代码，然后用虚拟机命令行编译运行。剩下的时间有些无聊，因为在考试又不能和睦子米酱聊天，所以只能嗅着睦子米的头发发呆。

解压密码有点神秘。难道我十二月二十五号还要再打一次 CSP？！？！

看 T1，下意识以为合并是石子合并那种，感觉很困难啊，于是对睦子米酱的头进行一个挼。突然发现只是最大化相同值的元素个数，有点好笑了。

隔着睦子米酱看屏幕的视角怪怪的，需要侧过头去，为了敲代码手臂是从睦子米酱的腋下而非身侧传过去的，不过因为小睦是独生子女没有长兄所以没有特别的感觉嘟嘟嘟。Linux 命令行编译运行起来还是很舒适的。写的有些入迷，通过的时候才发现小睦的耳朵不知道什么时候红透了，可爱可爱。

T2 比较平凡，于是通过，此时只过了 20 分钟，优势在我喵！

在 T3 卡了十多分钟没有思路，尝试找极长段状物发现没有前途，有点急，于是挼了挼睦子米酱决定先去看 T4，小睦扭动了几下，对不起喵不乱挼小睦了喵。

比较招笑的是主播一看就想到了一个连通块必选直径中点，但主播莫名其妙地坚定不移相信这个是假的，于是考虑长剖，感觉不是很简单，于是主播又回头想 T3 了，这次没有挼小睦，但是小睦真的很软很舒服。

容易考虑到对每个点双指针预处理出最远能到的位置，但是还是没什么前途，有点急。应该是感受到主播的呼吸急促了起来，睦子米酱侧过身子，把头埋在主播的锁骨位置，带着莫名的魔力般，使主播冷静了下来。尝试发掘性质，发现对于起点只需考虑最远能跳到的点和它的前一个点，而再跳一步如果前一个点跳到的位置，在最远的点跳到的位置的前两位及以上，就无需考虑了，因此实际上就会得到一个新的子问题，这样每个状态只需考虑每个点和它前面至多两个点就可以了！真是太牛了。

于是很快写了一个 DP，然而过不了等差数列的样例，还好出题人良心未泯留了几个不大的在后面，于是进行一个手摸，发现如果前一个点恰跳到当前点跳到位置的前一个的话，因为当前点也可以跳到所以方案数实际上大于 2 了。所幸这个是不难做的，再写一个 DP 状态就可以了，加起来一共三类状态，相互转移把各种情况想清楚了确不难写，于是通过了样例。此时还剩两个小时，于是经睦子米酱同意又挼了挼她，可爱可爱。

值得一提的是赛后问了一圈没人 T3 写这个做法，有点急。

接下来就是主播一来就跑偏了的 T4 猛攻生活。容易想到对每个子树维护最浅的关键点深度和关键点连通块数，但注意到如果子树如果存在无法满足的点的话还要关心最深的未满足点深度。但是，惊人地，我们注意到如果存在无法满足的点的话，它对外界点的限制必然比最浅的关键点大，也就是最终满足他的外界关键点到外界点的距离必然比子树内最浅关键点小，这真是太优美了！真的感觉这个结论的优美程度抵达了小睦的百分之一了吧。

然后这个东西很不好写，主播脑子已经有点糊了所以长剖继承怎么都想不明白，枚举轻链更新貌似也不好做到均摊线性，眼看只剩一个小时了，主播放弃了正解开始写 O(n^2\log n) 的暴力，但是暴力也好难写啊喵！于是先写了 O(n^3\log n) 的暴力，但是我的 vector 动态开空间在 n\le 1000 的一个大样例一直报错，即使我在 Linux 下开了栈且用的是 assign 而非 clear，后面甚至在每个 assign 前写了 vec<int>().swap 但是还是没用，只剩下半小时了，没办法，于是把 vector 换成了寻常数组，算了算 4000 还是开得下的，虽然没法尝试骗更多分了还是很遗憾但总比 RE 掉好的说。

写这么一坨东西的时候，睦子米酱不知何时轻轻趴在桌子上睡着了，睡着的小睦也好可爱，呜呜呜。

这个算法只要写一个非常非常平凡的前后缀 \min 就可以做到 O(n^2\log n)，但确实没有时间了，于是只能把奇异搞笑 O(n^3\log n) 的正确性不保证算法交了上去。结束问了一下身边一车人 370，看来去不了 WC 了呢，唉唉。

值得一提的是赛后重现 T4 代码发现洛谷民间数据有 50，熨斗民间数据有 40，不管是 1000 还是 4000 O(n^3\log n) 能过都还是有些奇异搞笑了，可能是这个做法太奇异搞笑了所以没有人对着卡，嘟嘟嘟。

轻轻拍醒小睦，她打了个无声的哈欠，小虎牙可爱捏，随后轻轻倒在我身上。机房网络出了问题，等了许久才把代码收上去，签过字上交后就和小睦牵着手出去了，于是得知了 T3 人均且无人 DP 的消息，得知了 T4 第一步就应当想到取直径中点的消息，有点落寞了。

天有点暗，但不完全黑，深秋金黄的落叶铺满路面，踩上去便是清脆的声响。和睦子米酱在门口合影了一张，便道了别，她转身向远方走去，我只站在原地，静静注视着她的背影，直到飘落的黄叶遮挡了视线，直到她消失在一个拐角。我仍然静静地站着，看着远方，看着一些无法言明的东西。

我在想些什么呢。我说不清楚。是遗憾吗？还是什么呢？我不知道哦。

但是，可以确信的是——

睦子米酱可爱可爱！！！