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

A. Magnets

• 模拟。

---

B. Simple Molecules

• 设12、13、23边的条数，列出三个等式，解即可。

---

C. Rational Resistance

• 题目每次扩展的电阻之一是1Ω的，所以假设当前的电阻为(frac{a}{b})会变成(frac{a+b}{b})或(frac{a}{a+b})，其实就是求gcd的过程。

---

D. Alternating Current

• 若出现连续两个相同的符号，其实线的方向是不变的，最后就是转化成括号匹配。

---

E. Read Time

• 二分时间(t)，(p_1)应该由(h_1)来覆盖，此时分两种情况：
  1. (h_1<=p_1)，(h_1)覆盖区间([h_1, h_1+t])。
  2. 否则，(h_1)此时有两种覆盖(p_1)的方法：先覆盖(p_1)，然后马上往回走；先往后覆盖，然后返回(p_1)。在这两种方法找覆盖区间最大的。

---

F. Water Tree

• 对于操作1，利用dfs序转化成区间覆盖问题，覆盖的值为最大操作id。
• 对于操作2，点(v)影响它的所有祖先，dfs序下这些祖先的区间都包含点(v)，那么就相当于祖先查询区间最大的操作id。
• 整个问题就变成区间修改+单点查询和单点修改+区间查询问题。
• 更简单的做法：用一个set维护所有empty链，对于操作1来说，直接暴力删除区间内的链;操作2则直接将点(v)插入，表示(v)到根的empty链。

---

G. Pumping Stations

• 本题的关键在于构出最小割树，在这前提下，根作为序列第一个值，每次贪心地取和序列最后一个点流最大的点，构出序列。