Codeforces Round #189 (Div. 1 + Div. 2)

A. Magic Numbers

• 不能出现连续的3个4，以及1、4以外的数字。

---

B. Ping-Pong (Easy Version)

• 暴力。

---

C. Malek Dance Club

• 考虑(x)二进制每一位1，假设位置为(p)，则前(p-1)位都需要一样，否则之前就计算了贡献，那么后面的位可以任取。

---

D. Psychos in a Line

• 链表模拟。

---

E. Kalila and Dimna in the Logging Industry

• 因为(b_n=0)，所以用最小代价砍倒第(n)棵树即可。
• (dp(i))表示砍掉第(i)棵树的最小代价。

• [dp(i)=min{dp(k)+b_kcdot a_i} ]

• 斜率优化。

---

F. Have You Ever Heard About the Word?

• 删除次数最多(sqrt n)次。
• 假设当前的删除长度为(len)，每隔(len)取一个关键点(p)，如果存在可删除串，则(p)和(p+len)的最长前缀和最长后缀之和大于(len)，通过二分+hash可以(logn)计算。

---

G. Ping-Pong

The length of the new interval is guaranteed to be strictly greater than all the previous intervals.

• 对于(a<b)，(|I_a|<|I_b|)，区间(a)和区间(b)要么相互可达，要么区间(a)完全被区间(b)完全包含。
• 利用线段树+并查集维护相互可达的区间。
• 判断(a)是否可达(b):
  1. 相互可达，即属于同一集合。
  2. 区间(a)的端点是否被(b)集合包含。
• 满足上面其中一点说明(a)可达(b)，否则不可达。