社区讨论

防止讨论 ai 与 bi 大小关系的一个小 bonus

P11833[省选联考 2025] 推箱子参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mhjds4fb
此快照首次捕获于
2025/11/04 00:55
4 个月前
此快照最后确认于
2025/11/04 00:55
4 个月前
查看原帖
看了一下题解没有人提到这个而且题解交不了了,讨论区简单说明一下,因为只是一个小点的提示感觉应该不算讨论区题解,如果确实违规请不吝告知.
首先整个序列 aabb 都单调,这可以推得 [ai<bi][a_i < b_i] 不同的两个箱子,移动路径一定互不干扰.具体来说,假如说 ai<bia_i < b_iai+1>bi+1a_{i +1} > b_{i +1},结合 ai<ai+1a_i < a_{i +1}bi<bi+1b_i < b_{i + 1} 是可以推得 ai<bi<bi+1<ai+1a_i < b_i < b_{i +1} < a_{i +1} 的;另一种对称的情况同理.因此整个序列按照 [ai<bi][a_i < b_i] 剖分之后,段与段之间是独立的.
现在考虑 ai>bia_i > b_i 的段落,只要我们将整个段落都镜像反转使得 ai<bia_i < b_i 即可.注意这并不是简单的 swap(a[i], b[i]),我们是将整个段 完全镜像,而不是将这一段中的每个移动路径各自镜像.具体来说,设这一段所有坐标最小值是 LL,最大值是 RR,我们将每个坐标 pL+Rpp \gets L + R - p
这样之后,就可以完全当成特殊性质 C 做了,可以省去很多不必要的分类讨论.

回复

1 条回复,欢迎继续交流。

正在加载回复...