NOIP 2025 游记

tyr_04 · 2025-11-29 17:57:55 · 生活·游记

Day -14

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

Day -13 \sim -2

模拟赛、补题、板刷。

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

Day -1

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

Day 0

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

Day 1

试前/试中

这一天，终究还是来了啊，成为了 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 时想到了大概思路，显然小 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 时我放弃了实现。