[ARC203B] Swap If Equal Sum 题解

首先，必要条件是两个序列的和相同。

容易发现，操作是可逆的。所以考虑将 和 变为一种相对规则的形式，比如单调。由于单调不降与单调递增是对称的，所以接下来讨论单调不降。

现在的问题是，能否将一个序列通过若干次操作变为单调不降的。考虑简化操作，变成：

• 交换 0 与 0 0
• （或）交换 0 1 与 1
• （或）交换 1 0 与 1

注意到，当序列之和（即 的数量） 时，我们一定可以把所有的 放在序列开头处，从而形成单调不降的序列。具体过程可以手模一下，这里不再展开。

另外，当序列之和 时显然有解。所以接下来单独讨论序列之和 的情况。即此时序列中有且仅有一个 。

根据 的位置分类讨论。发现，当 的位置 时，我们可以通过一些操作将它放置到区间 中的任意一个位置；当 的位置是 或 时，那么我们无法改变它的位置。也就是说，当 或 中的 在位置 或 时，当且仅当两个序列相等时才有解；其它情况下均有解。

代码是好写的，所以这里就不放了。