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

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

C++

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

B. 2D Traveling

题解

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

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

代码

Java

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

C++

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

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

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

C++

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

D1. Candy Party (Easy Version)

题解

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

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

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

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

代码

Java

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

C++

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

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

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

C++

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

E. Travel Plan

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

Codeforces Round #896 Travel Plan 题解 (Java/C++)
题解为了方便说明,先定义几个函数和变量:$len(i,j)$表示从$i$到$j$整个路径上所经过的节点数。比如样例1中,$len(2,3)=3$, $len(1,2)=1$。