Codeforces Round #743(Div. 2) ABCD 题解 (Java/C++)

A. Countdown

题解

显然，我们会把每一个非零的数置换到个位然后减掉。因此除了个位本身，其他位只要不是0，那么就除了这个数被减掉所需的操作之外，外加一个置换操作即可。

代码

Java

C++

B. Swaps

题解

显然，我们只需要关注第一位即可。于是我们根据数组b从小到大依次尝试，每次尝试选择代价最小的a使得a<b。

同时，我们注意到，随着b的每次增长，a其实可以选择的数也只会多一个。于是我们只需维护一个所有a的最小开销，当有个新的a时，更新最小开销即可。

代码

Java

C++

C. Book

题解

显然，这是一个经典的拓扑排序问题，但是有一点点变化。算是经典应用。

因为读书是顺序读，不能倒回去。因此当我们发现某一章（记为x）的入度为0，进而根据其出边去更新其他章节（记为y）的入度时，如果发现这一章（y）在当前章（x）前面，那么这一章无论如何一定需要再读一次。
于是我们将队列分成两个：
一个是只存储可以在这次阅读中理解的章节；
一个存储虽然入度为0，但是由于上面的情景，不能在当前阅读中理解的章节。

很自然的，第一个队列都处理完后，我们再处理第二个队列即可，此时第二种队列的就变成了第一种队列。

代码

Java

C++

D. Xor of 3

题解

首先我们考虑什么时候1会变成0，不难发现只有在三个数中有2个1时，这两个1会变成0。于是不难发现如果一开始有奇数个1，那么一定无解。

接着考虑到题目要求最多n次操作，因此不难猜测到最终的解法很可能是从左至右依次构建。（从右往左构建完全同理）

我们首先考虑最左侧是0的情况。比如010xxxx。对于010xxxx，我们可以分成两种情况：
一种是0101xxx，对于这种情况，直接变成0000xxx即可。
另一种是0100xxx，我们可以先把他变成0111xxx，接着再变成0001xxx。于是我们就通过两步操作将1往右推了2格。

显然对于011xxxx，我们可以直接依次操作将其变为000xxxx。因此对于001xxxx，我们可以将其转化为010xxxx或者011xxxx中的一种。

于是到此我们已经能够将任意的0xxxxxx通过至多两次操作转化为000xxxx。（因为我们已经讨论了001xxxx，010xxxx，011xxxx。）于是就能进一步将其转化为00000xx。
同时显然的，如果最左侧是1，而最右侧是是0的话，我们只需要倒过来操作即可。

现在，剩下的场景就是最左侧和最右侧都1的情况。

立刻可以想到，101xxxx和110xxxx可以直接变成000xxxx。于是我们只剩下100xxxx和111xxxx。而100xxxx可以直接转化为111xxxx，因此我们只需要考虑111xxxx这种情况。
结合0xxxx的情况，我们不难发现，在把最左侧的1变成0的前一个状态一定是110xxxx而不可能是101xxxx。于是为了产生110xxxx，其前一个状态必然是11101xx或者11110xx。
同理11101xx中的101是无法构造出来的，因此除非原数组恰好如此，否则我们只需要考虑11110xx。而要获得11110xx和要获得110xxxx是一样的。
于是对于111xxxx除了不断向右扩展，直到遇到一个101或者110为止。如果遇到了，考虑到奇偶性，可以以此为出发点，向左向右分别按照0xxxx处理即可。

代码

Java

C++