Original link: https://www.shuizilong.com/house/archives/codeforces-global-round-24/
Problem D. Doremy’s Pegging Game
In short, it is very similar to question D in the previous game . . Also a combinatorial count that needs to enumerate something. . .
First enumerate the last remaining angles, then enumerate how many angles are left in the middle, and finally remember to discuss the parity.
Problem E. Doremy’s Number Line
First of all, if x can be colored, then x-1 must also be colored, so we only need to find the maximum value that can be constructed and compare it with k.
Then obviously we have the ordinary lower bound a[0] and the ordinary upper bound a[0] + b[0], this is because we must dye 0 in the last step.
Now we don’t consider 0, and see if the maximum coloring of the remaining numbers can reach a[0], so we have reduced to a sub-problem, but here we still have a search tree about permutations that needs to be processed.
The core of the problem is to examine the search tree and seek pruning.
We found that as long as we sort according to a, we can optimize the size of the search tree to O(n).
See the solution for details. . .
Another approach is to sort by a+b, and the size of the search tree can also be optimized to O(n).
See here for details. . .
Using sorting to reorganize the search order is a common pruning technique for search questions. . . But this time it turned directly into simple greed. . .
All in all it looks pretty simple. . But it’s still quite difficult for me. . .
Problem F. Doremy’s Experimental Tree
Reminiscent of question F of #21 . . But this question is actually easier. .
The core is that the f() function satisfies the monotonicity of the path inclusion relationship in the tree (quadrilateral inequality?), and the distance function of the tree also satisfies this property.
Therefore, directly use f() to find the maximum spanning tree (because monotonicity is just inverse) to get the tree structure, and then simple redundancy can get the edge weight.
It can also be reversed to first use redundancy to directly obtain the distance function, and then use the distance function to find the minimum spanning tree to obtain the tree structure. Refer to here .
In short, the amount of information given in the title is redundant, and there should be many ways to do it.
This article is transferred from: https://www.shuizilong.com/house/archives/codeforces-global-round-24/
This site is only for collection, and the copyright belongs to the original author.