2025 NOIP 游记

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

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

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

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

$06:30$ 起床铃打了才起，半夜醒了很多次，怎么到正赛睡眠就不太好了。

不过感觉影响不大，洗了把脸就出宿舍了，去吃了个饭。

到机房休息了会，$07:30$ 在门口集合。

学校离考点挺近的，四分钟到考点，稍微等了一会，见了父母，简单聊几句就进场了。

这次怎么配置这么高，间隔一个机位坐，甚至是有靠背的皮椅，还有超大桌面，再也不用担心演草纸没地方放了。电脑也是 $\text{Win10}$，不过具体啥配置忘记看了。

$08:27$ 就拿到 $\text{pdf}$ 了，貌似是公布早了，我看别人都不知道密码已经公布了。

（后面时间点记不清了，等代码公示了补。）

浏览了一遍所有题，发现没有一题是那种能一眼看出算法的，感觉这场不简单的样子。

$\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{A}$ 题的 $O(n)$ 写法，发现我正好是倒着想的，想麻烦了，不过两种写法都过 $\text{luogu}$ 民间数据了，应该没问题吧。

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

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

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

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

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

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

【番外】