NOIP 2025 游记

$\operatorname{NOIP}$ 前，校命停课集训二周。旦日晨兴模拟赛，午后补题析疑。赛中数出 USACO 之题，最难者不过蓝题，解之甚易。

$11/29$，赛事设于曹杨二中。吾于 $2023$ 年曾于此角逐。

就座之后，见左右三人，皆校内旧识。所用电脑仍为 Win 7，甚为粗陋。$8:30$ 赛事始，压缩包密码依旧诡谲难测。

首题观数据范围，知前十三测试点乃背包之法。其要旨：每种糖，若重为 $x_i$、值为 $1$，则属 $01$ 背包；若重为 $x_i + y_i$、值为 $2$，则属完全背包。总计 $2 \times n$ 物。后写特殊性质 $A$，预计得分七十。

次题题面繁复，遂急写 $O(n\operatorname{log}n \times 2^n)$ 之法，得二十分。

三题审视一番，暴力之法难成，暂弃之。

四题固是数据结构之题！然思之良久，未得良策。初构线段树，维护各 $len$ 区间之最大值，以 $O(n^2\operatorname{log}n)$ 求各区间答案；后取答案于线段树中，复构第二棵线段树，维护各 $i$ 区间之最大值。每问则以 $O(n\operatorname{log}len)$ 计算。总复杂度为 $O(n(n+q)\operatorname{log}n)$。惜空间不足，仅得五分。

复归三题，先写八分暴力之法，后增些许权宜之计，效率稍提，能否冲至十六分，未可知也。此时已至 $12:50$，检视文件夹结构无误，赛事终了，上前签字。

彼时忽生小波折：提交文件依电脑编号排序，然师未觅得吾之文件夹。吾大惊失色，后遍查之，方知吾电脑文件夹名乃 $\operatorname{IP}$ 地址，非编号也，提交无虞。

估分当在 $103$ 至 $111$ 之间。后三题竟为黑题！$\operatorname{CCF}$ 命题之苛，何至于此！当诘其亲长，何以纵其刁难学子耶？ 徒令吾辈皓首穷经，终难窥其堂奥，可叹哉！

本次赛事得分甚低，若非吾有 皮克敏维基 为精神之柱，吾早已自由落体矣！

末附感言：

吾于贪心之术，素所不娴！昔年 $\operatorname{CSP-S}$ 第二题，末段贪心之法未解，竟堕暴力之途；今岁 $\operatorname{CSP-S}$ 第一题，反悔贪心之妙未察，徒作 $n^3$ 动态规划；$\operatorname{NOIP}$ 首题，贪心之机亦未悟，乃以背包之术应之。