Original link: https://www.shuizilong.com/house/archives/codeforces-round-819/
C. Jatayu’s Balanced Bracket Sequence
adjustment method.
The base case is ((())). . The connected components are n. We observe under what circumstances the connected component decreases.
(()()). . Like this. . The condition is that a sequence of parentheses at the same level has occurred before such that there is more than one valid sequence ending at the current position.
So just open a bool array to record which levels have appeared, and of course, it needs to be restored when popping the stack.
D. Edge Split
Considering the tree case first, it is found that the coloring does not affect the result anyway.
Knowing that the purpose of our coloring each edge is to reduce a connected component of the corresponding color.
Therefore, we consider fixing one of the colorings as a spanning tree, so as to ensure that the extra edges do not form a cycle.
And this is always guaranteed with only 3 extra edges.
E. Almost Perfect
Count the number of permutations that satisfy $\lvert p_i – p^{-1}_i \rvert \le 1$ in permutations of length n.
Cyclic decomposition of the permutations that satisfy the conditions, there are only three cases, (i) (i,j) (i,j,i+1,j+1).
Regardless of the case of 4, the number of 2 can be enumerated and paired in pairs. The scheme is:
$$\Sigma \frac{i!}{j! * (i-2*j)! * 2^j}$$
The ground push formula can also be obtained in a similar way to Stirling numbers.
You can preprocess this by enumerating the number of 4.
F. Late For Work
Meaning: A straight line represents a path. There are n points on the line, representing n traffic lights. The period of all traffic lights is t, and the starting point of the period of the ith traffic light is that it is green for the first gi seconds of each period and red for the last t – gi seconds. That is, in each cycle time [0, gi) is green and (gi, t] is red. The time it takes to get from the i-th traffic light to the i+1 traffic light is di. You can start at any time, Ask how much time it takes to cross these n traffic lights starting from the first traffic light.
In my impression, the Round of Zhenhai Middle School with multiple schools for 14 years and the SRM rng_58 era had similar problems. . .
https://ift.tt/EquedI5
This article is reprinted from: https://www.shuizilong.com/house/archives/codeforces-round-819/
This site is for inclusion only, and the copyright belongs to the original author.