NOIP 2023 游记

· · 个人记录

前几天在顺着 NOI 大纲去 CF 上补一些弱项知识点的 2000 到 3000 的题或者小清新思维题。虽然我完全没有强项知识点，只能补一些相对更弱的

这次是高中生参赛了，再加上 CSP-S 在玩泥巴，重要性直接拉满了。无所谓，压力大对我可能是比较好的事情。重点是脑子要清醒。

Day -1

不太想去大规模复习板子，就复习个别在会与不会的边缘的就好。

但是不妙的是眼药水要用完了，努力撑到 NOIP 吧。感觉现在眼睛已经弱到不用眼药水就不行了。

Day 0

差不多吃晚饭就停止继续补题了，去看看之前的东西。

十点半左右睡觉。但可能十一点后才睡着。

Day 1

结果一觉醒来已经 7:50 了，急匆匆洗了把脸赶去考场。睡眠质量一般吧。

进考场，解压压缩包，但是为什么我第一次解压只出了大样例没出 pdf 呢，很神奇。

开题，T1 一眼 O(n^2\log_2n) 发现过不了，想了一下发现只用比最小最大位即可，20 分钟左右过大样例。

T2 每次都只动一个位置所以可以暴力修改啊，那最后并查集判一下就好了。但是一开始看错题以为是末状态都相等，改了一下过大样例，现在 60 分钟。

看 T3，本来觉得挺好搞但是细想发现不简单，吸取经验教训先写 35pts 暴力去开 T4。我会把平方暴力二分 RMQ 优化到双 \log，但是一个点都跑不过去写它干啥。

Upd：我来说说这个所谓的暴力是什么玩意。设 f_i 表示第二个序列去匹配第一个序列，最右匹配到哪一位，那么我从第二个序列的 i 走到 i+1 时，若不能直接 f_i 和 i+1 匹配则在 f_i 的基础上往左找到第一个能跟 i+1 匹配的，否则暴力往右不断推进直到无法匹配。这一做法假得离谱，我赛时为什么会看不出来它是假的啊？而且为什么它能过样例啊？

T4 感觉有点眼熟，模拟赛是不是出过类似的？但既然我印象不是很深刻就不乱冲，吸取 CSP T2 的教训。

凭直觉认为 T3 比 T4 好想，于是写了 36pts 的平方暴力去继续想 T3。（写了 O(nm) dp 后什么都没有意识到，鉴定为我太菜了。）

想了一会终于会特殊性质了，只用尽量把匹配位拉低即可。这样就有 70pts 了。

Upd：而我所谓的会特殊性质，是这么个做法，对于第二个序列的 i，不妨设它匹配了第一个序列的 x，那么我走到 i+1 时，由于序列最右侧存在一个最值，那么我只需要考虑最后一个值前面的数都能匹配上。所以如果 i+1 不能匹配直接寄掉，否则观察是否能向后匹配直到匹配到一个比原定匹配点更小的位置，若能则向后匹配，否则不向后匹配。相当于就是一个只保证前面的活下来，把问题扔给最后的最值的策略。我现在还觉得是对的？但是好像也 WA 了。

先不急去检查一下，给 T1 上了个小拍子。不知道怎么检查 T2，于是回去尝试把 T3 的 70pts 做法扩展到通解。

到最后也没有什么重大发现，到虚拟机下测了一下小样例就差不多结束了。

估分 100+100+70+36=306，上天保佑把分都拿到。

我去，回家路上突然发现我好像忘记 T3 可以 ST 表预处理做单 \log 了，这下小丑了。

然后去自测发现 T1 只有 90pts，原因竟是特判 n=1 输出 0！！我真是天才！

看来失策了。这个分真的很差。和其他人的实力差距真的挺大的。

云斗 90+100+70+36=296

洛谷 90+100+100+36=326

小图灵 90+100+90+36=316

小图灵 WA 在 #5#6。

信友队 90+100+60+36=286

云斗 12 个 AK，GD 队线 380，恐怖如斯。

希望 CCF 让我的 T3 得以生存。

洛谷官方数据 90+100+60+36=286，看来还是被打爆了。