8 月杂题记

AT_joisc2017_c

题目描述：过于复杂，略。

答案明显具有单调性。考虑二分答案。

有一个很自然的想法，没点燃的要向正在燃的靠近，且一定以最大速度走 \(T\) 秒。

对于一个区间 \([L,R]\)，满足让它能用一个点燃的互相点燃。有一个条件为 \(X_r - X_l \le 2 \times (r - l) \times v \times T\)，转变一下，即为 \(X_r - 2 \times r \times v \times T \le X_l - 2 \times l \times v \times T\)。

我们就设 \(a_i = X_i - 2 \times i \times v \times T\)。

利用归纳法，要使 \([L,R]\) 合法，\([L+1,R]\) 或 \([L,R-1]\) 就需要合法。

我们找到一个性质最好的区间 \([L,R]\) 满足 \(L \le k \le R\) 且 \(a_L\) 最大，\(a_R\) 最小。

我们考虑 \([k,k]\) 扩展到 \([L,R]\)。

假设当前在 \([l,r]\)，先考虑扩展 \(l\)，到[i,r]。

• \(L \le i \le l \wedge a_l \le a_i\)。
• \(i \le j \le l \wedge a_j \ge a_r\)

其他情况同理。

若不能到 \([L,R]\) 则返回 \(0\)。

最后，我们将 \([1,n]\) 缩小到 \([L,R]\) 即可，与上面同理。