某島

… : "…アッカリ~ン . .. . " .. .
September 27, 2012

Codeforces Round #140

Brief description:

A. Flying Saucer Segments
.. 3 階漢諾塔(只能相鄰柱子間移動。。
有公式移動步數 f(n) = 3^n – 1..

Python:
http://codeforces.com/contest/226/submission/2239524
Ruby:
http://codeforces.com/contest/226/submission/2269427

B. Naughty Stone Piles
。堆石子問題。。(排序,分組。。
http://codeforces.com/contest/226/submission/2270030

C. Anniversary
求 [l, r] 之間的一個大小為 k 的子集,是的它們的 gcd 最大。

D. The table
貪心。。(反覆尋找局部收益最大操作直至不能。。
http://codeforces.com/contest/226/submission/2239190

E. Noble Knight’s Path .. .
。。給定一棵樹,動態維護以下操作。

  • 1 u: 污染一個頂點,(每個頂點至多被污染一次,沒有逆操作。。
  • 2 u v kth y 尋找 u、v 之間路徑上第 kth 個沒有被污染頂點。(只考慮 y + 1 時刻之後的污染操作。且 u,v 不納入考量。。。

Analysis:

C. Anniversary
設最大公約數為 d,集合中最小數為 ad,最大數為 bd。
則有 ad >= l, bd <= r。 。。方法1. 枚舉 d,反覆迭代。(每次用上一輪的 d 算出新的 d 並更新答案。 http://codeforces.com/contest/226/submission/2268689
。。方法2. 觀察答案要不 d 很小。。要不 a 很小。。(暴力枚舉兩種情況即可。。
http://codeforces.com/contest/226/submission/2268680

E. Noble Knight’s Path .. .
。。此題為可持久化版本的 QTREE 2 ..用主席樹維護任意兩個時刻之間路徑上有多少個點被污染過,再按照 QTREE 2 的方法倍增祖先即可。

http://codeforces.com/contest/226/submission/2265544

External link:

http://codeforces.com/contest/226/room/4