A. Polycarp and Coins
Solution:
Divide n by 3. If the remainder is 0, then c1 and c2 are equal; if the remainder is 1, then c1 has one extra; if the remainder is 2, then c2 has one extra.
Code:
Java
C++
B. Wonderful Coloring - 1&2
Solution:
Just Simulation.
First of all, if there are more than k of the same number, then ignore the part that exceeds k and do not paint, and only paint k types.
Then if a certain number happens to appear k times, just paint k colors directly.
Finally, if a certain number is less than k, after painting the current number, paint the next one, and paint from the next color.
For example:
Suppose our coloring order is: green, yellow, red. Proceed as follows:
- Paint the first 3 green.
- Paint the second 3 yellow.
- Because all 3s have been painted, so we continue to paint from 1. Because the previous color was yellow, paint the first 1 in red.
- Continue to paint 1, the next 1 is green, so the second 1 is painted green.
- 1 is finished, and then paint 4. We paint the first 4 into the next color, which is yellow.
Code:
Java
C++
C. Interesting Story
Solution:
Check each letter to see how many words the letter can support.
For each letter, we first look at how many times the letter appears in each word than other letters (it may be a negative number). Then, after sorting from largest to smallest, select words one by one.
Code:
Java
C++
D. Domino (Easy/Hard)
Solution:
If the number of rows is odd, first fill the odd layer with horizontal dominos. If the number of columns is odd, first fill the odd layer with vertical dominos.
Because if the number of rows is odd and no odd layers are laid by domino, then there must be a certain column, the remaining rows are odd numbers, and the domino need to be laid vertically, which is impossible.
After that, use same domino to make up 2*2 squares and fill them in order. Therefore, the number of horizontal or vertical cards remaining must be an even number.
Code:
Java
C++
E. Fixed Points
Solution:
The definition dp[i][j] represents the maximum m that meets the conditions when keep j digits in the first i digits.
dp[i][j] = dp[i - 1][j];
if (a[i] == j) {
dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, dp[i][j]);
} else {
dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i][j]);
}
So that:
- If a[i] is not selected, then dp[i][j] = dp[i-1][j];
- If you choose a[i], and this a[i] happens to be the last number, then dp[i][j] = dp[i-1][j-1]+1;
- If you choose a[i], but a[i] is not the last number, then dp[i][j] = dp[i-1][j-1].
Finally, dp[i][j] can be the largest among these three possible values.
Code:
Java
C++
Others
Too busy these days. Skip F.
