题解 | #铁道双子的大追捕#

题目链接

铁道双子的大追捕

题目描述

在一个由 $N$ 节车厢组成的火车上，旺仔哥哥（W）和橘望妹妹（M）正在进行一场追逐。我们需要判断 W 是否有办法始终不被 M 抓住。

M 的移动：M 的移动轨迹是固定的，在 $1$ 到 $N$ 号车厢之间来回匀速移动，每分钟移动一节车廂。
W 的移动：
- 列车行驶时（状态'0'）：W 可以移动到相邻车厢或留在原地。
- 列车停靠时（状态'1'）：W 可以移动到任意一节车廂。
抓捕规则：W 的行动总是在 M 之前完成。如果在任意时刻两人位于同一车厢，则 W 被抓住。

解题思路

本题看似复杂，需要考虑所有可能的移动方案，但实际上可以通过模拟一个聪明的 贪心策略 来解决。我们不需要使用动态规划来维护所有可能的位置，而是假设旺仔哥哥（W）在每一步都采取当前的最优解。

该贪心策略的核心思想如下：

橘望妹妹（M）的移动：M 的移动是完全固定的，我们可以轻松地在模拟中计算出她每分钟的位置。
旺仔哥哥（W）的贪心选择：
- 当列车停靠时 ('1'): 这是 W 最好的机会。由于他可以移动到任意车厢，最优选择是在 M 移动之后，立刻瞬移到 M 刚刚离开 的那节车厢。这步操作不仅绝对安全，而且能让他为后续的移动做好准备。
- 当列车行驶时 ('0'): W 的移动受限，只能在相邻车厢间移动。此时，他的最佳策略是尽可能地远离 M。具体来说：
  - 如果 W 所在的车厢号 m 大于 M 的车厢号 k，他应该朝车尾（n 号车厢）移动。
  - 如果 m 小于等于 k，他应该朝车头（1 号车厢）移动。在每一分钟，他都会朝着这个既定的大方向移动一格。

模拟过程

我们按照时间顺序，一分钟一分钟地进行模拟：

在第 t 分钟，首先根据列车状态（s[t-1]）和上述贪心策略，更新 W 的位置 m。
然后，更新 M 的位置 k。
检查 m 和 k 是否相等。如果相等，说明 W 在第 t 分钟被抓住，模拟结束。
如果直到最后一分钟两人位置都未重合，则 W 成功逃脱。

这个方法的关键在于，我们证明了（或相信）这个贪心策略覆盖了最优路径，从而避免了复杂的动态规划。算法的时间复杂度仅为 $\mathcal{O}(T)$ ，其中 $T$ 是总时长，效率非常高。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long m, k; // 使用 long long 防止策略移动时超出 int 范围
    int d;
    cin >> n >> m >> k >> d;
    string s;
    cin >> s;

    if (d == 0) d = -1;

    int t_len = s.length();
    for (int t = 1; t <= t_len; ++t) {
        // W 移动
        if (s[t - 1] == '1') { // 停靠
            // W 的策略是等 M 移动后，跳到 M 之前的位置
            long long m_prev_k = k;
            if (k == 1 && d == -1) d = 1;
            else if (k == n && d == 1) d = -1;
            k += d;
            m = m_prev_k;
        } else { // 行驶
            if (m > k) {
                m = min((long long)n, m + 1);
            } else {
                m = max(1LL, m - 1);
            }
            // M 移动
            if (k == 1 && d == -1) d = 1;
            else if (k == n && d == 1) d = -1;
            k += d;
        }

        if (m == k) {
            cout << "No" << endl;
            cout << t << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long m = sc.nextLong();
        long k = sc.nextLong();
        int d = sc.nextInt();
        String s = sc.next();

        if (d == 0) d = -1;

        int t_len = s.length();
        for (int t = 1; t <= t_len; t++) {
            // W 移动
            if (s.charAt(t - 1) == '1') { // 停靠
                long m_prev_k = k;
                if (k == 1 && d == -1) d = 1;
                else if (k == n && d == 1) d = -1;
                k += d;
                m = m_prev_k;
            } else { // 行驶
                if (m > k) {
                    m = Math.min(n, m + 1);
                } else {
                    m = Math.max(1, m - 1);
                }
                // M 移动
                if (k == 1 && d == -1) d = 1;
                else if (k == n && d == 1) d = -1;
                k += d;
            }

            if (m == k) {
                System.out.println("No");
                System.out.println(t);
                return;
            }
        }
        System.out.println("Yes");
    }
}

import sys

def solve():
    # 为了同时处理单行和多行输入，我们一次性读取所有输入并按空白分割
    # 这模拟了 C++ cin 和 Java Scanner 的行为
    tokens = sys.stdin.read().split()
    
    # 在某些环境下，如果没有输入，tokens 会为空
    if not tokens:
        return

    n, m, k, d = int(tokens[0]), int(tokens[1]), int(tokens[2]), int(tokens[3])
    s = tokens[4]

    if d == 0:
        d = -1

    t_len = len(s)
    for t in range(1, t_len + 1):
        # W 移动
        if s[t - 1] == '1':  # 停靠
            m_prev_k = k
            if k == 1 and d == -1:
                d = 1
            elif k == n and d == 1:
                d = -1
            k += d
            m = m_prev_k
        else:  # 行驶
            if m > k:
                m = min(n, m + 1)
            else:
                m = max(1, m - 1)
            
            # M 移动
            if k == 1 and d == -1:
                d = 1
            elif k == n and d == 1:
                d = -1
            k += d

        if m == k:
            print("No")
            print(t)
            return
            
    print("Yes")

solve()

算法及复杂度

算法：贪心策略模拟
时间复杂度：我们只需要对整个时间序列进行一次遍历，每次循环中的操作都是常数时间，因此总时间复杂度为 $\mathcal{O}(T)$ ，其中 $T$ 是字符串 s 的长度。
空间复杂度：我们只需要几个变量来存储当前的状态，因此空间复杂度为 $\mathcal{O}(1)$ 。