Codeforces Round #732 ABCD 题解 (Java/C++)

A. AquaMoon and Two Arrays

题解

模拟即可。每次找到一对i，j使得a[i]>b[i],a[j]<b[j]，对这个i，j进行操作即可。

代码

Java

C++

B. AquaMoon and Stolen String

题解

模拟即可。从左往右依次扫描，看看每次哪个字母没有出现过即可。

代码

Java

C++

C. AquaMoon and Strange Sort

题解

如果一个数需要移动，那么为了最终方向不变，显然需要移动偶数次。因此最终的方向只取决于初始位置和目标位置的奇偶性。
同时显然，如果不考虑方向，只需要从左往右依次归为即可。

所以，我们只需要统计初始状态的奇偶性和排序后的奇偶性。只要前后奇偶性相同即可。

代码

Java

C++

D. AquaMoon and Chess

题解

首先我们可以注意到，任意一对连续的两个1，经过若干次操作，一定可以到达任意位置。比如01100100，一定可以做到00010011。
我们可以注意到虽然两个连续的1可以到达任意的位置，但那个孤立的1的位置会受到影响。

如果只存在一对连续的两个1，那么其实独立的1的位置完全取决于那一对1的位置。
现在，我们考虑存在两对连续的两个1。比如01100100110。我们会发现其实独立的1的位置仍然取决于这些连续的1的最终位置，比如00001011110。

因此问题就转化为，将这些一对对的1，插入各处有多少可能。
比如01100100，我们首先排除不影响结果的孤立的1，于是我们得到0110000。接着，0肯定是一个可以插入的位置，11也是一个可以插入的位置，所以这个例子中，我们总共有6个坑（其中5个0，和1对1）。我们要往里放1对1，于是结果就是$C_6^1$。

代码

Java

C++