E
\(BFS\) 求最短路
需要注意到,所有垃圾是作为整体一起移动的,因此可能存在垃圾的所有区域一定是原图的某个子矩阵(子矩阵之外的其他区域至少有过一次出界,说明垃圾已被清除),只有 \(H^{2}W^{2}\) 种。而整张图在每个方向的偏移次数也是固定的,即 \(dx \in [-n,n]\),\(dy \in [-m, m]\)。因此,可以用 \((lx, ly, rx, ry, dx, dy)\) \(6\) 个变量构成的元组表示转移状态,进行 \(bfs\) 转移,总状态数是 \(O(H^{3}W^{3})\) 的,刚好符合限制。
转移过程需要注意两个限制:
- 偏移时任何垃圾不能经过 \(T\) 所在位置
- 每个方向的偏移次数有上下界
最终符合要求的状态:\((lx, ly, rx, ry)\) 表示的子矩阵内没有任何垃圾(子矩阵之外的垃圾至少出过一次界,此时所有垃圾一定都已被清除)。而判断某个子矩阵内是否有垃圾,直接用二维前缀和预处理即可,实现 \(O(1)\) 查询。具体细节见代码。
code
F
折半搜索 + 斐波那契数性质
\(n \leq 60\),即使将区间分成两半,每侧最多仍会有 \(30\) 个数,不能直接状压暴力枚举所有子序列。但注意到子序列需要额外满足一个性质:不能选择任意相邻的两个数。这样每侧的合法子序列个数就会大幅度减少:具体地,一个长度为 \(n\) 的序列,选择满足任意两个数不相邻的子序列的个数为 \(fib_{n}\),而打表发现 \(fib_{30}\) 约为 \(2e6\)。因此每一侧单独的答案可以直接暴力来求;而求两侧合并的答案,也只需要枚举一侧,找另一侧相对应的余数即可,复杂度是 \(O(NlogN)\) 的,\(N = 2e6\),因此折半搜索即可。但需要注意,将序列分成两半后,需要额外考虑去除左侧结尾和右侧开头两个数相邻的情况,这种情况的计算方式和上述相同,只需要钦定一定选这两个数即可。总复杂度为 \(O(NlogN)\),具体细节见代码。
code