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

A. A.M. Deviation

题解

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

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

代码

Java

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

C++

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

B. Reverse Sort

题解

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

代码

Java

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

C++

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

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

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

C++

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

D. Treelabeling

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

Codeforces Round #754 Treelabeling 题解 (Java/C++)
题解我们首先考虑什么时候$u\oplus v > \min(u,v)$。不难发现,当且仅当在u和v的最高位一个为0一个为1时$u\oplus v > \min(u,v)$。以下图为例:
点击上面链接查看详细题解

E. Array Equalizer

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

Codeforces Round #754 Array Equalizer 题解 (Java/C++)
题解首先,我们可以自然的注意到,i=1将直接影响所有的数,且最终结果只会受到b[1]-a[1]的影响。
点击上面链接查看详细题解