ABC388 F 题解

chenxi2009 · 2025-01-12 12:13:52 · 题解

Upd 2025.1.15：修改了一些错误。删去了过于简单的证明。优化复杂度。

思路

暴力复杂度 O(NB)。考虑去掉明显不需要计算的位置。\ 除去 A=B 的情况外，发现起点后若干号位置后面都是可达的。易证这个位置大约为 B^2。\ 换句话说如果一个点可达，只要下一个区间离它足够远，那么下一个区间前面一串位置都是可达的。以这个足够远的长度（大约 460）把区间分隔成若干个大块，每大块内部暴力求解即可。求出一个格子是否可达复杂度为 O(B)，总时间复杂度为 O(MB^3)。

细节：

• 存在大小大于等于 B 的区间时直接输出无解。
• 除去第一个大块之外，每一个大块前面要预留出 B 个可达的位置作为起点。终点同理。
• 注意判断终点是否可达，所以也要把它划进一个大块里。

在暴力求解的时候我们判断一个点前面一个区间内是否有点可达以得出这个点能否到达，那么这可以用一个树状数组去维护。时间复杂度降为 O(MB^2\log M)（不过真的有必要么）。

代码

口胡的还没写，晚点可能补上。