251025 模拟测 总结

挂得很惨，分数就不说了。

Pro.A

这种题目都做不出来，我可以退役了，哇哦！

其实很简单的，想复杂了。

弄一个递归，考虑每种情况——由于这个所谓 \(c\) - 好串是有一侧全是 \(c\) 还有一侧是 \(c+1\) - 好串，可以把左右两侧分别为 \(c\) 的情况各考虑一下，然后递归去处理就行。递归边界 \(l=r\)，看这一位是不是等于 \(c\) 算代价即可。

Pro.B

“少考虑了一种情况”——这话从何说起呢。

考虑最优性。对于第 \(i\) 关，有两种处理方法：

• 用手枪一个一个地打死小怪，用 AWP 打死 boss。
• 用手枪攻击所有怪，或者用一次激光枪，让 boss 血量 \(-1\)，随后被迫移动到第 \(i+1\) 关。

对于被迫移动的情况，又有两种方法！

• 折回来，打第 \(i\) 关的 boss。
• 用手枪攻击所有怪，或者用一次激光枪，让 boss 血量 \(-1\)，随后被迫移动到第 \(i\) 关，然后再用手枪打死第 \(i\) 关的 boss，折回第 \(i+1\) 关，一样用手枪打死 boss，最后移动到第 \(i+2\) 关。

第二种方法确实有点绕啊我呃呃。

然后根据这些移动的信息方法去对应 DP 就可以了，转移式很简单的，注意细节，尤其考虑 \(d\) 的个数处理。

\[dp_{i+1} = \min( dp_i + a_i \times r_1 + r_3 + d , dp_i + \min((a_i+1) \times r_1 , r_2) + r_1 + 3 \times d) \]

\[dp_{i+2} = dp_i + \min((a_i+1) \times r_1 , r_2) + \min((a_{i+1}+1) \times r_1 , r_2) + 2 \times r_1 4 \times d) \]

Pro.C

主播主播，你这个扫描线加树状数组还是太吃操作了！

考虑离线这些操作，按 \(n-y\) 分组存进 vector，然后依次遍历 \(i\)，遍历到了就回答，最后在一次性输出。

考虑用树状数组维护差值次数前缀和，可以根据这个数值判断某个值是否有移出去的希望；每次二分找最小 \(res\) 使 \(res\) 的前缀和值满足条件，然后两次 upd 更新与 \(res\) 相关的具体前缀和值，原理和差分有点相似。然后最后回答就可以了，总的来说是不难的。

重点在于这个 \(res\) 的范围数值求解，也就是这个二分的所谓“满足条件”是什么意思——其实就是要 \(\ge i - a_i\) 啦。

Pro.D

升级版本的欧拉回路，好玩！

其实整个的本质就是在判断是否存在一个欧拉回路。而且这个欧拉回路还必须包含所有要求经过的边。

通过并查集把所有并不强制要求经过的边全部合并起来，还要记录每个点的度数，当然啦，这里的度数只包括要求经过的边！因为这才是欧拉回路的核心基底。

然后要求的不就是把这些点弄成偶数嘛，这还不简单，考虑这个修改的本质过程，两边的奇偶性同时变化，相互消除嘛，但是只有一个节点是奇数度数那就消不动咯，因此只要连边后的这些集合中没有哪个集合只有一个度数为奇数的点就行了，否则相互拼凑总是可以消成功的。