NOIP 2025 游记

Zskioaert1106 · 2025-11-19 18:58:28 · 生活·游记

奖不配才者郁，才不配奖者怍。

前情提要

CSP-S 2025 由于大脑分配不当错失 \sqrt 7，输。

但还是来体验 NOIP 了。

我本没对 NOIP 抱什么希望，不论什么借口，比七级线低几十分就是既定事实。模拟赛确实没做出来过 T1，三值逻辑确实写了几个月，NOIP 2024 确实没能自己独立做出来任何一题，前夕还病了——无所谓，我就去观光一下。

Day 1

早上七点半到达考场，充分熟悉楼层环境，然后坐等开考。

开 T1，看起来挺友好的贪心。咋七个大样例，把 NOIP 快进成 IOI 了。写写写测调调想改测想改测改测想想想写写测调想写测调测调测调测改测调测测测交，通过大样例已经用了恰好 1h。我好菜。

T2 略思无果，于是去把看起来像数据结构 + 扫描线的 T4 暴力写了，在朴素算法和看起来能过特殊性质但是带 \log 的线段树之间选择了严格 n^2 过不了任何特殊性质的 ST 表。

然后回来争 T2 部分分。答案是 2^n 的几种很快搞出来了，开始写复杂度带 2^n 的暴力。写到一半发现自己不会求真正的总和最大，差点直接弃了。还好仔细一想发现是背包，遂求出来。

我的暴力时间复杂度是 O(\sum 2^nn^2)。n \le 10，\sum n \le 5 \times 10^3，T \le 5 \times 10^4，a_i \le 10^9（埋下伏笔），请问我会超时吗？

我考场上当然不管这个。时间大概过半了，我开始写 m=2 的部分分。看起来分不少而且好写，于是我先吃了两个三明治和一片面包。

嗯我们考虑。考虑不会。我认真想了 T2 的几个假做法，顺便想了 T3 的几个假做法，然后想出来了 m=2 的做法。我觉得自己是不会有什么问题的，然后就开始了漫长的样例过不去之旅。

时间来到十二点，没明白哪个环节出了问题的我把 T3 的 O(n^n) 写了，开始用肉眼观察大样例。

在一个小时的庞大试错里，一个最旁枝末节而又最普通不过的尝试让我当场爆炸。

我们都知道，2 \times 10^9 是不会爆 int 的。本题中由于 w_i \in \{1,2\}，为了防止 \dfrac{a_i}{w_i} 带来浮点数运算，我将整个序列乘以了 2，并清楚地知道这不需要开 long long。

然后在许久之后我解不等式的时候，我用了 a_i+a_j \leqslant a_1。