题解：P10137 [USACO24JAN] Walking in Manhattan G

· · 题解

思路分析

思路真的非常的清奇，好题。部分参考这篇题解。先提示一下，一种正解是倍增。

这道题的突破口是奶牛转向的条件。从奶牛第一次转向起，如果他转向，那意味着它遇到了一条与他方向不同，正好出入的奇偶性不同不同的道路。

到这里，我们仍然看不到倍增的影子。硬要说有的话，你可以选择找出所有的交叉点的下一个点。但是交叉点的个数是 O(n^2) 的，显然接受不了。

但是我们容易发现，当奶牛下一次走向同方向的道路时，其奇偶性必然会发生改变。

有了上面的结论，横纵就先对独立了，也就是说我们可以考虑倍增了。

对于每一条边，记录出他的下 2^j 条与他间隔为奇数的道路出现的位置。由于上述性质，当在 x 方向走到后 2^i 条边时，y 方向也必然走到了后 2^i 条边的位置。

因此我们可以考虑先走到下一个路口上，然后倍增快速寻找最后一次能够走到二者均改变的路口。最后考虑一下剩余的距离对应的位移即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, r[200005][19], c[200005][19];
vector<int> h, v; char o;
inline int ps(const vector<int>& v, int p) {
    return lower_bound(v.begin(), v.end(), p) - v.begin();
}
inline void query(int x, int y, int d) {
    int hp = ps(h, y), vp = ps(v, x), a = 0, lp;
    if (y != h[hp])
        if (d + y > h[hp]) d -= h[hp] - y, a += h[hp] - y;
        else return void(cout << x << " " << d + y << endl);
    if (x != v[vp])
        if (d + x > v[vp])d -= v[vp] - x, a += v[vp] - x;
        else return void(cout << x + d << " " << y << endl);
    //正确性：题目保证了初始点在道路上，这也就意味着以上两个if至多会进入其中的一个。
    for (int k = 18, ad; ~k; k--) {
        int nh = r[hp][k], nv = c[vp][k];
        if ((ad = v[nv] - v[vp] + h[nh] - h[hp]) > d)continue;
        d -= ad, a += ad, hp = nh, vp = nv;
        //不管你先走v还是先走h，都一定会走到下一个奇偶性不同的十字路口
        //因此，在这一步，可以优先保时复，直接向后跳就完事了
    }
    //此时已经跳到了最后一次能暴力走的路口，需要直接处理了。
    //注意到我们一直在跳路口，现在的位置也是一个路口。
    if (a & 1)
        //奇数步，向北走
        //如果走不到下一个奇偶性变化的点就在当前路
        //否则在拐角后的某个位置
        if ((v[lp = c[vp][0]] - v[vp] < d) && (d -= v[lp] - v[vp]))
            return void(cout << v[lp] << " " << h[hp] + d << endl);
        else return void(cout << v[vp] + d << " " << h[hp] << endl);
    //类似于向北走的思路
    if ((h[lp = r[hp][0]] - h[hp] < d) && (d -= h[lp] - h[hp]))
        return void(cout << v[vp] + d << " " << h[lp] << endl);
    else return void(cout << v[vp] << " " << h[hp] + d << endl);
}
signed main() {//写在前面：有参考3qdyj2s2的代码
    ios::sync_with_stdio(0); cin >> n >> m;
    for (int i = 1, p; i <= n; ++i)
        (cin >> o >> p, o != 'V' ? h : v).emplace_back(p);
    sort(h.begin(), h.end()); sort(v.begin(), v.end());
    h.emplace_back(2.1e9), v.emplace_back(2.1e9);
    for (int i = 0; i != 19; i++)
        r[h.size() - 1][i] = h.size() - 1,//谨防越界
        c[v.size() - 1][i] = v.size() - 1;//直接暴力跳回是好方法
    for (int i = h.size() - 2; i >= 0; i--) {
        r[i][0] = (h[i] + h[i + 1] & 1 ? i + 1 : r[i + 1][0]);
        //检验是否 h[i] 与 h[i + 1] 奇偶性不同
        //不同就是下一个点作为转折点
        //否则就是下一个点的下一个奇偶性不同的点
        for (int j = 1; j != 19; j++) r[i][j] = r[r[i][j - 1]][j - 1];
    }
    for (int i = v.size() - 2; i >= 0; i--) {
        c[i][0] = (v[i] + v[i + 1] & 1 ? i + 1 : c[i + 1][0]);
        //道理同上
        for (int j = 1; j != 19; j++) c[i][j] = c[c[i][j - 1]][j - 1];
    }
    for (int i = 1, x, y, d; i <= m; ++i)
        cin >> x >> y >> d, query(x, y, d);
}//能快速想到这是倍增的题的人也是真的厉害