NOIP 2025 游寄

· · 生活·游记

嗯哦哎批 2025 游寄

Day - ？？

上次 csp-s t3 成功骗到 90 pts，所以决定 noip 先打暴力。

Day - ？

无数次 noip 模拟赛爆炸了，不过想必正赛不会这么难吧（后来发现模拟赛其实全是信心赛）。

Day -3～-1

补 cf 1+2 的 I 题，结果和 Cubber 想了三天没想出来。一看题解竟然是爆搜，时间复杂度最坏 2^n 期望 O(1)，大为震撼。于是决定 noip 多写暴力，多打爆搜。最后发现挺有道理的。

Day 1

起得最早的一次，好久没看到升起的太阳了，感觉非常非常美。

上次来南航还是 23 年噗叽组，喜提二等。不过这场嗯哦哎批不会像以前那么菜了

T1

看上去很困难。首先 x，y，x，y 这样取，等价于无限个代价为 x + y，价值为 2 的物品，和单个 x。对于价值为 2 的，既然无限个，直接选代价最小的。价值为 1 的肯定从大到小选。那么答案就是

(m - pre_i) / m * 2 + i

然后 8 分钟过大样例了，没想到 noip t1 这么简单（事后才发现挂了）。

T2

原来预期 T2 是去年 T2 难度，就默认绿题。结果想了一会没思路，这个 T2 怎么这么难。 首先对一种方案，正解是，如果 m 是奇数就让分配 1 的最大值先用掉，然后剩下的分配为 1 的两两配对，排序取最大的。容易证明这个贪心覆盖了所有情况。

那题目里的贪心什么时候会变得愚蠢呢？

很明显是取了两个价值为 1 的（或者后一个甚至取不了了），导致一个价值为 2 的，更优的，选不了了。枚举这三个玩意的位置就行了。

结果挂掉了，调了 1h，死因是取两个 1 之间可能会取其它的 2，但是我禁止了这种情况。写了一个 2^n 的对拍，心态彻底炸掉了。（结果考完发现很多人都爆炸了？）

T3

然后就开始打爆力了，虽然还有 2h，但是前面已经想好先打暴力再打正解（事后发现都是黑，显然不应该想正解）。于是写了个每条边

{sz_u}^2 * {sz_v}^2

转移的暴力。max(mex_u, mex_v) 可以优化掉，变成三方的。不知道有多少分，反正 48 分的链和菊花跑的飞快。

T4

怎么叫 query，怎么又是 ds。 时间复杂度这么高，这怎么打爆力？

然后发现我是唐诗，可以把每种长度分开处理。每种长度单调栈维护，就有 n^2q 的做法了。

考完以后

以为自己爆炸了，结果大家好像都被创死了，甚至过 T2 的都比想象里的少。

然后得知 T1 挂了，由于 c++ 向零取整，哪怕前面是负的，也不会因此扣掉 2。不知道怎么过大样例的。

预期

[0, 100] + [92, 100] + [40, 48] + [5, 15]

之后

和某些超级大佬吃饭，听说 “T3 正常人真不是想一下就过了”，感觉被开除人籍了。

12 月开始要进行文化课大学习了，不知道要学多久。

PS ：我怎么把游记写成题解了