【第四次 ACdream 群原創群賽】解題報告


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