NOIP模拟（20171031）T2 朋友（BZOJ2143 飞飞侠）

时间：2022-12-16 23:48:19

题目链接
BZOJ2143
orz题解
我们引入云端的概念
建立一个包含 n∗m∗(n+m−2) 个点的分层图 G[1⋯n][1⋯m][1⋯n+m−2]
其中 G[n][m][0] 表示街区， G[n][m][h](h>0) 表示一个高为 h 的云端节点
对于任意一个云端节点，有五条权值为0出边，分别指向低一层的相邻云端及正下方的云端，即：
G[x][y][h])→G[x][y][h−1]

G[x][y][h])→G[x−1][y][h−1]

G[x][y][h])→G[x][y−1][h−1]

G[x][y][h])→G[x+1][y][h−1]

G[x][y][h])→G[x][y+1][h−1]

对于地面节点 G[x][y][0] 我们向 G[x][y][a[x][y]] 连一条权值为 b[x][y] 的边

这就相当于地面上有个弹射器能把你发射到 a[x][y] 的高度，然后从空中*降落，每下降一个单位高度，你最多往前后左右移动一个单位（或者不移），最后降落到地面，再弹（自行脑补画面），这样就等价于题目所述的从一个点走到曼哈顿距离不超过 a[i][j] 的点上
然后跑dijkstra即可
代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define BIG 0x3f3f3f3f
using namespace std;
int a[251][251],b[251][251];
int n,m;
int dis[251][251][451];
bool vis[251][251][451];
inline int getint(){
    int x;
    scanf("%d",&x);
    return x;
}
inline void write_char(char c){
    putchar(c);
}
inline void W(int x){
    printf("%d",x);
}
struct pos{
    int a,b,c;
    pos(int a,int b,int c):a(a),b(b),c(c){
    }
    bool operator == (const pos &x2)const{
        return a==x2.a&&b==x2.b&&c==x2.c;
    }
};
struct pii{
    int dis;
    pos po;
    pii(int a,pos b):dis(a),po(b){
    }
    bool operator < (const pii &b)const{
        return b.dis<dis;
    }
};
__gnu_pbds::priority_queue<pii>q;
__gnu_pbds::priority_queue<pii>::point_iterator po[251][251][451];
//priority_queue<pii>q;
inline bool tense(int &a,const int b){
    return a>b?(a=b,true):false;
}
bool check(pos a){
    return a.a<=n&&a.a>=1&&a.b<=m&&a.b>=1;
}
const int xx[10]={0,1,0,-1,0},yy[10]={1,0,-1,0,0};
inline void dijkstra(pos s,pos e1,pos e2){
    q.clear();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int k=0;k<=n+m-2;++k){
                dis[i][j][k]=BIG;
                vis[i][j][k]=0;
                po[i][j][k]=NULL;
            }
        }
    }
    dis[s.a][s.b][s.c]=0;
    po[s.a][s.b][s.c]=q.push(pii(dis[s.a][s.b][s.c],s));
    bool f=0;
    while(!q.empty()){
        pos u=q.top().po;
        q.pop();
        if(vis[u.a][u.b][u.c])continue;
        vis[u.a][u.b][u.c]=1;
        if(u==e1||u==e2){
            if(f)return;
            else f=1;
        }
        //cout<<u.a<<" "<<u.b<<" "<<u.c<<" "<<dis[u.a][u.b][u.c]<<endl;
        if(u.c==0){
            if(dis[u.a][u.b][u.c]+b[u.a][u.b]<dis[u.a][u.b][a[u.a][u.b]]){
                dis[u.a][u.b][a[u.a][u.b]]=dis[u.a][u.b][u.c]+b[u.a][u.b];
                if(po[u.a][u.b][a[u.a][u.b]]!=NULL){
                    q.modify(po[u.a][u.b][a[u.a][u.b]],pii(dis[u.a][u.b][a[u.a][u.b]],pos(u.a,u.b,a[u.a][u.b])));
                }
                else{
                    po[u.a][u.b][a[u.a][u.b]]=q.push(pii(dis[u.a][u.b][a[u.a][u.b]],pos(u.a,u.b,a[u.a][u.b])));
                }
            }
        }
        else{
            for(int i=0;i<6;++i){
                pos v=pos(u.a+xx[i],u.b+yy[i],u.c-1);
                if(check(v)&&dis[v.a][v.b][v.c]>dis[u.a][u.b][u.c]){
                    dis[v.a][v.b][v.c]=dis[u.a][u.b][u.c];
                    if(po[v.a][v.b][v.c]!=NULL){
                        q.modify(po[v.a][v.b][v.c],pii(dis[v.a][v.b][v.c],pos(v.a,v.b,v.c)));
                    }
                    else{
                        po[v.a][v.b][v.c]=q.push(pii(dis[v.a][v.b][v.c],pos(v.a,v.b,v.c)));
                    }
                }
            }
        }
    }
}
int main(){
    n=getint(),m=getint();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            a[i][j]=getint();
            a[i][j]=min(a[i][j],n+m-2);
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            b[i][j]=getint();
        }
    }
    int Xx=getint(),Xy=getint(),Yx=getint(),Yy=getint(),Zx=getint(),Zy=getint();
    pos x=pos(Xx,Xy,0),y=pos(Yx,Yy,0),z=pos(Zx,Zy,0);
    int ansx=0,ansy=0,ansz=0;
    dijkstra(x,y,z);
    ansy+=dis[y.a][y.b][y.c],ansz+=dis[z.a][z.b][z.c];
    dijkstra(y,x,z);
    ansx+=dis[x.a][x.b][x.c],ansz+=dis[z.a][z.b][z.c];
    dijkstra(z,x,y);
    ansx+=dis[x.a][x.b][x.c],ansy+=dis[y.a][y.b][y.c];
    int ans=BIG;
    char c='N';
    /*cout<<ansx<<endl; cout<<ansy<<endl; cout<<ansz<<endl;*/
    if(ansx<ans){
        ans=ansx;
        c='X';
    }
    if(ansy<ans){
        ans=ansy;
        c='Y';
    }
    if(ansz<ans){
        ans=ansz;
        c='Z';
    }
    if(c=='N')write_char('N'),write_char('O');
    else{
        write_char(c);
        write_char('\n');
        W(ans);
    }
    return 0;
}

