A. Average Height
Solutions:
Put all odd number together. And then put all even number together.
Code:
B. TMT Document
Solution:
Greedy. Firstly, let's count the number of M as count_m. And we mark first count_m T as leading T (the first T in TMT). And mark remained T as ending T (the last T in TMT).
Scan the string once.
- If we meet a leading T, then
count_first++. - If we meet a M, then
count_first--;count_m--;count_last++. - If we meet a ending T, then
count_last--.
In this process, all these three counts can't less than 0. And after this process, all these three should be 0.
Code:
C. The Sports Festival
It is a normal DP problem. We maintain the segment state. After sorting, just look at the smallest sum for a segment.
D. Binary Literature
Simple structure problem. Find the proof for the existence of the answer first. And based on the proof, the solution can be given almost immediately.
I forgot to find the longest common sub-sequence during the contest. After the contest, I thought about it again. And I found that: it's easier to build based on the number of 0 and 1 by brute force.
E. Almost Sorted
A little complex. Can split to two parts for this problem.
One part is the preprocessing of all the possibilities in the permutation of length $n$.
The second part is to construct the result based on the number of all the permutations.
The logic is a bit complicated, and you can think of a solution if you think about it.
