某岛

… : "…アッカリ~ン . .. . " .. .
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