A: Strange Table
Solution:
Just calculate the row and column problem.
Code:
B: Partial Replacement
Solution:
Greedy。Start from frist *, find as far as possible * with in k.
Proof:
Under the premise of not exceeding k. If the closer * have solution，then the farther * must also have a solution.
Because they want as less * as possible. So chose farther one.
Code:
C: Double-ended Strings
Solution:
Because the length of a and b is 20. So just brute force with $n^4$.
Enumerate the possible substrings of a, and then get the b string to see if it is also a substring. Even no need KMP.
Code:
D: Epic Transformation
Solution:
Count the number of occurrences of each number. Then take the two most frequent numbers each time. It's enough to simulate it all the time, up to 10w times.
Code:
E: Restoring the Permutation
Solution:
Greedy. Let's prove it.
Because q is increasing.
when $q_i\neq{q_{i-1}}$, then $p_i=q_i$
When $q_i={q_{i-1}}$. If want lexicographically maximal, then go to the remaining numbers to find the largest value which smaller than $q_i$. If want lexicographically minimal, find the smallest value which smaller than $q_i$.
Code:
TreeSet is very useful.
F: Triangular Paths
Solution:
Let's consider the sum of each node. The node with odd sum always go to the right. And the next node of it is also with odd sum. So it come to a kind of "layer".
So the problem change to count the number of odd layer need to be passed.
The only thing is: If the current position and next position are in same even layer, then every step need change the status.
Code:
G: Maximize the Remaining String
Solution
Lexicographically maximum. And the length of answer is less than 26. So let's go through the index of answer string one by one.
For each index (for example ans[i]), we want to chose the biggest alphabet, and want to put it in front as much as possible.
But we also need avoid something like abcde, and we put ans[0]=e. And then all other alphabet can't put in follow position.
So what I did is: For each ans[i], we try to put alphabet from z to a.
- Filter out the alphabet never present or already be chosen.
- Find the first index of current alphabet after "the index of last chosen alphabet".
- Check all 26 alphabets, to see if all of them are never present or already be chosen or can be chosen after the index above. If so, we can chose current alphabet. And because we try from z to a, so if current alphabet is ok, then it should be the best solution.
代码：
