正经题解｜测试机器人

题目解析

由于每个操作需要的权重都是一样的，所以本质上就是求 $\bf{多源无权有向图最短路}$，对于本题而言就是求从 $i (1 \le i \le n)$ 移出 $[1, n]$ 的最少步数。

令 dist[i] 表示从 $i$ 移出 $[1, n]$ 的最小步数。

我们可以使用记忆化深度优先搜索来得到 $dist[i]$。

对于每个 $[l, r]$ 的询问，遍历求出 $max(dist[i])$ 和 $min(dist[i])(l \le i \le r, dist[i] \ne \infty)$ 即可。

AC代码

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 1e5;

int n, m, dist[N], vis[N];

string s;

int get_pos(const string &s, int i) {
    if (s[i] == 'R') return i + 1;
    if (s[i] == 'G') return i + 2;
    return i - 3;
}

int dfs(int u) {
    if (u < 0 or u >= n) return 0;
    if (vis[u]) return dist[u];
    vis[u] = 1;
    dist[u] = dfs(get_pos(s, u));
    if (dist[u] >= 0) ++dist[u];
    return dist[u];
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> m >> s;
    memset(dist, -1, sizeof dist);
    for (int i = 0; i < n; ++i)
        if (vis[i] == 0) dfs(i);
    for (int i = 0; i < m; ++i) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        int minv = INT_MAX, maxv = 0;
        for (int j = l; j <= r; ++j)
            if (dist[j] > 0) {
                minv = min(minv, dist[j]);
                maxv = max(maxv, dist[j]);
            }
        if (minv == INT_MAX and maxv == 0)
            cout << "-1 -1\n";
        else
            cout << minv << ' ' << maxv << '\n';
    }
    return 0;
}

复杂度分析

记忆化深搜求出 $dist[i]$ 的时间复杂度为 $O(n)$;
对于每个查询统计答案时间复杂度为 $O(n)$；
总的时间复杂度为 $O(nm)$。