好，接下来是吐槽时间
标算太慢了！！！
标算太慢了！！！
标算太慢了！！！
空间复杂度 O(n3) ，时间复杂度 O(n3log2n)
来看看我自创的玄学做法
NOIP模拟（20171031）T2 朋友（BZOJ2143 飞飞侠）
暴踩标算有木有
其实思想很简单
我们解绝对值不等式
|x−x1|+|y−y1|≤a[x1][y1]
解得

{x1−y1−a[x1][y1]≤x−y≤x1−y1+a[x1][y1]x1+y1−a[x1][y1]≤x+y≤x1+y1+a[x1][y1]

那我们就得到了 x−y 和 x+y 的范围了，然后就可以线段树优化建边了
具体操作见代码
空间复杂度 O(n2log22n) ，时间复杂度 O(n2log22n⋅log2(n2log22n)) 

#include<bits/stdc++.h>
#define LEN 5000005
#define BIG 100000000000000000ll
using namespace std;
inline int getint(){
    int x=0,p=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')p=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    return x*p;
}
inline void putint(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    static int buf[30];
    int tot=0;
    do{
        buf[tot++]=x%10;
        x/=10;
    }while(x);
    while(tot)putchar(buf[--tot]+'0');
}
int n,m;
struct road{
    int e,nxt,len;
}r[LEN];
int tot=0;
int first[LEN];
inline void creat(int a,int b,int c){
    r[++tot].e=b;
    r[tot].len=c;
    r[tot].nxt=first[a];
    first[a]=tot;
    //cout<<a<<" "<<b<<" "<<c<<endl;
}
int used=0;
namespace seg_in{
    struct seg_in{
        seg_in *ls,*rs;
        int l,r;
        int out;
        seg_in();
        void* operator new(size_t);
    }buf[LEN],*null=buf,*tail=buf;
    seg_in::seg_in():ls(null),rs(null),l(0),r(0),out(0){
    }
    void* seg_in::operator new(size_t size){
        return ++tail;
    }
    void insert(seg_in *&k,int l,int r,int x,int y){
        //cout<<x<<" "<<y<<" "<<l<<" "<<r<<endl;
        if(k==null){
            k=new seg_in();
            k->l=l,k->r=r;
            k->out=x+y;
        }
        if(l==r){
            //cout<<"in"<<x<<" "<<y<<" "<<l<<" "<<r<<endl;
            return;
        }
        int mid=(l+r)/2;
        //cout<<mid<<" "<<x-y<<endl;
        if(x-y+200<=mid)insert(k->ls,l,mid,x,y);
        else insert(k->rs,mid+1,r,x,y);
    }
    void create_roads(seg_in *a,seg_in *b,int c){
        if(a==null||b==null)return;
        creat(a-buf,b-buf,c);
        create_roads(a->ls,b->ls,c);
        create_roads(a->rs,b->rs,c);
    }
}
namespace seg_out{
    struct seg_out{
        seg_in::seg_in *root;
        seg_out *ls,*rs;
        int l,r;
        seg_out();
        void* operator new(size_t);
    }buf[LEN],*null=buf,*tail=buf;
    seg_out::seg_out():root(seg_in::null),ls(null),rs(null),l(0),r(0){
    }
    void* seg_out::operator new(size_t size){
        return ++tail;
    }
    inline void insert(seg_out *&k,int l,int r,int x,int y){
        if(k==null){
            k=new seg_out();
            k->l=l,k->r=r;
        }
        seg_in::insert(k->root,1,399,x,y);
        if(l==r){
            //cout<<"out"<<x<<" "<<y<<" "<<l<<endl;
            return;
        }
        int mid=l+r>>1;
        if(x+y<=mid)insert(k->ls,l,mid,x,y);
        else insert(k->rs,mid+1,r,x,y);
    }
}
#define pos(i,j) ((i-1)*m+j+used)
seg_out::seg_out *root=seg_out::null;
inline void insert(int x,int y){
    seg_out::insert(root,2,400,x,y);
}
inline void make_roads(seg_in::seg_in *cur,bool x){
    if(cur->l==cur->r&&x){
        int plus=cur->out,sub=cur->l;
        int x=(plus+sub)/2-100,y=plus-x;
        //cout<<plus<<" "<<sub<<" "<<x<<" "<<y<<endl;
        creat(cur-seg_in::buf,pos(x,y),0);
    }
    if(cur->ls!=seg_in::null){
        creat(cur-seg_in::buf,cur->ls-seg_in::buf,0);
        make_roads(cur->ls,x);
    }
    if(cur->rs!=seg_in::null){
        creat(cur-seg_in::buf,cur->rs-seg_in::buf,0);
        make_roads(cur->rs,x);
    }
}
inline void make_roads(seg_out::seg_out *cur){
    make_roads(cur->root,cur->l==cur->r);
    if(cur->ls!=seg_out::null){
        seg_in::create_roads(cur->root,cur->ls->root,0);
        make_roads(cur->ls);
    }
    if(cur->rs!=seg_out::null){
        seg_in::create_roads(cur->root,cur->rs->root,0);
        make_roads(cur->rs);
    }
}
int a[205][205],b[205][205];
void query(seg_in::seg_in *cur,int x,int y,int a,int b){
    if(cur==seg_in::null)return;
    int l=x-y+200-a,r=x-y+200+a;
    if(l<=cur->l&&cur->r<=r){
        creat(pos(x,y),cur-seg_in::buf,b);
        return;
    }
    int mid=(cur->l+cur->r)>>1;
    if(l<=mid)query(cur->ls,x,y,a,b);
    if(mid<r)query(cur->rs,x,y,a,b);
}
void query(seg_out::seg_out *cur,int x,int y,int a,int b){
    if(cur==seg_out::null)return;
    int l=x+y-a,r=x+y+a;
    //cout<<l<<" "<<r<<" "<<cur->l<<" "<<cur->r<<endl;
    if(l<=cur->l&&cur->r<=r){
        query(cur->root,x,y,a,b);
        return;
    }
    int mid=(cur->l+cur->r)>>1;
    if(l<=mid)query(cur->ls,x,y,a,b);
    if(mid<r)query(cur->rs,x,y,a,b);
}
int totused=0;
long long dis[LEN];
bool vis[LEN];
inline void dijkstra(int s,int e1,int e2){
    for(int i=1;i<=totused;++i){
        dis[i]=BIG;
        vis[i]=0;
    }
    dis[s]=0;
    typedef pair<long long,int> pii;
    priority_queue<pii,vector<pii>,greater<pii> >q;
    bool f=0;
    q.push(make_pair(dis[s],s));
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u])continue;
        if(u==e1||u==e2){
            if(f)return;
            else f=1;
        }
        for(int i=first[u];i;i=r[i].nxt){
            int v=r[i].e;
            if(dis[u]+r[i].len<dis[v]){
                dis[v]=dis[u]+r[i].len;
                q.push(make_pair(dis[v],v));
            }
        }
    }
}
int main(){
    n=getint(),m=getint();
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            a[i][j]=getint();
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            b[i][j]=getint();
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            //cout<<i<<" "<<j<<endl;
            insert(i,j);
        }
    }
    used=seg_in::tail-seg_in::buf;
    //cout<<used<<endl;
    make_roads(root);
    //cout<<"success";
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            query(root,i,j,a[i][j],b[i][j]);
        }
    }
    totused=used+n*m;
    int Xx=getint(),Xy=getint(),Yx=getint(),Yy=getint(),Zx=getint(),Zy=getint();
    int x=pos(Xx,Xy),y=pos(Yx,Yy),z=pos(Zx,Zy);
    int ansx=0,ansy=0,ansz=0;
    dijkstra(x,y,z);
    ansy+=dis[y],ansz+=dis[z];
    dijkstra(y,x,z);
    ansx+=dis[x],ansz+=dis[z];
    dijkstra(z,x,y);
    ansx+=dis[x],ansy+=dis[y];
    int ans=BIG;
    char c='N';
    if(ansx<ans){
        ans=ansx;
        c='X';
    }
    if(ansy<ans){
        ans=ansy;
        c='Y';
    }
    if(ansz<ans){
        ans=ansz;
        c='Z';
    }
    if(c=='N')cout<<"NO";
    else{
        cout<<c<<"\n"<<ans;
    }
    return 0;
}
标签：

相关文章