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

A. Sereja and Bottles

• 模拟。

---

B. Sereja and Array

• 维护全局增量(Y)，对于操作1（即(a_{v_i}=x)）操作，改为(a_{v_i}=x-Y)。

---

C. Sereja and Contest

• 观察式子(d_i=sum_{j=1}^{i-1}{(a_jcdot(j-1)-(n-i)cdot a_i)})
• 假设最先排除的是(k)，那么对于(i<k)的数是不会有影响的，因为(d_i)会因为总人数(n)的减少而变大。

---

D. Sereja and Periods

• 显然，匹配过程是贪心做的。
• 问题转化为串([a,b])最多能匹配多少个串(c)。
• (dp)做法：
  1. (dp(i))表示串c从位置i开始，串a从位置0开始匹配得到的最长长度。
  2. 假设当前匹配了(L)长，则(L+=dp(L \% |c|))，重复(b)次即可。
• 循环节做法：
  1. 每次匹配一个串(a)后，得到串(c)的位置，由于(|c|le 100)，所以最多101次后得到循环节长度，那么就可以直接计算最后的数量。

---

E. Sereja and Subsequences

• 问题就是求所有不同上升子序列的乘积和。
• 假设所有(a_i)均不相同，那么直接树状数组维护即可。
• 由于(a_i)可能相同，所以需要考虑前一个(a_i)带来的贡献，计算新的贡献时需要扣除重复的贡献。

---

F. Sereja and Straight Lines

• 将坐标系转45度后，原坐标系的曼哈顿距离成为新坐标系的切比雪夫距离。
• 将点按((x,y))排序，二分距离(d)，维护(dxle d)区间，两边的(y)坐标极差不超过(d)，则当前(d)可行。