题解：P10275 [USACO24OPEN] Walking Along a Fence B

cff_0102 · 2024-09-30 19:30:16 · 题解

发现 x,y 小于等于 1000，可以直接把每个点前的第一个柱子位置和编号存下来。再用一个前缀和数组记录下每两个柱子之间的距离，即代码中的 dis。

要求出两个点之间的距离，可以先找到对应的栅栏的起始点，然后计算它们之间的距离 d，即 dis[y]-dis[x]（如果 y 在 x 前面则需要交换这两个点），再分别计算这两个点到栅栏起始点的距离 dis_1,dis_2，距离就是 d-dis_1+dis_2。

最后只需要输出 \max(d-dis_1+dis_2,dis_n-(d-dis_1+dis_2)) 即可。

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
int cald(int xa,int ya,int xb,int yb){
    return abs(xa-xb+ya-yb);
}
struct point{
    int x,y,n;
}pt[200005],lp[1005][1005];
int dis[200005];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,p;cin>>n>>p;
    for(int i=1;i<=p;i++){
        cin>>pt[i].x>>pt[i].y;
        pt[i].n=i;
    }
    pt[0]=pt[p];
    for(int i=1;i<=p;i++){
        int lx=pt[i-1].x,ly=pt[i-1].y,nx=pt[i].x,ny=pt[i].y;
        dis[i]=dis[i-1]+cald(lx,ly,nx,ny);
        if(lx==nx){
            if(ly<ny){
                for(int j=ly;j<ny;j++){
                    lp[nx][j].x=lx;
                    lp[nx][j].y=ly;
                    lp[nx][j].n=i-1;
                }
            }else{
                for(int j=ly;j>ny;j--){
                    lp[nx][j].x=lx;
                    lp[nx][j].y=ly;
                    lp[nx][j].n=i-1;
                }
            }
        }else{
            if(lx<nx){
                for(int j=lx;j<nx;j++){
                    lp[j][ny].x=lx;
                    lp[j][ny].y=ly;
                    lp[j][ny].n=i-1;
                }
            }else{
                for(int j=lx;j>nx;j--){
                    lp[j][ny].x=lx;
                    lp[j][ny].y=ly;
                    lp[j][ny].n=i-1;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        int xa,xb,ya,yb;cin>>xa>>ya>>xb>>yb;
        int lxa=lp[xa][ya].x,lxb=lp[xb][yb].x,lya=lp[xa][ya].y,lyb=lp[xb][yb].y;
        int lna=lp[xa][ya].n,lnb=lp[xb][yb].n;
        if(lna>lnb){
            swap(xa,xb);
            swap(ya,yb);
            swap(lxa,lxb);
            swap(lya,lyb);
            swap(lna,lnb);
        }
        int dis1=dis[lnb]-dis[lna];
        int disa=cald(xa,ya,lxa,lya);
        int disb=cald(xb,yb,lxb,lyb);
        int ans=abs(dis1-disa+disb);
        cout<<min(ans,dis[p]-ans)<<endl;
    }
    return 0;
}