B. Robot Program 详细题解

问题理解

我们有一个机器人在数轴上运动，初始位置为 $x$（$x \neq 0$），有一条长度为 $n$ 的指令序列 $s$（由 $L$ 和 $R$ 组成）。

机器人按顺序执行指令（每秒一条），但有一个关键规则： 每当机器人到达位置 $0$ 时，指令计数器立即重置，即重新从 $s$ 的第一条指令开始执行。

如果机器人执行完所有 $n$ 条指令后，当前位置不是 $0$，它就停止运行。

我们需要计算在接下来的 $k$ 秒内，机器人进入 $0$ 点的次数。

注意：“进入”意味着到达 $0$ 点的那一瞬间算一次，包括初始时刻吗？
根据题意，机器人从 $x$（$x \neq 0$）开始，所以初始不在 $0$。第一次进入 $0$ 是在某次移动之后。

---

核心观察

这个问题可以分解成几个阶段：

阶段 1：第一次到达 $0$ 点

从初始位置 $x$ 出发，按顺序执行指令，直到第一次到达 $0$ 点。

设经过 $t_1$ 秒（即执行了 $t_1$ 条指令）后，机器人第一次到达 $0$。

如果在整个第一轮执行中从未到达 $0$，那么：

• 执行完 $n$ 条指令后，机器人必然停在某个非零位置
• 因为没到过 $0$，所以不会重置，之后就没有指令可执行了
• 因此机器人会在 $n$ 秒后停止，之后 $k$ 秒内不会再动
• 答案就是 $0$（因为从未进入 $0$）

所以首先要检查：是否存在 $t_1$ 使得 $1 \le t_1 \le n$，并且执行前 $t_1$ 条指令后位置变为 $0$。

---

阶段 2：重置后的循环行为

一旦机器人第一次到达 $0$，它会立即重置指令指针，从 $s$ 的第一条指令开始重新执行。

此时机器人在 $0$ 点，执行一轮完整的 $n$ 条指令后，它会到达某个新的位置，记作 $d$（$d$ 是执行完整个 $s$ 后的位移，即 $R$ 的数量减去 $L$ 的数量）。

那么从 $0$ 出发，执行一轮 $n$ 条指令的路径如下：

• 从 $0$ 开始
• 执行第 $1$ 条指令，位置变为 $p_1$
• 执行第 $2$ 条指令，位置变为 $p_2$
• ...
• 执行第 $n$ 条指令，位置变为 $d$

注意：在这 $n$ 步过程中，可能会多次经过 $0$ 点。
这些经过 $0$ 的时刻（除了起点 $0$ 本身）也是“进入 $0$ 点”的事件。

---

阶段 3：周期重复

从 $0$ 开始执行完一轮 $n$ 条指令后：

• 如果 $d = 0$，那么机器人在一轮结束后回到 $0$，下一轮又从 $0$ 开始，行为完全重复
• 如果 $d \neq 0$，那么一轮结束后机器人在 $d$（非零），然后因为没有到达 $0$（因为结束位置不是 $0$），所以不会重置，机器人停止

等等——这里要小心！

根据规则：只有到达 $0$ 时才重置。
如果一轮结束时位置是 $d \neq 0$，那么：

• 执行完第 $n$ 条指令后，机器人在 $d$，不是 $0$
• 没有触发重置
• 没有更多指令可执行（因为执行完了整个序列）
• 所以机器人停止

这意味着：如果机器人从 $0$ 出发执行一轮后没有回到 $0$，那么它只会执行这一轮，然后停止。

因此，如果要产生多次进入 $0$ 的循环，必须满足 $d = 0$，即一轮的净位移为 $0$。

---

更准确的分析

实际上，标程采用了一种更巧妙的方法：

1. 先尝试到达 $0$
   从 $x$ 开始模拟，直到要么到达 $0$，要么用完 $n$ 条指令且没到 $0$。
   如果 $n$ 条指令用完还没到 $0$，答案就是 $0$。

2. 如果到达了 $0$
   设到达 $0$ 用了 $t_1$ 秒。此时：

   • 已经进入 $0$ 一次（计入答案）
   • 剩余时间 $k' = k - t_1$ 秒

