Codeforces 369 Div2
I have just finished a very disgusting [question] (http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1607) on 51nod. I have done it in various situations and I plan to write about some of the questions on 51nod sooner or later. After that, I made up questions E in this round. The questions in this round were very simple, so simple that I solved four of them, and the fourth question was submitted in 1:59:47, which was thrilling. I think I played well and was very lucky. After this battle, Codeforces’ rating became 1758, an increase of 77 points, which is quite happy. I wanted to record it because I didn’t do a lot of things in August, but it just passed.
The code is here.
Needless to say for question A, for question B, just find out the numbers and bring them in to verify whether the four directions meet the conditions.
C Coloring Trees
Question C means that there are n points lined up in a row, and each point either has a color or no color. Now you are asked to color all the colorless points with a color. The requirement is that after coloring, they are divided into k segments according to color. Each point on a color has a corresponding cost.
Let you find the minimum cost while meeting the conditions of segment k. If it cannot be satisfied, -1 is output.
dp[i][j][k] represents the minimum cost when reaching the i-th point, divided into j segments, and the current color is k.
The transfer is quite easy, not much to say.
In fact, it is very weak to do dp questions by yourself. This dp is relatively simple, and many people can see it directly at a glance.
D Directed Roads
The purpose of question D is to give n points, build a directed graph, and then give an outgoing edge for each point. The requirement is that you can change the direction of some edges so that there is no cycle in the graph. How many options are there for the edge?
This kind of question where each point has an edge has been asked many times. This kind of graph must form a ring. For a block, there are x points on the ring and y points not on the ring. Then the number of solutions is:
$$
(2^x-2)*(2^y)
$$
Subtract 2 to represent the empty set and the complete set, and you can change the direction for the rest. Then you can change the direction of the y side at will, and it will not form a loop. Just draw it and it will appear.
E ZS and The Birthday Paradox
~~For some topics, you still have to strike while the iron is hot like writing a diary, otherwise you will forget many of your feelings in the process. ~~
The meaning of question E is that given that there are 2^n days in a year and k people, what is the probability that these people have the same birthday.
~~Wow, after reaching this point, I found that this round of questions is really good, the meaning of the questions is concise and easy to understand, and the code is not particularly complicated and disgusting. ~~
First, based on the pigeonhole principle, if k>(2^n), then there must be the same situation and the result will be output directly.
Then, the probability of having the same birthday is difficult to calculate. The probability of having different birthdays is
$$
\frac{(2^n-1)*(2^n-2)*\cdot\cdot\cdot*(2^n-(k-1))} {2^{(k-1)*n}}
$$
First fix one person, and then the probability that the second person is not the same as him is (2^n-1)/(2^n). Next, consider the third person and not be the same as the first two people, and so on.
Since the result requires the simplest fraction, if this is the simplest fraction, you can be sure that 1-x is also the simplest fraction, because 1-a/b=(b-a)/b, and gcd(a,b)=gcd(b-a,b), so when finding the common denominator of the above formula, the common denominator is obviously 2^x.
Now the problem turns into a request
$$
(2^n-1)*(2^n-2)*\cdot\cdot\cdot*(2^n-(k-1))
$$
What is the maximum number of powers that can be divided by 2, and now if x (satisfies
$$
In the standard decomposition formula of prime factors of positive number n!, the exponent of prime number p is recorded as L_{p}(n!), then L_{p}(n!) =\sum_{k>=1}{[\frac{n}{p^k}]}
$$
Knowing this, the final result will be easier to obtain. Also for
$$
(2^n-1)*(2^n-2)*\cdot\cdot\cdot*(2^n-(k-1))
$$
For example, it can be found that when k-1>=mod, the final result must be 0, that is, there must be a number that is evenly divisible by mod. There’s not much left.
This question is really fun. ^—^