CODE FESTIVAL 2016 Qualification Round B

Title link and Code link

It is very rare that I can solve four questions this time (A and B can no longer be improved). I was very sleepy at noon, so I slept for an hour, and then I finished C and D. The Trie for Question E is great. . .

C - Gr-idian MST

The meaning of the question is that the grid of $W \times H$ is given, and then there is an interconnection cost between each grid, from grid $(i,j)$ to grid $(i+1,j)$ for any ZZZPROTECT5 The ZZZ costs are all $p_i$, and the cost of any $i$ from grid $(i,j)$ to grid $(i,j+1)$ is $q_j$. Ask the minimum cost required to finally connect the grid into a whole.

At first, I looked at Bingchaji and found that the order of magnitude was a bit large. . . Then look for patterns and keep looking for the minimum value. If it is in the x direction, then y will be less than 1 next time. If it is in the y direction, x will be less than 1 next time.

D - Greedy customers

The meaning of the question is that there are $N$ customers standing in a row. Each customer has $A_i$ dollars in his hand. Now it is up to you to bid. Starting from customer 1, if the price offered is less than or equal to the money in his hand, then he will buy your item. The question requires that the money in each customer’s hand cannot be 0 at the end, and asks how many items can be sold at most.

One minute before the end of the game, I didn’t think carefully about the situation. I submitted it myself in a panic, but I actually passed it. . . Later I found out that the situation was indeed poorly thought out and I can only say that I was lucky.

First of all, it is definitely possible to turn the selling price into an ascending sequence without affecting the final buying and selling situation.

Then consider starting from price 1, selling to the first user, and leaving 1 yuan. The price $x$ starts from 2. For the money $N$ that can be divided into $x$, $N/x-1$ items can be sold, while $x$ does not need +1, because the last item can be sold for $x+1$, making the remaining money at this position less than $x$ yuan. And if you encounter a situation like $val[i]=x$, there is nothing you can do. $x$ can only add 1.

E - Lexicographical disorder

The meaning of the question is that $N$ strings are given, $Q$ queries $k_i, p$, each query is the position of the $k_i$th string in the dictionary order.

Create a Trie tree and record the value of each position. When querying, count the number of other characters in the same position of each string and the number of ending characters. The solution is really bright. . .