NOIP 2025 游记

我清楚 NOIP 是高中的主场，对我的作用不大，我也明白我的实力没资格冲击省选，但我还是希望 NOIP 能表现好一些，最终选择了脱产 whk。

模拟赛、补题、板刷。

在模拟赛中能偶尔切切紫，但我始终不清楚我对紫题的定位，到底是多花一些时间去想正解，还是拼暴力，我始终拿不准。

梦到 NOIP 四紫，死磕一整场 T1 爆零，感觉切紫已经成为了我的执念 /ll

考点依旧是 CQBZ，试机，键盘手感还行，机子挺快，随了一道绿练手，20min 过了

这一天，终究还是来了啊，成为了 G2029 倒数第二个到达考场的人。

有几个小登围在一楼看座位表。

lyj：楼上有座位表，去楼上看

小登：我就要在这里看咋滴

lyj：......

进场了，解压缩，看题。

T1 发现又是贪心，10min 会了，思路就是找出 $minn = min_{i = 1}^{n} (x_i + y_i$)，然后 $x_i \le \frac{minn}{2}$ 的优先选择，剩下的直接循环节，10min 打完代码，大样例六过不了，改改调调还是过不了，已经过去 40min 了，有点红温。这时突然发现还有情况没有讨论，冷静分析了一下，剩下钱的可能会买另外的糖果，加上以后还是过不了，然后发现要反悔，一开始 $x_i \le \frac{minn}{2}$ 的最大 $x$ 不一定要选，注意了几个细节，再打打调调过完了大样例，静态查错 5min。T1 共耗时 1h。

T2 发现是数数，一开始读错了题，以为很水，15min 搓完后发现题读错了，重新思考，然后做了 1h 都不会，我一直认为 T2 不过是不可接受的，于是继续想。

好在我前面的思考并不是无效的，我在 11:00 时想到了大概思路，考虑用总方案数 $2^n$ 减去不合法的方案数，显然小 R 的策略出现非最大值的情况时，一定可以通过反悔最后两次 $w_i = 1$ 的选择凑出一个 $2$ 取某个 $w_i = 2$ 的位置，且这个 $w_i = 2$ 的位置一定是没被选的性价比最高的 $2$ 位置。我们设这两个 $w_i = 1$ 的位置分别是 $i,j$，而这个 $w_i = 2$ 的位置是 $k$，那么一对合法的 $i,j,k$ 必须满足 $a_k > a_i + a_j$。我们考虑将 $a$ 从大到小排序，钦定 $i < j$，可以证明按性价比排序后 $i$ 最靠前，$k$ 居中，$j$ 靠后，枚举 $i$ 和 $k$，那么 $j$ 可选的位置一定是这个数组的某个后缀（$j$ 可能不存在，因为性价比排序后整个 $w_i$ 数组的后缀可能都是 $2$），当 $i$ 固定时，$j$ 的可选范围一定随着 $a_k$ 的增大而减小，因此 $j$ 的可选范围具有单调性。同时必须满足性价比排序后 $k$ 前的所有位置（不包括 $k$ 本身）$w_i$ 之和为 $m - 1$，然后就是把整个数组分成三段讨论，推一些组合数，这里不细讲，总复杂度 $O(Tn^2)$。

距离比赛结束还有 2h，我得到了 T2 的做法，我明白这是我最后的机会。

就这样，我 1h 打完了代码，测试第二个大样例时发现错完了，我甚至质疑我做法的正确性，但在 20min 后，我通过了这组 hack。

我开始测试一个又一个大样例，一个又一个找不到差异，我已经有些恍惚了，最后一个大样例在 400ms 内跑完，对比 .out 和 .ans 文件找不到差异。

我的心态在此刻已经崩掉了，我没有意识到 T2 其实并不平凡，剩下 30min 做 T3/T4 几乎拿不到分。

去厕所冷静了下回来，开 T3，不会；开 T4，转化为前缀和形式再预处理出 ST 表，总复杂度 $O(qn^2)$，立刻开打，但在最后 10min 时我放弃了实现。

$100 + 100 + 0 + 0 = 200$，出场前我满脑子都是“今年没去年高”，出场后我才发现 T2 过的人不算多，心态好了很多。

NOIP 聚餐似乎成为了 G2029 的传统文化，可惜的是有一部分人没来，希望下一年的我们，能取得更好的成绩！

$85 + 100 + 0 + 0 =185$，挂了 $15pts$，至少 T2 没挂，这次 NOIP 表现还算可以吧，继续加油！