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++
