====== 牛客多校4 ======
^ 比赛时间  ^        比赛名称                       ^ 赛中过题 ^   总计过题   ^   题目总数   ^   罚时   ^   Dirt   ^   校内排名   ^
| 25.07.24 |        [[20250724|牛客多校4]]         |    3     |   8    |   13    |   502   |    2/5   |  11/18  |
===== 赛时 =====
==== F 00:26 +0 ====

Ender_hz: 签到题，把挪动的代价与原本的价值合并后排序即可。
==== B 02:49 +0 ====

_istina_: 判断会不会因为视野问题进入死胡同。先 BFS 找出所有能到的位置，再倒着处理出所有位置能到达的最远处。Meowscore 思路构建，_istina_ 最终攻克。总体上是简单题，感觉开晚了。
==== I 04:27 +2 ====

Ender_hz: 朴素的 BFS，罚时一发是因为箱子传递的时候只考虑了 ''!'' 而未考虑 ''@''，另一发是因为没有看清输出格式要先输出步数，准备写 check 的时候才看到（
===== 赛后 =====


==== D（_istina_ 补） ====

_istina_: 构造指定值的行列式。还是想象力不足+线代没学好。该把这个二进制分解解法记住了。=)

==== E（没补） ====

_istina_: 分析性质+树剖。技能树点的不够全面。赛时甚至没有信心开这题。
==== G（Meowscore 补） ====

_istina_: 赛时发现了一些结论，比如删去的部分只能是一段左括号加一段右括号。但没能推进得出最终的解法。可能需要多做一些括号序列题积累一下认识了。。
==== K（Ender_hz 补） ====

Ender_hz: 有一点 hash collision 的思想，总之就是进行 $\lfloor\sqrt{1000}\rfloor + 1$ 次模 $\sqrt{10^{18}}$ 的生日悖论草过去，记得最后输出的时候对 $\lfloor\sqrt{1000}\rfloor^2+1\sim 1000$ 项的答案输出 $0$。
==== L（Ender_hz 补） ====

Ender_hz: 赛时思路太局限了，只想着拆分 $\lfloor\cdot+\cdot\rfloor$ 用前缀和，没想到倍增。

思路是 $x$ 在 $\lceil\log V\rceil = 30$（$V$ 为值域）次操作后贡献最多为 $1$，利用这个性质做倍增，离线预处理时间复杂度 $\mathcal O\left(\dfrac{n}{\log V}\log^2 V+\dfrac{n}{\log V}\log n\right)=\mathcal O(n\log V)$，单次询问时间复杂度 $\mathcal O(\log n+\log V)$，注意最后答案其实就是终值 $-$ 初值。
==== M（Ender_hz 补） ====

Ender_hz: 赛时没有注意到题解里的性质 '';w;''

这个题的重点是搜索的状态设计，注意到一个状态在进行两个数取平均、排序、每个元素减掉最小值后的状态一定前序于原来的状态，所以只要保证升序枚举，就可以记忆化后直接转移。

$12\rm{s}$ 的时限牛客的少爷机可以轻松草过去。
===== 总结 =====

Ender_hz: 坐牢的一场，**提交前记得观察输出格式**。

_istina_: 牢完了，签完到之后几乎就一直无所事事。G 题搓出来一个假结论验来验去，D 题更是一点正解的边没摸到。m(

MeowScore: