Codeforces Round #762 (Div. 3) ABCDEFG Solutions (Java/C++)

A. Square String?

Solution:

First, see whether the length of the string can be divisible by 2, and then verify whether the first half and the second half are the same.

Code:

Java

C++

B. Squares and Cubes

Solution:

Preprocess all these numbers in the beginning. After that, putting it in the map or using binary search can solve this problem.

Code:

Java

C++

C. Wrong Addition

Solution:

Simulate from right to left. If the S of a certain bit is greater than or equal to A, the A+B of this bit must not be greater than or equal to 10. On the contrary, the S of the previous digit and the S of this digit must be equal to A+B.

If it is found during the process that it cannot be constructed, then it cannot be constructed.

Code:

Java

C++

D. New Year's Problem

Solution:

Binary search the final result. If this result is ok, then the following conditions must be met:

1. Everyone can find at least one store, making that person's satisfaction at that store higher than the current results.
2. At least one store exists so that this store can satisfy at least two people at the same time.

Code:

Java

C++

E. MEX and Increments

Solution:

First, we count the number of occurrences of each number, denoted as count.

For the ith number, obviously we need to at least change all count[i] to i+1.
Then we add the number of steps are needed to have values from 0 to i-1.

Obviously, in order to have values from 0 to i-1, the operation that needs to be operated must be: a certain count[j]=0 (j<i-1). At this time, find the nearest k from j to the left so that count[k]>1.
So we use a list to maintain all count[k]>1, and whenever we find count[j]=0, just take one from the list and fill it up.
Therefore, we can update this list by the way after calculating the current i, and calculate the minimum cost in advance so that 0 to i have values.

Code:

Java

C++

F. Let's Play the Hat?

Solution:

Just take turns assigning people each time.

Taking m=3 and n=8 as an example, we make the following arrangements:

Code:

Java

C++

G. Unusual Minesweeper

Solution:

First, through DSU, we linked all the mines that would explode together.

So we sort all connected blocks. Then simulate second by second until all connected blocks explode.

Code:

Java

C++

There is also a question H, at a glance it is 2400, and then it seems to be more troublesome. After all, it's New Year's Eve, so be lazy.