119F
ARC119F 题解
前言 ARC119F 好厉害,是没见过的自动机 DP。 正文 [1] 分析 主要分析一下为什么这么写。 [2] 状态设计 [3] 自动机状态转移 感觉状态设计中最难的就是如何处理带 \(O\) 的。 见参考资料。 [4] 代码 还没写。写ing 这是自动机的初始化(有点麻烦)。 int to[Kin ......
[ARC119F] AtCoder Express 3
题目链接 观察样例 1 的解释,发现切换类型的方法是比较单一的 这种就是直接走一段换一段,我们可以人为钦定换乘时最多走一步,因为相邻的同色也可以视作走车站 这种情况复杂一些,需要往回走一段,但是依然可以发现往回走也至多一步,因为如果走了两步说明往回走了一步到达的车站依然同色,那么走的车站必然不会是后 ......
[ARC119F] AtCoder Express 3
有简单做法,但是pb大神讲了自动机做法。 这么有趣的自动机不去做?亏大发。 有两个重要的观察。 当你出现长度大于 $4$ 的连续段时,一定会向后走一次并跳过这一段。 某些时候,当你能用同样的步数走到最后的两个格子,且中一个是 $\rm A$,一个是 $B$ 时,可以看作你处于一个既能是 $\rm A ......