NOIP 2025 游记

2021CHD · 2025-11-28 14:25:05 · 生活·游记

前情提要：CSP 2025 游记。

Day 1

目标：能拿一等奖，去 APIO。

再度宣传 APIO 2025 游记。

!noip@Nov29,2025:dream，NOIP：2025 年 11 月 29 日，梦想。

:::success[省流]

估分：100+100+48+45=293。

:::

上午直到进考场之前都还在膜拜大佬积攒 RP。

进考场，坐了若干分钟后就开考了。

这次特意强调了一定要建“以考生姓名为文件名的文本文档”，于是一开考就建好了。

我们看到题目：「糖果店」、「清仓甩卖」、「树的价值」、「序列询问」。

先看一遍题，「糖果店」放在第一题，肯定不难。果然在看题的几分钟就已经有了一个看起来没毛病的做法。

「清仓甩卖」看起来有点神秘，数据范围 n\le5000,\sum n\le5\times10^5 好像需要一个小常数的 O(n^2) 做法？由于没什么明显的想法，先跳下一题了。

「树的价值」看起来也有点神秘，居然还限制了树高？这个数据范围盲猜复杂度是 O(nm\log n) 吧。由于没什么明显的想法，先跳下一题了。

「序列询问」一看就是数据结构题，感觉可能复杂度会是 O(nq) 可能还加一些比较小的项。由于没什么明显的想法，先回去想「清仓甩卖」了。

现在还剩四个小时，不慌。

结果「清仓甩卖」卖着卖着给我卖不自信了？感觉完全没有突破口，感觉什么贪心、DP、数据结构什么的好像都扯不上什么关系。

试图从部分分入手，结果发现搞了半天都只是一点一点抠下来的分数，没什么实质性进展。

终于，在我尝试去做出“特殊性质 B”时，我突然意识到，正解似乎和“特殊性质 B”是一个东西，于是按着这个方向想下去似乎正解就出来了？

感觉 T2 做了接近一个小时，这辈子有了。（此时我还没有意识到问题的严重性）

于是马上去做「树的价值」，感觉似乎有一个状态数是 O(n^3) 的 DP，仔细分析一下，发现状态数其实是 O(n^2m)，不过区别好像不大。

然后经过仔细观察，发现这个 DP 等效于 n 个书上背包，所以复杂度是 O(n^3) 的，这里已经有六十分，所以先开下一题。

「序列询问」没啥想法，也没想到任何数据结构可以维护这种东西，于是开始考虑暴力。

首先想的肯定是“特殊性质 A”，这个只要对于一个长度做到线性就好，果然不难，很快就做出来了。

“特殊性质 B”和 O(n^2q) 的暴力也是轻轻松松，但是好像 O(n^2q) 只有五分……

想了一个更快速的暴力，可以做到 O(n^2+nq^2)，大概可以把前四个点冲过去，但是应该也就这么多了。

想了一段时间的“特殊性质 C”发现不会，感觉“特殊性质 D”好像也没啥用，就放弃了。

此时大概还剩两小时四十分钟，开始回去写「糖果店」的代码。

写的过程中发现还有一种情况需要考虑，好在问题不大，顺着写很快就写完了，也是成功通过大样例。

接下来写「清仓甩卖」，直接按照我的想法去写，写完以后果然没有问题，也是成功通过大样例，常数特小，最后一个大样例没开 O2 只跑了 0.3 秒不到。

接下来写「树的价值」，写着写着，我以为我可以把我的做法优化到 O(n^2)，虽然感觉有点奇怪，但也就写下去了。

果不其然，写到一半发现是假的。只能删掉，然后重新写回 O(n^3) 的做法，然后拿到 60 分……48 分？怎么 T3 有 25 个点？？？

还好看错的不是什么关键信息，虽然凭空少了 12 分，但还是决定继续去写「序列询问」。

最后也是不慌不忙把「序列询问」三个档的 45 分都拼起来了，各自的常数也都还能接受，感觉分数也差不多了。

最后还余下十几分钟，按照惯例把四题丢虚拟机跑一遍，都没有问题。于是就这样平凡地结束了。

出场问了一圈，没几个人上 300（当然上 300 的也是有的），感觉这场题好像很难。

预估 T1 黄，T2 上位蓝或下位紫，T3 T4 不确定是上位紫是黑，看情况很可能都是黑。

结果洛谷 T2 给我评到黑了？不过很快就降紫了，这还差不多。

T1 看起来马上就要升绿了，但是不管那么多了。

神说他估分 400，果然神就是神。

然后获得了一个三个月来最长的周末。

我认为我还没有退役，先蹲一下官方成绩。如果不挂分的话一等奖肯定是稳的，感觉 APIO 的机会也很大。（不过没进队的话恐怕就要在 APIO 之前先和 OI 说再见了）

听说 qbf 不会 T3，有点惊讶。这说明今年的题确实很难。

Day 5

出分了。

一分都没挂，和估分完全一致，也是终于在正赛打稳了一次。

这下肯定不会退役了。

由于全站推荐以后改不了，所以后续改题情况放到剪切板里了。