CodeChef August Lunchtime 2016
I did August Lunchtime 2016 on Codechef. The above questions all have Chinese questions, answers, and codes. I think this website is also good. . .
Then after finishing this time, I found that there were three easy courses and one medium course. I didn’t use any data structure at first thought, it seems to be similar, but the diameter of the fourth tree has the same idea as the farthest point pair of the tree on 51nod. When I did it, I felt it was quite difficult. In the third question, the array size is too small, but it keeps returning to WA, and I have been looking for it for a long time. The second one with the same number also WA’d one night. Thinking about it this way, it seems that it is not that simple.
The code is here.
There is no need to write question A, Studying Alphabet. . .
Question B Lock-Free Stack
Because there is P = (A1 + 1) × (A2 + 1) × … × (AN + 1), and P<=10^6, so there are at most 20 processes, then the output of each process must comply with the stacking order. (At first, I searched one by one and found that there were the same numbers, so I waited all night. Later, I just needed to satisfy the order for each process).
Question C Short in Average
I have done the original question of this question myself, and my impression is that the average value problem can easily be divided into two points, and then subtract the two points from each value, and then judge. [51nod The same is true for 1711 average] (http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1711). Divide the average number
The idea of this question is also the same. Subtract the dichotomy value x from each edge, and then directly judge the ring.
Question D Product of Diameters
The great thing about this question is that you need to think backwards, add edges to it, and then output the result. Then adding edges to it is the product of the diameter divided by the diameter of each tree. This can be maintained, and then the internal diameters of the two trees are found. This maintenance is equivalent to maintaining the farthest distance in a set. I thought about it and [51nod 1766 The farthest point pair on the tree] (http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1766) is essentially the same question. It also maintains the two farthest points in a set. Then the merger of the two sets can only be found among these four points. Find lca by doubling and find the distance.
The idea of this question is quite simple. If you want to think clearly about the process, you still can’t write some details well enough.