P14044 [SDCPC 2019] Wandering Robot

DreamGrid 制作了一个可编程机器人，用于探索无限二维平面。机器人有一个基础指令序列 $a_1, a_2, \dots a_n$ 和一个“重复参数” $k$，二者合起来形成完整的指令序列 $s_1, s_2, \dots, s_n, s_{n+1}, \dots, s_{nk}$，用以控制机器人。 一共有 4 种有效指令，分别为 `U`（上）、`D`（下）、`L`（左）和 `R`（右）。假设机器人当前位于 $(x, y)$，指令对机器人的控制如下： - U：机器人移动到 $(x, y+1)$。 - D：机器人移动到 $(x, y-1)$。 - L：机器人移动到 $(x-1, y)$。 - R：机器人移动到 $(x+1, y)$。 完整指令序列由如下公式生成： $$ \begin{cases} s_i = a_i & \text{如果 } 1 \le i \le n \\ s_i = s_{i-n} & \text{否则} \end{cases} $$ 机器人初始位置为 $(0, 0)$，依次按顺序执行完整指令序列中的每一条指令，总共执行 $nk$ 条指令。为了评估探索过程，DreamGrid 想要计算机器人在执行全部 $nk$ 条指令过程中，距离起点 $(0, 0)$ 的最大曼哈顿距离。 回顾一下，$(x_1, y_1)$ 与 $(x_2, y_2)$ 之间的曼哈顿距离定义为 $\left| x_1 - x_2 \right| + \left| y_1 - y_2 \right|$。

输入包含多组测试数据。第一行输入一个整数 $T$，表示测试用例的个数。对于每个测试用例： 第一行输入两个整数 $n$ 和 $k$（$1 \le n \le 10^5, 1 \le k \le 10^9$），分别表示基础指令序列的长度和重复参数。 第二行输入一个字符串 $A = a_1a_2\dots a_n$ （$|A|=n$，$a_i$ 取值为 `L`、`R`、`U`、`D` 中的一个），代表基础指令序列中的第 $i$ 个指令。 保证所有测试用例中所有字符串 $A$ 的长度之和不超过 $2 \times 10^6$。

对于每个测试用例，输出一行一个整数，表示答案。

对于第一个样例，最终的指令序列是 ``RULRULRUL``，机器人的轨迹依次为 $(0, 0) \to (1, 0) \to (1, 1) \to (0, 1) \to (1, 1) \to (1, 2) \to (0, 2) \to (1, 2) \to (1, 3) \to (0, 3)$。显然轨迹上最远的点是 $(1, 3)$，曼哈顿距离为 $4$，答案为 $4$。 由 ChatGPT 5 翻译