Codeforces Round #754 ABCDE 题解 (Java/C++)

A. A.M. Deviation

题解

显然调整$a_1$和$a_3$是没有意义的。于是不难发现，每次操作对结果的影响都是3。

因此，只需要考虑初始值除以3的余数。如果余0，则输出0。否则输出1（因为余2时再次减去3，可以得到-1）。

代码

Java

C++

B. Reverse Sort

题解

显然，每一次置换都是将左边的1和右边的0置换。而且这样的置换一定不会出现相互冲突。因此最多只需要一次操作即可。

代码

Java

C++

C. Dominant Character

题解

其实总共只有4类子串可能满足条件：

1. 显然，如果存在两个连续的a，也就是“aa”，那么这个子串一定满足条件。
2. “aba”或“aca”。
3. “abca”或者“acba”。
4. “abbacca”。

我们尝试构造其他做法。
我们从第四种可能着手。我们尝试往“abbaccc”后面增加字母，我们需要增加两个额外的字母a。
显然不能直接添加两个a，因为此时#1是更优的解。
也不能添加aca或者aca。此时#2是更优解。
也不能添加abca或acba。此时#3是更优解。
但添加abba或者acca也不行。因为添加了太多的其他字母。

代码

Java

C++

D. Treelabeling

这个题目的关键在于找出$u\oplus v > \min(u,v)$的条件。

E. Array Equalizer

这个题目的关键在于将未知的b[1]-a[1]作为一个变量，代入其他数，已得到一些列的一元一次表达式。然后根据b[1]-a[1]通过二分搜索分别找出大于0的和小于0的表达式即可。