官方题解|机器人Ⅰ

题目大意

现在机器人有一种移动方式，问机器人从某一个起点到达 $l_i$ $r_i$ 位置。

题解思路

问题 $1$ 我们现在机器人从 $p_0$ 开始,走了一圈到达 $p_1$ ，那么 $p_1$ 的位置会在哪里？
我们设白色节点的数目为 $t$ ,那么我们可以到达 $(p_0 + t) \mod n$ 位置。因为这次的移动，本质上是相当与 $robot$ 顺时针走了 $t$ 步。

问题 $2$ 现在我们机器人最终到达了 $l_j , r_j$ ,那么对于 $l_j 和 r_j$ 有什么限制?
其中一个节点应该是最后一步走到的，我们设最后一步走的是顺时针，那么 $r_j$ , 这个点似乎就相当于未生效。 这样我们可以找到这一圈的起始点 $p_1$。
只后，我们可以从 $p_1$ 开始模拟，机器人是否可以到底 $l_j, r_j$ 。

时间复杂度 O($n \times m$)

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
int vis[3002];

int dis(int f, int to, int n, int t) {
    memset(vis, 0, sizeof vis);
    int now = 0;
    int x = 3002;
    while (f != to && x--) {
        f = (f + t) % n;
        now += n;
    }
    if (x <= 0) return -1;
    return now;
}

pair<int, int> run(int l, int r, int L, int R, int n, string &s) {
    int p = l;
    if (l != r) {
        int k = 0;
        int l_t = l;
        while (l_t != r) {
            if (s[l_t] == '0') k++;
            l_t = (l_t + 1) % n;
        }
        if (s[l_t] == '0') k++;
        p = (L + k) % n;
    }
    l = r = p;
    int step = n;
    int tt = 0;
    int las = l;

    while (step--) {
        if (l == L && r == R) {
            return {p, tt};
        }
        if (s[las] == '1') {
            r++;
            r %= n;
            las = r;
        } else {
            l--;
            l = (l + n) % n;
            las = l;
        }
        tt++;
    }
    return {-1, -1};
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    int t = 0;
    for (auto i: s) if (i == '1') t++;


    for (int i = 1; i <= m; i++) {
        int p_i, l_i, r_i;
        cin >> p_i >> l_i >> r_i;
        p_i--, l_i--, r_i--;
        if (l_i == r_i) {
            cout << dis(p_i, l_i, n, t) << endl;
        } else {
            //最后一步是向左走
            auto [pp,tt] = run((l_i + 1) % n, r_i, l_i, r_i, n, s);
            int z = -1;
            if (pp != -1) {
                int dis2 = dis(p_i, pp, n, t);
                if (dis2 != -1) {
                    z = dis2 + tt;
                }
            }
            auto [pp1,tt1] = run((l_i) % n, (r_i - 1 + n) % n, l_i, r_i, n, s);
            if (pp1 != -1) {
                int dis2 = dis(p_i, pp1, n, t);
                if (dis2 != -1) {
                    if (z == -1) {
                        z = dis2 + tt1;
                    } else {
                        z = min(z, dis2 + tt1);
                    }
                }
            }
            cout << z << endl;
        }
    }
}