游记 - NOIP 2025

天呐。

Day -2

信心赛预期 $100+80+60+40$，T2 挂成 $56$，原来是诡谲做法少了一个 case。结果一看题解，发现 T2 T4 都是奶龙题。T2 就是那种扫描线然后枚举一下转移 DS 存一下就线性了，T4 就是那种二维偏序，然后有唐人认为 tag 不可以放在一起求和，当前做法下限两只 $n$。

Day -1

上午调了点以前没调完的题，中午回家。下午直接睡觉，14:00~18:00，还是被叫醒的。

观看“为什么康熙是洪承畴儿子的假说能引起这么大的反响？”。

00:00 上床睡觉。

Dream

梦见自己参加 NOI D 类，D1 200+，去吃大排档，D2 个位数分数，D3（？）缺考，在外面玩（？）。喜提铜牌中位。

第二段梦是 NOIP 在江苏考，然后乘坐神秘学弟的敞篷车，我就坐在天窗上面，我眼看就要撞到某个树枝，然后车就缩下去了（？）。就把我载到了某个小区，可能是宾馆吧。第二天醒来出去买早餐，要了一个土豆一个蛋，被削皮削成了两个“核”，大概指甲盖大小吧。这时一看表，已经 8:26 了！去宾馆打家长电话，家长在广州（？）炒股（？），没法把我送到考场。然后我就（莫名其妙地）到了考场，找不到入口。我说我的 OI 生涯，这么久以来的努力，就因为这么扯淡的原因全部付之东流了。 在地上打滚，又哭又闹。

On site

2025.11.29.

然后我就惊醒了，6:26。

被神仙考场吓哭了。GDFZ 考场 5。

!noip@nov29.2025:dream。

顺利编写 .vimrc。

T1 好长啊。看一看。好像不会。

T4，果然是数据结构。T3 放棵树，T4 序列 DS，跟去年一样嘛，那肯定大家都 AK 了。这 T4，所有区间……是不是简单题？分治肯定有很多分……什么？25？……拼 subtask？

T3 800？MEX，棋无常树？树形背包搞一搞，三只 $n$ 好像比较简单，应该很多分吧。什么？48？那不倒闭了。不对，我真的会 $O(n^3)$ 吗？……$f(u,i,j)$ 表示 $u$ 子树内 MEX 是 $i$，还剩 $j$ 个数没定。卷。怎么是 $O(n^4)$ 的啊？

T2……好长啊。好难啊。无法刻画。

T1……是不是 $x_i,y_i$ 绑一起就行了……

此时已经过去了 1h 多一点点。

算了先写写 T1。哦要开 long long，要判负数。过样例了。

T2，诶那我通过 $m$ 直接知道最大价值和是多少了，那可能是个绿。怎么样例 1 错完了？哦原来是当前状态下的最大价值和。……这还能刻画吗……

先写 T4 吧。分治复杂度是不是很好啊，感觉有点像 $O(n\log \dfrac{n}{L})$，但是好像还好一点。$L,R$ 跨度大的时候好像就倒闭了，还是只有 $O(nq\log n)$……最后一组样例 10s，跑进 2s 的样例的 subtask 分数总和是 35……

T3 搓一搓，好像可以预先定下来每个点处取子树的空余点位能造成的贡献：是链剖分上子链的 top 到自己的距离，那就变成定一个 $b_u$ 满足 $\sum_{v\in \text{subtree}(u)} b_v\le \text{size}_u$，然后…… $O(n^2m)$？搓一搓……还挺快的嘞。76pts 到手，丢掉。

想起来 T4 分析复杂度的时候其实是对 $R$ 取 $\min$ 的，加一下，马上多过了很多。C 性质不能做？……好像没有很好的做法。不如开目前没获得分数的 T2。

刻画一下形态，必然是某个 2 由于前面提前取了一个 1 被 pass 了，所以枚举一下，2 后面可能取一个 1，两个 case 合并起来就是后缀有一个 $2^k$ 系数。然后前面的条件，感觉像是组合数区间和？

诶怎么样例 2 爆完了？抓一组样例，暴力，调试语句，哎呀我怎么暴力都写挂了，看看都是什么 case，是不是算错了……

怎么只剩 1h 了啊？……但是我也只有 T2 能做了，不是吗。如果打出来 $100+0+x+y$，那高二就真的完蛋了吧。

诶不对，我 for 一下看看是不是我又在乱写组合数了，我怎么想怎么觉得其他的部分应该是对的啊。诶，组合数就是对的？看来是的确是前面的“组合数区间和”错了。

那就是组合数区间卷起来……可以范德蒙德？好像不行？有一个上下界……不管了样例都过了，68 可能是可以冲过去的，丢掉吧。

此时 12:45。$100+68+76+65$。如果不挂分，如果不卡时间，如果没有编译器 bug。

4.5h 的轰隆隆心脏跳动声呢。

交给上天吧。

name.txt。

我想这可能是 4 个奶龙题，但是我有一些很简单的道理没有想清楚。

Aftermath

是的，我有一些很简单的道理没有想清楚。

就是说这个 T2，你知道吗，我在 $a$ 里选几个，$b$ 里选几个，加起来要选 $k$ 个，我们只要枚举一下左边选了几个，就可以加一只 $n$ 了。上下界是手推的，它就是结结实实的范德蒙德卷积，只是我先入为主了（虽说按我那个垃圾写法，改掉也是 $O(n^2\log n)$）。

就是说这个 T4，我们注意到复杂度可以仔细分析到 $O(n\log \dfrac rl)$，可以倍增预处理。

就是说这个 T3，你考虑每个点可以选择对某个连续段做贡献，那当然是选到根的最长连续段啦。然后 $f(i,j)$ 表示定了最长连续段是 $j$，手动拉一下链。

就是说所有人都 $100+100+x+100$ 了。

这场没有打到 $341$ 真是可惜。其实只是我太菜了，一紧张什么都不会了，纯靠肌肉记忆。这个 T4 在赛场上冲不出来完全是情有可原的，但是这个 T2，……

我说我的 OI 生涯，这么久以来的努力，不会就因为这么扯淡的原因全部付之东流了吧。

Day 4

$100+92+76+65=333$。

Never imagined. Right bet. 即使是 GD，似乎也是不错的名次了。

也就是说，不断思考，找寻自己，重视策略，的确是正确的路途。主要还是走了狗运，这次的失误没有严重到把我拉到万劫不复的深渊里。

可是那些战友们，在最后一年如此 NOIP，纵使有一定的必然性，又怎能甘心？……

---

Time is fading away

So much has been lost to date

All of our sacrifice

Our love should suffice in this tribulation, oh

Gravity is pulling me

But I learned how to anchor myself to my feet

With this new-found strength

I will carry your burdens together with you

Yes, our love will come through…

---

There’s many reasons to grieve the past

We must choose to rise above it all

Can you hear me?

Have I finally reached you?

Won’t you believe?

Forgiveness is power, the healing that last

So let this beat in your heart

Forever more…