About June

CodeChef April Challenge

qwer posted @ 2014年5月10日 16:44 in CodeChef , 1038 阅读
armer FebSolved POTATOES 5077 46.22
Shortest Path in Binary TreesSolved BINTREE 3863 37.89
Chef and DigitsSolved ADIGIT 2678 14.21
Counting MatricesSolved CNPIIM 1927 18.16
Divide the TangerineSolved TANGDIV 1486 17.4
Sereja and PermutationSolved SEAPERM 1174 8.94
Cards, bags and coinsSolved ANUCBC 343 5.39
Final Battle of ChefSolved FBCHEF 57 6.87
Chef and Tree GameSolved GERALD08 28 1.47
Make It Zero 3 LMATRIX3 4 1

GERALD08题解 -> http://blog.sina.com.cn/s/blog_5a4635700101i70w.html

FBCHER题解 :

 

    首先考虑询问,要求当前时间点到根路径上破产的点的个数,那么只要知道每一个点是在什么时候挂掉的就可以了。

    考虑操作,要将离T点距离为d的点的权值减 X/(2^d)。先得到树的bfs序,对于T的子树,同一层的点减少的权值是相同的,从T点向上走,同一层且没有减过的点减少的权值是相同的。维护以bfs序建的线段树即可

    再考虑询问,按时间做,如果一个点在这个时刻挂了,就把它的子树减1,这个只要搞个dfs序就可以了

 

Orz __Shi - > http://shizhouxing.is-programmer.com/

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter