…

Problem C. Hotel

。。给定一颗 n 个结点的点权树，问树上两点的路径之间第 k 个权值介于 [a, b] 之间的结点是什么。。。
（ n <= 1e5, 每个结点的权值 ai 介于 [1, 1e5] 之间。。且互不相同。。 。。做法类似 Codeforces 140 DIV 1 的 Problem D。。
。。对于询问树上两点之间第 k 个满足条件的点。。一般方法是通过倍增祖先。。进行二分查找。。。
。。。。需要有两个 move_up 函数。。一个是普通的主要用来求 lca。。另一个需要计算树上两点之间，权值介于 [a, b] 之间的结点有多少个。。对于后者我们使用主席树来维护。。复杂度 O(nlognlogn)。。。

。。(。倍增祖先。。主席树。。700ms+- …

Problem E. Hotel

。。。问 n 个人的 m = 2 的约瑟夫问题。。。
。。最后剩下的人是多少。。

def f(x)
	return x == 1 ? 1 : 2 * f(x/2) + (x.odd? ? 1 : -1)
end

while s = gets do
	p f(s.chomp.to_i)
end	

Posted by xiaodao
Category: ACdream
Tags: 主席树