LSS 1 Editorial

Contest Link
If you haven't read the problems or tried to solve it yourself, don't read this.

A - Clock

Difficulty: d2b
Hint The hour hand of the clock moves 0.5 degree per minute, the minute hand of the clock moves 6 degree per minute. Then it turns into a Travel problem. In each minute, the minute hand can catch up the hour hand by 5.5 degree.
Extra Can you solve it when there are X hours in the clock and Y minutes in each hour?

B - DP

Difficulty: d2c
Hint F(i,j) means the number of paths from (1,1) to (i,j) by walking down or right. There are A path to choose when walking down and B path to choose when walking right. Consider each possible route from (1,1) to (i,j), the contribution of this path is always a^ib^j. So the answer is C_{i+j}^{j}a^ib^j
Extra can you solve it when F(i,j)=aF(i-1,j)+bF(i,j-1)+c?
Extra/Source can you solve UOJ 420?

C - Triangle Fang

Difficulty: d2c
Hint We can get the answer for (x,k) (don't forget k is constant) in O(n) then we consider if we move the triangle one-unit right, what's the delta of the deliciousness. Then you will find this problem can be done by 3 prefix sums.
Extra/Source Can you solve CF 263E?
std wrote unreadably: std

来源:Hell Hole Studios Blog

< <上一篇