专栏文章

题解:AT_arc203_b [ARC203B] Swap If Equal Sum

AT_arc203_b题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miohsyj1
此快照首次捕获于
2025/12/02 19:26
3 个月前
此快照最后确认于
2025/12/02 19:26
3 个月前
查看原文
纯粹的手玩题,不知道为什么能有水色的难度。
本人首先手玩的是 22111100 的情况。
比如说:(1,1,0)(1,1,0) 可以把区间 [1,1][1,1] 和区间 [2,3][2,3] 互换得到 (1,0,1)(1,0,1),再把区间 [1,1][1,1] 和区间 [2,3][2,3] 互换得到 (0,1,1)(0,1,1),就有了所有的情况。
通过更多的手玩,我们发现在有 2\ge 211 时,可以把序列随意交换。
接下来考虑只有 1111 的情况。
[1,0,0,0][1,0,0,0] 是不能进行任何操作的,但是 [0,1,0,0][0,1,0,0] 可以,因为可以把 [1,1][1,1][3,4][3,4] 两段区间交换得到 [0,0,1,0][0,0,1,0],进行以上交换可以把 11 从任意非最左非最右位置交换至任意非最左非最右位置。
时间复杂度线性。

评论

0 条评论,欢迎与作者交流。

正在加载评论...