Codeforces Round #896 (Div. 2) ABCDE 题解 (Java/C++)

A. Make It Zero

题解

如果把所有数都一起异或起来。那么对于每一位来说，如果这一位上本来有奇数个1，那么最后所有数在这一位都会是1。否则就都是0。

那么如果n是偶数，最坏的情况也就是第一次把所有数的某一位全部变成1，然后再全部异或依次变成0。

如果n是奇数也是类似的。第一步也是把所有数的某一位都变成1。然后把前n-1个数变成0。接着再把最后两个数全变成1。最后把最后两个数变成0。

代码

Java

C++

B. 2D Traveling

题解

首先，途中经过非主要城市不会得到更优的解，只经过一个主要城市也不会得到更优得解。
所以，除了直接从a城到b城之外，唯一可能的更优解一定是分别找距离a、b两城最近的主要城市。

那枚举这两个主要城市即可。

代码

Java

C++

C. Fill in the Matrix

题解

主要的构造方式自然是每一行错开一位。比如$$
\begin{bmatrix}
0 & 1 & 2 & 3 & 4 \\
4 & 0 & 1 & 2 & 3 \\
3 & 4 & 0 & 1 & 2 \\
2 & 3 & 4 & 0 & 1 \\
1 & 2 & 3 & 4 & 0 \\
\end{bmatrix}
$$

对于m大于n，直接按照上面的方式构造即可。因为列数多于行数，对于大于n的列都是0，所以不需要做出任何调整。

对于m小于等于n。由于上面的构造方式缺少0。所以从m-1行开始，不再进行错位。

代码

Java

C++

D1. Candy Party (Easy Version)

题解

显然，如果平均数不是整数，那么一定无解。

另外，如果$a_i=avg$那么这个$a_i$给出去的和收回来的糖果数目一定相等。
因为每个人都必须要给出一次和收回一次。那恰好就是平均数的人就根本不需要考虑。直接跳过就好。

对于剩下的人，不论是收到还是给出，都是$2^?$个糖果。所以他原有的糖果数距离平均数的二进制一定是若干个1后面跟若干个0。比如111100，或者1111。
因此我们也可以根据他糖果的数的变化，直接确定这个人收到了多少糖果，给出去了多少糖果。

最后，显然，给出去的糖果都应该有其对应的接收者。

代码

Java

C++

D2. Candy Party (Hard Version)

题解

对比Easy version，每个人可以选择不给出糖果或者不收糖果。
那么，对于糖果数恰好等于平均数的还是忽略。

剩下的人，如果差的糖果的二进制里包含的不止一个1，那么他依然是必须要接收糖果的同时给出糖果。有且只有二进制里只包含一个1的，才可能只给或者只收。比如1000可以只给或者只收，但1100就不能。

对于可以选择不交换的人，显然提供了更多的灵活性。
如果这个人恰好需要收$2^x$个糖果，那么他可以选择接受$2^{x+1}$个糖果，并给出$2^x$个糖果。反过来，如果他需要给出$2^x$个糖果也是类似的。
也就是说，这部分人，除了能够按照其需要消化对应的x，也能够在x+1无法消化的时候将其转化为x。

所以相比Easy version，我们要区分硬性和弹性（显然，Easy version中都是硬性的）。那么在从大到小依次处理的时候，如果发现某一个x的硬性的需求或供给无法处理的话，就需要看x-1是否能够补充。
注意：当处理x的时候，如果弹性的需求或供给没有用于x+1的处理，那么也将转化为硬性的需求或供给。

代码

Java

C++

E. Travel Plan

这个题目有点缝合怪的感觉，感觉是把两个经典（或者简单）问题强行合并到了一个题目里面。