AtCoder Grand Contest 002
Question link, I have never been exposed to this D question before, the overall score is two points, which is quite typical. I had a headache doing E and F. I submitted question E many times and question F was the DP. . . They are all amazing.
A Range Product
The question is, given a range, ask whether the product is exactly negative. . . . . .
B Box and Ball
The meaning of the question is that n boxes are given, the first box has a red ball in it, and the rest have white balls. Now there are m operations, each time a ball is randomly drawn from the x-th box and placed in the y-th box. Ask how many boxes are likely to contain red balls in the end.
Anyone who has an affair will be counted. Please note that there is no ball in the box.
C Knot Puzzle
The meaning of the question is that there are n pieces of rope, and each piece of rope has a length. Now these n pieces of rope are connected together, and Snuke wants to take it apart. The requirement is to choose a length of at least L before it can be broken into two pieces. Ask if this piece of rope can be broken into n pieces and give a strategy.
At the beginning of this question, I was greedy and started to split it from both ends, and found that it was wrong. For example, in this case:
4 6
3 3 1 4
It is better to select the maximum value of the adjacent sum, and if it satisfies >=L, this segment will be the last segment.
D Stamp Rally
The meaning of the question is to give an undirected connected graph, and then ask x, y, z q times, and find out after which edge the number of nodes connected by x and y is, and the number is greater than or equal to z.
The problem seemed very scary when I was doing it. In fact, for each query, it is to see which time after adding an edge, the sum of the number of the two union sets is greater than z. Then for q queries, we use the idea of dividing the whole, save the mid in the vector, and then run the whole together. Keep narrowing it down each time.
E Candy Piles
The meaning of the question is that there are now n piles of balls (the original question is about sugar, it is easier to understand the picture if it is said to be a ball…). Both parties have two operations. One is to select the pile of balls with the most balls and eat them. . . Another is to eat one ball from each pile. The last person to eat the ball loses. First give the number of balls in each pile and ask who wins in the end.
This question is amazing. . . I’ve seen something similar.
If we arrange the balls from largest to smallest, we will find that it is like this,
In this case, the two operations are as follows:
After that, the problem can become that you start walking from the lower left point and stop at the boundary, like this:
For the border, it is a victory state, marked ⭕️. Failure status, marked ❌. Then the reachable state of a point (x, y) is (x+1, y), (x, y+1). Based on these, the winning and losing situation of each point in this picture can be drawn.
Now we are asking whether the lower left point (1,1) is ❌ or ⭕️.
According to Figure 7, the analysis shows that the distance from the inflection point to the line y=x must be odd or even. If the distance is even, the winning state cannot be achieved. Finally, note that all boundary values are on the straight line of y=x. At this time, there is only one inflection point, and there is no right value, only the up value.
F Leftmost Ball
The meaning of the question is that there are balls of n colors, ranging from 1 to n, and there are k balls of each color. Now arrange these balls in a row, and dye the leftmost ball of each color into color 0. Ask how many possible final ball arrangements there are.
This dp is also awesome. . . .
It is very wonderful to convert these n*k balls into a graph. The gray ball represents the color 0, and then ask how many topological sortings there can be in this graph. (ORZ….)
How many kinds are there next? . . And use dp to solve (ORZ….)
For each situation dp[i][j], there are two options: 1. Take a gray ball dp[i-1][j]. 2. Take an orange ball and put it first in the current position, then the position of the remaining k-2 balls is arbitrary, that is, C(i+j*(k-1)-1, k-2)*dp[i][j-1].
Finally multiply the result by n!