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

A. AquaMoon and Two Arrays

题解

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

代码

Java

Submission #122936684 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #122936879 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. AquaMoon and Stolen String

题解

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

代码

Java

Submission #122939177 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #122939343 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. AquaMoon and Strange Sort

题解

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

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

代码

Java

Submission #122942197 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #122942459 - Codeforces
Codeforces. Programming competitions and contests, programming community

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

Submission #123580528 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #123580894 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论