FoxAndMountainEasy

作者：赵晟宇

关键词：模拟 数学

题目简述

定义升降序列只包含字符'U'或'D'，其中'U'表示升高一个单位高度，'D'表示降低一个单位高度，且每个时刻的高度都不得低于0。给定初始高度$h0$与目标高度$hn$，要求构造一个长度为$n$的升降序列，且这个序列中必须存在连续的一段与给定的特征序列相同。特征序列的长度为$m$。输出是否可能即可。

$1 \leq m \leq n \leq 10^5$ $1 \leq m \leq 50$ $0 \leq h0, hn \leq 10^5$

算法

容易发现，升降序列的顺序对目标高度是没有影响的。若不考虑高度至少为0的限制，我们可以直接假定特征序列出现在前$m$位。如果把特征序列放在前$m$位，出现了高度为负值的情况，设这个过程中的最低负高度为$-h$，那么我们一定需要先用$h$个'U'来提升到高度$h$，再执行特征序列。剩余位数不足$h$时直接输出无解。否则，计算出经过这段特征序列之后的高度$h'$，以及剩下的序列位数$n'$。

接下来的判断是非常简单的。设剩下部分的高度差$d = |h' - hn|$，那么满足要求的充要条件是$n \geq d$且$n - d \equiv 0 \pmod{2}$。

时间复杂度$O(m)$，空间复杂度$O(m)$。