2025 NOIP 游记

· · 生活·游记

\text{Day -INF}

考前几天模拟赛状态还好，感觉不会重现 \text{S} 惨痛经历。

感觉周围退役氛围挺浓厚的，虽然我还有一年才退役，祝好吧。

\text{Day 0.5}

今年还是挺不一样的，不再是一个人孤军奋战了，也是第一次赛前一天在学校度过。

考前一天晚上 10:30 躺床上，到 50 多才睡着。

不过感觉影响不大，洗了把脸就出宿舍了，去吃了个饭。 到机房休息了会，$07:30$ 在门口集合。 学校离考点挺近的，四分钟到考点，稍微等了一会，见了父母，简单聊几句就进场了。 这次怎么配置这么高，间隔一个机位坐，甚至是有靠背的皮椅，还有超大桌面，再也不用担心演草纸没地方放了。电脑也是 $\text{Win10}$，不过具体啥配置忘记看了。 ## $\text{Day 1} （后面时间点记不清了，等代码公示了补。） 浏览了一遍所有题，发现没有一题是那种能一眼看出算法的，感觉这场不简单的样子。 $\text{A}$ 题看起来跟 $\text{club}$ 很像，于是留了个心眼，发现数据范围是 $10^{18}$，感觉不太可能是 $\text{dp}$。 于是先想贪心，想到了一个贪心思路，写了写。 一下子过了大样例，只有大样例 $6$ 没有过，有误差 $1$，感觉是贪心不够彻底的原因。 按照直觉补了一种贪心，发现还是过不了，索性去写对拍了。 写完对拍，拍出来了好多，然后就一点点调。 最后发现错误的点是在，和最小的糖果不一定买了最多轮，也不一定买了次多轮。于是就发现这个轮数对应一个单峰性，考虑写三分套二分（赛后发现这个二分没必要写，直接 $O(n)$ 也是可以的）。 快速写完了三分，过了大样例 $6$，但是对拍出来了一个 $\text{corner case}$，发现这个单峰性并不严格，稍微手模了一下，又发现单峰性只对于上升阶段不严格，于是稍微改一下判断条件即可。 终于是把 $\text{A}$ 题过了，虽然并不顺利吧，但是至少心态没有乱，没有重蹈覆辙。 去看 $\text{B}$ 题了，先想了大概 $7$ 分钟正解，感觉不太可做，于是考虑 $O(2^n)$ 二进制枚举的暴力，直接跑背包 $\text{dp}$ 求最优解即可，能过掉 $1 \sim 5$ 的点。 但是感觉这个分数不太高，看到了 $A$ 性质，发现答案显然是 $2^n$，白送的 $4\text{pts}$。 之后本来想考虑一下 $m=2$ 的性质的，但想了一会发现没什么进展，于是跳了看 $m=2n-1$ 的性质，发现这个东西答案也是 $2^n$，又是白送分。 既然 $m=2n-1$ 这么轻松，于是就去看 $m=2n-2$ 了，发现这个东西也挺轻松的，分讨即可。 然后又想了一会 $m=2$，发现还是没思路，只剩两个小时了，决定先把后两题暴力打了。 $\text{C}$ 题暴力不太好打的样子，写了个暴力枚举然后树形 $\text{dp}$，只能过 $1,2$ 的点（我也不知道当时为什么没想到用树形 $\text{dp}$ 搞定部分分，可能只想先把暴力写完吧）。 $\text{D}$ 题是我擅长的序列问题，但还是先保底打了个暴力，毕竟是 $\text{D}$ 题。 然后发现 $A$ 性质就是个单调队列，而且 $2,3$ 的点本地也跑挺快的，卡卡常大概率能过，但是没有太大把握，相比于这 $20\text{pts}$，感觉 $\text{B}$ 题的 $m=2$ 的 $20\text{pts}$ 貌似更好拿一点，于是决定去写 $\text{B}$ 了。 事实上就是这样，一开始都挺顺利，搞了一会组合数容斥，写完才发现我构造出了一种完全不可能的情况，好在没有浪费很多时间，感觉脑子有点不清醒，去上了个厕所，正好 $12$ 点整。 回来又推了一遍，发现了正确的情况，正好之前的代码能用上，稍微改了改就过了大样例，本来想先写 $O(n^3)$ 再优化的，但写完发现这个就是 $O(n^2)$ 的，于是就拿到了 $20\text{pts}$，这一刻感觉我赌对了。 但是还是很遗憾没有时间去写 $\text{D}$ 的单调队列了，不然还有望凑到 $200\text{pts}$。 ## $\text{Day 1.5}

下午听说了 \text{A} 题的 O(n) 写法，发现我正好是倒着想的，想麻烦了，不过两种写法都过 \text{luogu} 民间数据了，应该没问题吧。

这场一共打了严格大于 11,060 个字符，燃尽了。

总结

确实在 \text{A} 题有点浪费时间了，本来 5 分钟就想到了贪心，但是硬生生控了我快一个小时。

可能节省一点 \text{A} 题的时间的话，\text{D} 的单调队列大概是能写出来的。

其实这场还是挺幸运的，赛前刚复习的贪心、三分、单调队列都考到了。

遗憾的是码力还是跟不上，\text{B} 题其实还可以拼更多分，\text{CD} 题的树形 \text{dp} 和单调队列也应该写出来的。

不过已经比 \text{S} 的临场状态好多了，算是正常发挥了吧，没有打出什么非平凡分也是正常的。

【番外】