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

A. Whose sentence is it?

• 模拟。

---

B. Archer

• [pro=frac{a}{b}+(1-frac{a}{b})(1-frac{c}{d})frac{a}{b}+(1-frac{a}{b})^2(1-frac{c}{d})^2frac{a}{b}+… ]

• 本质就是无穷级数求和。

---

C. The Closest Pair

• 因为根据(x)坐标差值优化，那么只要构造(x)坐标都一样的即可。

---

D. Cats Transport

• 假设一人在时间T出发，则所有满足(T+D[h_i]ge t_i)的猫都会被带走，所以按(t_i-D[h_i])排序，就可以用(dp)做。
• (dp(i,j))表示前(i)只猫(j)个人的最小代价。
• 写出转移方程后，发现可以用斜率优化做。

---

E. Fetch the Treasure

• 问题主要在于如何确定一个格子是否可达。我们可以将格子按(pos \% k)分组，对于一个组(g)来说，我们只要确定(min{pos,pos \% k =g})，那么大于等于最小值的点都是可达的，由于(kle 10^4)，所以使用(dijkstra)求最小值即可。

---

F. Interval Cubing

• 根据Fermat's Little Theorem，(x^{p-1}=1(mod p))。
• 对一个数(x)操作(k)次后，(x'=x^{3^k mod (p-1)}(mod p))。
• 因为(3^{48} mod 95542720 = 1)，所以循环节为48。那么对于每个数维护48个值即可。

---

G. Biologist

• 总收益为(sum{w_i})，考虑总收益扣除最小代价，将问题转化为最小割问题。
• 根据狗的性别划分成二部图。源点(S)连接性别为1的狗，容量为(v_i)，汇点(T)连性别为0的狗。
• 若人的需求是0，则与源点(S)连接代价为(w_i+isfriend*g)的边，跟狗都连(INF)的边。若需求是1，则与汇点(T)连接代价为(w_i+isfriend*g)的边，狗同上。