AtCoder Grand Contest 004
Title link and Code link
A Divide a Cuboid
The meaning of the question is to give a cube of A*B*C and divide it into two parts using a face. The difference in volume of the two parts is required to be minimum.
If one of A, B, and C is an even number, then it is directly 0. If they are all odd numbers, choose the smallest one among A*B, B*C, and A*C.
B Colorful Slimes
The meaning of the question is that there are N colors, and there are two ways to get the i-th color.
Directly spend Ai seconds to get the i-th color.
Recite a spell and spend k seconds so that the i-th color you have obtained becomes the i+1-th color, and the N-th color becomes the first color.
Enumerate the number of spells to be used. When x spells are used, for the i-th color, the cost is the minimum value of the previous x colors.
C AND Grid
The meaning of the question is that there are two h*w grids A and B. Each grid on the graph is either a black point or a white point. A and B are both connected graphs. Now A and B intersect together to form graph C. Each square is ANDed. Given two intersecting graphs C, find the original two graphs A and B. It is known that the black point of graph C must not be on the boundary.
You will find this kind of connection. . .
Then according to Figure C, Figure A and Figure B can be constructed like this.
D Teleporter
The purpose of the question is to give a directed graph, any point can reach point 1, and it is required to change the end points of some edges in the graph so that all points reach point 1 after accurately passing k times.
After reaching point 1 after k times instead of less than or equal to k times, it can be analyzed that the outgoing edge of point 1 must point to point 1. If not, it needs to be modified.
In this way, the distance between all points to point 1 is less than or equal to k.
greedy. Use 1 as the root node for deep search. When the maximum depth of a node’s child nodes is greater than or equal to k, this edge needs to be cut and connected to node 1. (At first, I wanted to judge that a point needs to be cut when its current depth is greater than k. Later, I found that the distance needs to be calculated, and there may be points below that need to be cut. This approach is more troublesome)
E Salvage Robots
The meaning of the question is that there is an exit on the h*w grid. All robots follow the same instruction direction. When the robot goes out of bounds, the robot is invalid. Ask how many robots can reach the exit at most.
I have thought about this question for a long, long, long, long time. . . I never understood the meaning of the solution. . .
Later, after asking LYC, finally. . .
First of all, we must not consider the movement of these robots. Consider the movement of the exit, and then record the movement distance of the exit in four directions. The picture above shows that the exit takes u steps up, d steps down, le steps to the left, and ri steps to the right. The yellow area represents the rescued robot. Then you will find that if the exit takes u steps up, the u-row robot below cannot be saved. Therefore, the robots in the red area in the picture below represent either those that have been rescued before, or those that have exploded. The ones in the white boxes represent things that are not determined yet and need to be resolved.
So now, I have a general idea. Use dp[le][ri][u][d] to represent the current state. Consider four directions. Assume that the current robot goes to the right, then you can get the robot in the green box in the picture below. If you go down, you can get the robot in the purple box.
F Namori
The meaning of the question is an undirected connected graph with n points and m (n-1<=m<=n) edges. At the beginning, all points are white. For each operation, two adjacent points are selected and their colors are flipped. It is required that they are all black points in the end. Find the minimum number of operations.
First consider the case of m=n-1, and this question is magically transformed again. . .
Because the tree is a bipartite graph, after dichotomizing the tree nodes, each operation is equivalent to transferring black to the white node through this edge. Then I record how much black is transported on each edge, which is the token mentioned in the solution. If you can change the question here, it would be really easy to get 1500 points. . .
Then we need to consider the situation of the ring. Since there are at most n edges, we need to consider what will happen if the edges on the ring are removed.
Even-numbered ring: To judge that the remaining graph is still a bipartite graph, the number of tokens passing by the three-thirds edge + the number of tokens passing by the other edges is the minimum.
In an odd-numbered ring, at this time, either the two points have tokens, or neither points have tokens. Distribute the remaining more or less tokens to these two points, and calculate the entire graph again.