题解：P10137 [USACO24JAN] Walking in Manhattan G

_Weslie_ · 2025-11-25 16:29:06 · 题解

比较有意思的题。

Solution P10137

下文称“关键点”为横纵路径的交点。

不难考虑暴力。

1. 每次先把奶牛从初始点挪到一个关键点。
2. 根据时间开始模拟到下一个关键点（称一次这个过程为“挪一步”）。
3. 最后如果剩余的时间不足以把奶牛挪到关键点就用完时间 t 然后输出。

会 T 飞。

考虑一头奶牛，如果它已经在一个关键点了且时间已经确定，那么它接下来的移动路径是确定的，这个显然。

进一步的，如果时间的奇偶性确定了，那么移动路径同样确定，因为你往哪边挪只与时间的奇偶性相关。

这个时候你其实可以想倍增了。因为路径确定，所以你可以设 f_{x,y,0/1,j} 表示 (x,y) 这个关键点，初始时间奇偶性为 0/1，挪了 j 步之后到哪个位置。

于是我们第二步的复杂度被降到 \operatorname{O}(\log n)，但是 MLE 了，因为你显然不可能把 n^2 的倍增数组开下来。

你再想想呢？你想想两次转向会发生什么？

你会发现两次转向又回到了之前的方向！

而且如果我们以两次转向为一个单位考虑，行和列就可以正式被拆开了——因为你预处理倍增数组的时候，你需要保证第 i 行转移到的行一定会使得从第 i 行结束到目标行开始奇偶性变化（否则你无法走到目标行）。

然后还有一个性质：你开始走上走右，在轮数一定是 2 的倍数的情况下，对最终位置其实并没有影响。

可以参考这张图上的蓝线和红线理解。

那么可以设 f_{i,j} 表示第 i 条竖线，连转 2^j 个两次后，到达第几条竖线；g_{i,j} 表示第 i 条横线，连转 2^j 个两次后，到达第几条横线。

然后转移倍增数组就是

初值设为第一个使得两条竖线间距离差为奇数的点即可，具体上说，设 dis 为第 i 和 i+1 条竖线的距离差，则：

结束第二步之后你有可能剩下一部分 t 还可以走，直接暴力跑就行，容易发现最多会暴力 3 次。

复杂度 \operatorname{O}(q\log n)。代码实现较难。

::::success[Code]

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define ls (now<<1)
#define rs ((now<<1)|1)
#define int long long
using namespace std;
const int N=200005;
const int mod=1000000007;
const int intinf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
int lx[N],ly[N];
int f[N][19],g[N][19];
int n,q,lenx,leny;
pair<int,int> solve(int x,int y,int t){
    pair<int,int>ans=make_pair(0,0);
    int ut=0;
    int px=lower_bound(lx+1,lx+lenx+1,x)-lx,py=lower_bound(ly+1,ly+leny+1,y)-ly;
    if(lx[px]!=x&&ly[py]==y){
        if(t<=(lx[px]-x)){
            ans.fi=x+t;
            ans.se=y;
            return ans;
        }
        t-=(lx[px]-x);
        ut+=(lx[px]-x);
        x=lx[px];
    } 
    if(ly[py]!=y&&lx[px]==x){
        if(t<=(ly[py]-y)){
            ans.fi=x;
            ans.se=y+t;
            return ans;
        }
        t-=(ly[py]-y);
        ut+=(ly[py]-y);
        y=ly[py];
    }
    for(int i=18;i>=0;i--){
        int nx=f[px][i],ny=g[py][i];
        int sum=(lx[nx]-lx[px])+(ly[ny]-ly[py]);
        if(t>=sum){
            ut+=sum;
            t-=sum;
            px=nx;py=ny; 
        }
    }
    x=lx[px];y=ly[py];
    if(t==0){
        return make_pair(x,y);
    }
    for(;;){
        if((ut)&1){
            int sum=(lx[px+1]-lx[px]);
            if(t<=sum){
                x+=t;
                return make_pair(x,y);
            }
            t-=sum;
            ut+=sum;
            x=lx[px+1];px++;
        }
        else{
            int sum=(ly[py+1]-ly[py]);
            if(t<=sum){
                y+=t;
                return make_pair(x,y);
            }
            t-=sum;
            ut+=sum;
            y=ly[py+1];
            py++;
        }
    }
    return make_pair(x,y);
} 
signed main(){
    fastio;
    cin>>n>>q;
    char ch;
    for(int pos;n;n--){
        cin>>ch>>pos;
        if(ch=='V')lx[++lenx]=pos;
        else ly[++leny]=pos;
    }
    lx[++lenx]=mod*2;ly[++leny]=mod*2;
    sort(lx+1,lx+lenx+1);
    sort(ly+1,ly+leny+1);
    for(int j=0;j<=18;j++){
        f[lenx][j]=lenx;
        g[leny][j]=leny;
    }
    for(int j=0;j<=18;j++){
        for(int i=lenx-1;i>=1;i--){
            if(j==0){
                if((lx[i+1]-lx[i])&1)f[i][0]=i+1;
                else f[i][0]=f[i+1][0]; 
            }
            else f[i][j]=f[f[i][j-1]][j-1];
        }
        for(int i=leny-1;i>=1;i--){
            if(j==0){
                if((ly[i+1]-ly[i])&1)g[i][0]=i+1;
                else g[i][0]=g[i+1][0];
            }
            else g[i][j]=g[g[i][j-1]][j-1];
        }
    }
    for(int x,y,t;q;q--){
        cin>>x>>y>>t;
        pair<int,int>ans=solve(x,y,t);
        cout<<ans.fi<<' '<<ans.se<<'\n';
    }
    return 0;
}

::::