Codeforces Round #117 (Div. 2)
代码
A. Battlefield
any trench in meters numerically does not exceed b.
- 这个条件意味着每次都是在蓄能开始时走向下一条线段，也就是说每条线段相当于花费了\(a+b\)的时间。
- bfs,用\(d_i\)表示到达线段i需要经过最少的线段条数，到达\(B\)的时候直接计算欧几里得距离。
B. Vasya's Calendar
- \[ans = \sum_{i=1}^{n-1}{d-a_i}\]
C. Optimal Sum
- 考虑去掉绝对值符号。
- 假定最后和为非负数，那么\(k\)次操作将前\(k\)小的负数转化成整数。
- 将长度为\(len\)的窗口\([l,r]\)逐渐往右移，优先队列维护绝对值大的负数。
- 弹出\(a[r-len]\)时，判断该位置是否有变号。
- 加入\(a[r]\)时，如果是负数，需要考虑是否变号，有两种情况：
- 操作次数仍有剩余，那么显然直接变号。
- 否则，考虑之前变号的负数绝对值最小的那个，是否小于\(|a[r]|\)而进行替换。
- 若最后和为负数，将\(a_i\)取反后再做一次即可。
D. Common Divisors
- kmp求出所有循环串的长度。
- 假设循环串长度为\(L\), 判断\(s[0..L]=t[0..L]\)。
E. Wooden Fence
- \(f(i,j,k)\)表示长度为\(i\)，最后一块类型为\(j\)，旋转状态为\(k\)的方案数。