3. 重置后，从 $0$ 开始
   从 $0$ 开始执行指令序列，找出第一次（非起点）到达 $0$ 的位置。
   设从 $0$ 出发，经过 $c$ 条指令后第一次回到 $0$（$c$ 可能在 $1$ 到 $n$ 之间，也可能不存在）。

   如果存在这样的 $c$，那么：

   • 每 $c$ 秒，机器人就会进入 $0$ 一次
   • 在剩余 $k'$ 秒中，这样的周期有 $\left\lfloor \frac{k'}{c} \right\rfloor$ 次
   • 加上之前的一次，总共 $1 + \left\lfloor \frac{k'}{c} \right\rfloor$ 次

   如果不存在这样的 $c$（即从 $0$ 出发后永远不会再回到 $0$），那么只有第一次到达 $0$ 的那一次，答案为 $1$。

---

标程解析

标程的代码逻辑如下：

li n, x, k;
cin >> n >> x >> k;
string s;
cin >> s;
// 第一阶段：从 x 出发，尝试到达 0
for (int i = 0; i < n; ++i) {
    x += (s[i] == 'L' ? -1 : +1);
    --k;           // 消耗 1 秒
    if (!x) break; // 到达 0，停止模拟
}
li ans = 0;
if (!x) {  // 如果成功到达 0
    ans = 1;  // 第一次进入 0
    // 第二阶段：从 0 开始，找回到 0 的最小周期
    for (int i = 0; i < n; ++i) {
        x += (s[i] == 'L' ? -1 : +1);
        if (!x) {
            ans += k / (i + 1);  // 剩余时间能完成多少个完整周期
            break;
        }
    }
}
cout << ans << '\n';

关键点：

• 第一个循环模拟到第一次到达 $0$，同时消耗时间
• 如果成功到达，$ans$ 初始为 $1$，$x$ 此时为 $0$
• 第二个循环从 $0$ 开始，找第一次回到 $0$ 的位置（步数为 $i+1$）
• 一旦找到，用剩余时间 $k$ 除以周期长度，得到额外进入次数
• 注意：第二个循环开始时 $x$ 已经是 $0$，所以执行第一条指令后 $x$ 变成 $\pm 1$，然后继续

---

公式总结

设：

• $t_1$ = 从 $x$ 到第一次到达 $0$ 所需的步数（如果存在）
• 如果 $t_1$ 不存在，答案为 $0$
• 否则，设 $c$ = 从 $0$ 出发后，第一次回到 $0$ 所需的步数（$1 \le c \le n$，如果存在）
• 如果 $c$ 不存在，答案为 $1$
• 如果 $c$ 存在，答案为 $1 + \left\lfloor \frac{k - t_1}{c} \right\rfloor$

其中 $k$ 是总时间，实际剩余时间在模拟中已经通过 --k 处理，所以代码中直接用 k / (i+1)。

---

复杂度分析

• 每个测试用例模拟最多 $2n$ 步（两次遍历 $s$）
• 所有测试用例的 $n$ 之和不超过 $2\times10^5$，所以总复杂度 $O(\sum n)$
• 完全满足时间限制 $2$ 秒

---

示例验证

以第二个示例为例： $n=2, x=-1, k=8, s=\text{RL}$

第一阶段：

• 初始 $x=-1$，$k=8$
• 指令1: $R$，$x = -1+1 = 0$，到达 $0$，$k=7$，停止 $t_1=1$，$ans=1$

第二阶段：

• 从 $x=0$ 开始（代码中 $x$ 已被重置为 $0$）
• 指令1: $R$，$x=1$（不是 $0$）
• 指令2: $L$，$x=0$，到达 $0$，步数 $i+1=2$
• $ans = 1 + \lfloor 7/2 \rfloor = 1+3 = 4$ ✅

---

总结

这道题的关键在于：

1. 区分“第一次到达 $0$”和“从 $0$ 出发后的循环周期”
2. 理解重置规则导致只有净位移为 $0$ 才能产生多次进入
3. 通过模拟找到最小周期 $c$，然后用除法计算完整周期数

标程通过两遍遍历巧妙地解决了问题，避免了显式处理循环和净位移的复杂判断。