游记 - NOIP 2025 | Anchor

hopeful_imitation · 2025-12-03 22:43:50 · 生活·游记

天呐。

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。

[email protected]: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