Codeforces Round #764 ABCDEFG Solutions (Java/C++)

A. Plus One on the Subset

Solution:

Obviously, output the maximum value minus the minimum value.

Code:

Java

C++

B. Make AP

Solution:

Just try to operate on each number in turn. As long as a feasible solution is found, then output YES.

Code:

Java

C++

C. Division by Two and Permutation

Solution:

For x from 0 to n, We count which a[i] can generate it.
So we find the x with the least possible i from 0 to n each time, and randomly find one of the i and perform several operations on it to get x.
If the process finds that an x has no optional i, output No.

Code:

Java

C++

D. Palindromes Coloring

Solution:

Obviously, as long as there is only one letter in a string that appears an odd number of times, and all other letters appear an even number of times, then this string must be able to get a palindrome by adjusting the order.

Then we only need to count how many pairs of letters, such as aa, bb, cc. And these letter pairs are evenly distributed to k strings.
In the last remaining, we pick at most k letters, and they can be added to k strings as the only odd number of letters.

Code:

Java

C++

E. Masha-forgetful

A good Trie and DP problem.

F. Interacdive Problem

Solution:

We binary search the initial value of x. We can find that for the median mid of all possible values of x, we give c such that mid+c is exactly divisible by n.
If x is on the left of mid, then $\lfloor\frac{x+c}{n}\rfloor<\lfloor\frac{mid+c}{n}\rfloor$. Otherwise $\lfloor\frac{x+c}{n}\rfloor=\lfloor\frac{mid+c}{n}\rfloor$.

The only trouble is to record each time c, and calculate the c for the current mid.

Code:

Java

C++

G. MinOr Tree

Solution:

First, we first find the highest 1 of the final result. So add edges by the number of bits until all the nodes are being connected together.

The answer we assume at this point is a binary number with all 1s, like 111111. (Perhaps the OR of all sides less than 6 bits is not 111111, but we can ignore that for later practice.)
At this time, the highest bit 1 cannot become 0, because if this bit can be 0, it means that 5 bits are enough. If we must replace the highest bit with 0, then the higher-order edge is needed to supplement, and the value of such OR is larger.
So we start from the second highest bit, and try to change each bit to 0 in turn, and see whether it can still form a tree. That is, we try 101111 first, then 1?0111, where ? depends on the result of the first attempt.

This is done because, obviously, we want to have 0 as higher bits as possible. Therefore, when discussing whether a certain bit can be 0, the lower bits must be all 1 (to form a tree as much as possible).

Code:

Java

C++