NOIP2025 游记

· · 生活·游记

来写个正经游记，不知道去不去省选，不知道这是不是最后一篇游记。

Day -1

被拉去停了一天课。效率很低。上午一直在犯唐，下午和晚上把两个把我创死的题给补了。怎么都这么唐！生气了。

下午的时候久违地去踢球了。突然发现我变得很会盘带了！但是脚腕扭来扭去的酸死了。最后 1min 进了个蝎子摆尾。谁给我刷的不定形射门？

离开机房之后就去 冰 了。荒野活动3v3总是能遇到神人，一些要配合的角色直接难受得跟吃了一大坨一样，好不容易拿迪克几乎c了一把又被神人队友搞崩了。就在刚刚开了一把本来稳赢的队友开始挂机。破防。

不管了。然后睡前重温了一下 Reina。然后：

我说得胜已成定局。

Day 1

没睡好，于是醒得很早。最近开始喝咖啡了。雀巢是对的。

进考场还是感觉有点小困，有点迟钝。

我的习惯一直是给 solve 函数改名。这次分别叫 Sana Shinku Reina Shizuku。

T1 想了一会儿才想到只有一个取 \ge 2 个。写了写就过样例了。

由于我一直的目标就是苟个省一，于是觉得目标已经达成一般了，做出了 T2 滚去打暴力就是胜利。此时我还不知道事情的严重性。

幸运的是，等我知道事情的严重性已经是结束比赛之后的事了。

先读懂了题，然后去想办法用一个简单方式表示一组 w 能不能取到上界。发现这个贪心是很优的，只有在最后剩下一块钱取 w=2 的时候是有问题的，这个时候回去前后各一个 w=1 的，那就是要看有多少情况替换掉会比较优。

那这一共就三个位置，枚举其中两个，想了想觉得枚举 w=2 和前一个 w=1 的比较好做。然后再对剩下不同价值的东西计算方案。发现大概分成四块。最大的可能对对前面消耗的钱有 1/2 的贡献，然后有一块有 0/1 的贡献，再后一块只能取 w=2，最后一段没影响随便取。前面 1/2 一定有 1，直接减掉，发现变成了组合数，后面找到对应的位置算一下就行。

然后细节上有一点问题，这个时候也不算非常清醒。调了一会儿，大概在 1h 45min 的时候过了。

去上了个厕所，发现呆 gen 还在 T2。感觉还不错。并没有意识到 T2 会卡掉大部分人。然后花十几分钟拍了一下，没问题。

然后怀着打暴力的心情去做 T3 T4。T3 看了眼觉得这个题挺适合我的，想了想，结果无意中翻到 T4。题面这么简洁，还是数据结构，部分分肯定好搞。于是想了想，发现回了 40pts。先不急，再想了想 T3，一时半会没想到 n^4，于是先打了 T4 40pts。

然后去想 T3。本来想的是 dp_{u,i,j,k} 表示 u 子树内 mex=i，不贡献给 mex 的组成 [j,k] 区间的方案数。想了好一会儿发现记这个 [j,k] 很蠢，只用记个数，变成 dp_{u,i,j}，前缀 \max 优化转移就是树形背包的 O(n^3) 了。这我还说啥了，直接开写呗。写了一会儿过了样例。爽上厕所。

然后再去想 m=2。必须要和深度有关。然后发现深度不大的时候不贡献给 mex 的不会很多，大概就是 O(m) 或者 O(m^2)？开写，发现空间炸了，于是用上了之前想过的树形 dp 按深度滚动数组的方法。很有效！但是常数大到要命，似乎只能过 m=2 了。

中途又去上了个厕所。止步于此，三次。发现呆 gen 还在 T2，意识到事情不对劲了。

最后 15min 发现我会 T4 C（其实一开始就有点会了），犹豫了一下还是写不动了。开摆。结果突然文思泉涌了。乐。

出来交流。yhd 和 zlt 有不太确定的三题。hla 好像炸了，默哀。msk 考的还挺好，gen 和 emo 都没过 T2。

给 ccf 白捐款了！

学弟们发挥一般啊，不管了。想到什么再写吧。总之最后是 100+100+[48,56]+40=[288,296]，别挂就赢。

后续的话，等出成绩吧，是这个分就去考个省选玩玩。之前的几次经验来看我和省选（day1）相性很好,万一对上脑电波了呢？但是由于心态原因，还是不太可能停课集训的。顺其自然吧。

Day ?