NOIP 2025 游记

前情提要，初二体验。

CSP-S 之后，家中事情颇多，难以兼顾 OI，状态有所下滑。

流感泛滥，不幸中招，高中期中考试。

数学游戏过于困难。

WYZ 高一物理喜获 $99$，满分 $100$，大神呐。

回初中参加滨海研学活动半天，潍坊老传统。

天气非常冷。

上午依旧暂停文化课，在机房看板子，复习了前缀函数等字符串算法。

和同学 CCK 探讨 P7831 [CCO 2021] Travelling Merchant，大有启发，是道好题。

中午上车。由于人数原因，信竞和生竞在同一个班里上文化课，众多生竞同学前来送行，相当壮观。

车上和 GJY 与 ZRL 两位 LCA Project 的大神互相交流题目（埋下伏笔）。

注意到 NOI 2025 Au CXM 和我们一起坐大巴车走，太强了。

车上较 CSP-S 少了很多人且都在睡觉，导致没能抓拍到张力照片。

下午 $\tt14:00$ 左右到达酒店，光顾着喝咖啡以及参观健身房导致错过抢房间绝佳时机，提前一天望穿秋水，$\tt14:40$ 左右终于和 WJT 分到双人间。

感觉和 CSP-S 时的酒店差不多，质量可以。首先打开硬件开始 【数据删除】，因为 ZYZ 前来到访，在建议下开始 VP CF Educational Round，没有切出 E。

约 $\tt16:00$，LXN 让我们下楼拍合照了，在电梯里遇见了 GLRQ 的父亲。

临时借用了某老年活动的会场，背景是西游记。

回房间后发现高一期中成绩出来了，果不其然，我的理科爆掉了，物理只有 $58$ 太难受了，但是英语 $135$？YZH 和 GLRQ 并列班级第 $3$，大神呐。

晚饭是和 ZRL 以及他的母亲一起吃的。

ZXH 带来水果披萨！！！

晚上准备试机，进入山理信息楼发现比想象中的要小，导致人虽然少，仍感到很挤。

对面 GWF，强强。

写了一棵线段树，写了对拍，测了一下 NOI Linux，发现自己并不会在 Linux 中创建能装大样例的文件，在 Windows 下，这叫做“文本文档”。打算试机结束后晚上看看怎么用。

出机房，找到厕所位置，结束所有任务。下一楼和班主任 SRH 谈话，得知自己期中原始分班排 $26$，彻底炸了。

回大巴车时绕了远路，在山理门口合影，照片并没有找到，又因光线不佳，就不发了。

在车上交流，LHX 发现机子上的删除默认永久删除，我竟然不知道，太大意了。

回酒店继续和室友 【数据删除】，洗漱上床，打开电视观看“英超十佳球”，十分激情。

晚上 $\tt10:30$ 难以入睡，让小度播放《两只老虎爱跳舞》关机成功。

早上 $\tt4:30$ 就起了，但是仍然感到 chilling & sleepy，很快再次入睡。

$\tt 6:22$ 被小度叫醒。清醒一下下楼吃饭，面居然是凉的，差评。但是豆腐脑很好吃，豆味醇浓，好评。CCK 作为食神发动技能，经粗略估算，吃下了约 $1.25$ 倍太阳质量的食物。

随大巴车去考场，$\tt 7:55$ 左右坐在了位置上，开始写缺省源。

$\tt 8:30$ 开考了，密码 !noip@29Nov,2025:dream（好像是这个）。

看 $\text{T}1$，感觉是贪心或 DP，$\text{T}2$ 没有什么思路，$\text{T}3$ 单纯树形 DP 显然做不了，$\text{T}4$ 可拿部分分。

开 $\text{T}1$，发现自己 DP 做法是愚蠢的，考虑答案的构成，必然是对于每一个货品，由任意个“两份”和至多一份“单品”组成。发现我们只关心购买数量，这样把所有的“两份”由“两份”最便宜的那个货品贡献，一定是不劣的。因此答案必然可以等价为若干个最便宜的“两份”和至多 $n$ 个“单品”组成。通过枚举选择多少“单品”，佐以排序，可以在 $\mathcal{O}(n\log n)$ 的时间复杂度内解决。代码是简单的，$4 \min$ 写完了，通过所有大样例，这时候是 $7:49$。

开 $\text{T}2$，感觉十分困难，对于性质的逆向刻画相当复杂。遂改从 $\text{T}4$ 骗分，发现线段树 $\mathcal{O}(n^2)-\mathcal{O}(qn^2\log n)$ 是简单的，略施小计，优化到了 $15$ 分（应该）。

倒看 $\text{T}3$，发现树形 DP 没太有前景，应该是 Dsu On Tree 状物，或者神秘小贪心？尝试写写，发现使用 bitset 优化可以 $\mathcal{O}(\frac{n^3\log n}{w})$？现在看来是假的，时间复杂度并不对，但那时并没有意识到，写完发现不仅太慢还过不了样例，遂弃之。

再看 $\text{T}2$，容易发现对于两类，我们会取其中较小的前几个。并且，贪心错误原因，可转化为买了 $1$ 的导致剩下 $1$，此时 $1$ 的没有了或者两个 $1$ 的和起来小于一个 $2$ 的。尝试将两类数字分别除以 $1$ 和 $2$ 后顺序排序，枚举最后是在哪里出错的，貌似是可以组合数的。可惜最后没有拿到能过大样例的实质性做法。遗憾暴力分 $24$。

这时候已经 $\tt 12:00$ 左右，很快写完了 $\text{T}3$ 的暴力，开始后悔自己不会数数，不会各种形式的数数。

最后检查一下就交了，不挂的可能有 $100 + 24 + 8 + 15 = 147$。

出来听说 GWF 考得相当好，CXM 说自己 $\text{T}4$ 只有 $75$，但是大家都觉得他在 fake，实际上早就 AK 了。遇见 HDZ 问他考怎么样，只说：“退役了。”出来遇见初一巨犇 ZRL，看他沉默不语，询问得知 $175$ 左右，还是强。

许多人退役了。

之后 LXN 带我们去吃烧烤，大家相当激动，尤其是管理员整活得出黄黑黑黑后，戏称 $\text{CTS}$ 难度。

观察 ZYZ 神奇吃饭方式。

初中生还是很活跃的。

回到车上，GJY 发现 $\text{T}4$ 是他做过的一道 LCA Project 的原，但卡在 $\text{T}2$ 且对原题的掌握不是很清晰，没有拿分，祝他好运。当初是 ZRL 和他讲的这道序列分治，但是他也没有拿到不平凡分数，实际上只需要简单的把原题开个多测并略加修改就能轻松拿下特殊性质 $\text{ABCDE}$，祝他好运。

回去路上向 GJY 介绍了 B 站上的一个互动视频，他进展得比我快多了，但直到下车都还没有真结局。

和 ZRL 玩 MC，再一次被他的操作折服。

下午 $\tt 16:00$ 左右回到 WFYZ。

结束了。