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

A. Countdown

Solution:

Obviously, we will replace every non-zero number with the ones digit and then subtract it.
Therefore, in addition to the operation required for this number to be subtracted, a swap operation can be added. (Except for the ones digit itself)

Code:

Java

C++

B. Swaps

Solution:

Obviously, we only need to focus on the first place. So we try from small to large according to the array b, and each time we try to choose the least cost a where a<b.

At the same time, we noticed that with each increase of b, there is only one more number that a can choose. So we only need to maintain a minimum cost of all a, and when there is a new a, update the minimum cost.

Code:

Java

C++

C. Book

Solution:

Obviously, this is a classic topological sorting problem, but there is a little change. It is a classic application.

Because reading is sequential reading, you cannot go back. Therefore, when we find that the in-degree of a certain chapter (denoted as x) is 0, and then update the in-degree of other chapters (denoted as y) according to its outgoing edge, if we find that this chapter(y) is before the current chapter(x), then this chapter must be read again anyway.
So we divided the queue into two:
One is to store only chapters that can be understood in this reading;
The other stores chapters that cannot be understood in the current reading due to the above scenario, although the in-degree is 0.

Naturally, after the first queue is processed, we can process the second queue. At this time, the second queue becomes the first queue.

Code:

Java

C++

D. Xor of 3

Solution:

First of all, we consider when 1 will become 0. It is not difficult to find that only when there are 2 1s in the three numbers, these two 1s will become 0. So it is not difficult to find that if there is an odd number of 1s at the beginning, then there must be no solution.

Then considering that the problem requires at most n operations, it is not difficult to guess that the final solution is likely to be constructed from left to right. (Construction from right to left is exactly the same)

We first consider the case where the leftmost is 0. For example, 010xxxx. And for 010xxxx, we can divide it into two situations:
One is 0101xxx. In this case, it can be directly changed to 0000xxx.
The other is 0100xxx, we can change it to 0111xxx first, and then to 0001xxx. So we pushed 1 to the right by 2 bits in 2 steps.

Obviously, for 011xxxx, we can directly change it to 000xxxx in turn. Therefore, for 001xxxx, we can convert it to one of 010xxxx or 011xxxx (be remove the first zero).

So now we have been able to convert any 0xxxxxx into 000xxxx through at most two operations. (Because we have discussed 001xxxx, 010xxxx, 011xxxx.) So we can further convert it to 00000xx.
At the same time, obviously, if the leftmost is 1 and the rightmost is 0, we only need to reverse the operation.

Now, the remaining scene is the case where both the far left and the far right are 1.

It can be immediately imagined that 101xxxx and 110xxxx can directly become 000xxxx. So we only need to consider 100xxxx and 111xxxx. And 100xxxx can be directly converted to 111xxxx, so we only need to consider 111xxxx.
Combining the situation of 0xxxx, it is not difficult for us to find that the state before changing the leftmost 1 to 0 must be 110xxxx and not 101xxxx. So in order to generate 110xxxx, the previous state must be 11101xx or 11110xx.
Similarly, 101 in 11101xx cannot be constructed, so unless the original array happens to be so, we only need to consider 11110xx. To get 11110xx is the same as getting 110xxxx.
Therefore, for 111xxxx, in addition to continuing to expand to the right, until a 101 or 110 is encountered. If you encounter it, considering the parity, you can use this as a starting point, and proceed to the left and right according to 0xxxx.

Java

C++