题解：P6399 [COI2008] TAMNICA

· · 题解

P6399 解题报告

前言

模拟赛 T3，写题解以寄之。

思路分析

首先这个形式就很像最短路。

考虑直接模拟填出矩阵，然后相邻点的连边，边权均为 1，然后 BFS 从 1 到 n 的最短路。复杂度为 O(n+m)。

这样做可以获得 50 的高分！

考虑优化这个建图过程。

发现图上大部分的点都是无用的，考虑将这些点去掉。

首先可以仿照 P2239，对于每一个 b，求出它对应的 a。

然后在图上只保留 1,n，以及每次操作的 a,b。

这样总点数就是 O(m) 的。

然后对于每一对 (a,b)，连一条边权为 1 的无向边，对于每一对编号相邻的关键点，连一条边权为两点编号差值的无向边。

直接跑出 1 到 n 的最短路，就做完了。

总体复杂度 O(m\log m)。

代码实现

50 分暴力 bfs 代码。

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int a[1005][1005];
int n,m,len,total,x,y,b,c,bx,by;
struct node{
    int x,y;
}pos[2000005];
int head[2000005],nxt[5000005],target[5000005],tot;
void add(int x,int y){
    tot++;
    nxt[tot]=head[x];
    head[x]=tot;
    target[tot]=y; 
}
int dis[2000005];
queue<int> q;
void bfs(){
    dis[len*len]=1;
    q.push(len*len);
    while(q.size()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=target[i];
            if(!dis[y]){
                dis[y]=dis[x]+1;
                q.push(y);
            }  
        }
    }
}
int main(){
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0); 
    cin>>n;
    len=sqrt(n)+1;
    total=a[++x][++y]=1;
    while (total<len*len){
        while(a[x][y+1]==0 && y+1<=len) a[x][++y]=++total,pos[total]=(node){x,y};
        while(a[x+1][y]==0 && x+1<=len) a[++x][y]=++total,pos[total]=(node){x,y};
        while(a[x][y-1]==0 && y-1>=1) a[x][--y]=++total,pos[total]=(node){x,y};
        while(a[x-1][y]==0 && x-1>=1) a[--x][y]=++total,pos[total]=(node){x,y};

    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>b;
        b=len*len-b+1;
        bx=pos[b].x;
        by=pos[b].y;
        for(int j=0;j<4;j++){
            if(a[x+dx[j]][y+dy[j]]){
                if(a[bx+dx[j]][by+dy[j]]>a[bx][by]+1){
                    c=a[bx+dx[j]][by+dy[j]];
                    break;
                }
            }
        }
        add(b,c);
        add(c,b);
    }
    for(int i=2;i<=len*len;i++){
        add(i,i-1);
        add(i-1,i);
    }
    bfs();
    cout<<dis[len*len-n+1]-1;
    return 0;
}

100 分正解。

可以使用 map 存点的编号，这样更好写一些。


#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,b[500005],a[500005];
map<int,int> dfn;
vector<int> v;
int geta(int b){
    int k=sqrt(b);
    if(k&1) k--;
    if(b==4) return 1;
    if(b==k*k) return (k-2)*(k-2)+1;
    int h=(b-k*k)/(k+1);
    h*=2;
    int j=(k-2)*(k-2)+(b-k*k-1)-h;
    return j;
}
int head[500005],nxt[2000005],targetx[2000005],targetw[2000005],tot;
void add(int x,int y,int w){
    tot++;
    nxt[tot]=head[x];
    head[x]=tot;
    targetx[tot]=y;
    targetw[tot]=w;
}
int dis[500005],vis[500005];
struct node{
    int x,dis;
    bool operator<(const node &a)const{
        return a.dis<dis;
    }
};
priority_queue<node> q;
void dij(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    q.push((node){s,dis[s]});
    while(q.size()){
        int x=q.top().x;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=nxt[i]){
            int y=targetx[i],w=targetw[i];
            if(dis[x]+w<dis[y]){
                dis[y]=dis[x]+w;
                q.push((node){y,dis[y]}); 
            }
        }
    } 
}
signed main(){
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>b[i];
        a[i]=geta(b[i]);
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    v.push_back(1);
    v.push_back(n);
    sort(v.begin(),v.end());
    unique(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        dfn[v[i]]=i+1;
    }
    for(int i=1;i<v.size();i++){
        add(dfn[v[i]],dfn[v[i-1]],abs(v[i]-v[i-1]));
        add(dfn[v[i-1]],dfn[v[i]],abs(v[i-1]-v[i]));
    }
    for(int i=1;i<=m;i++){
        add(dfn[a[i]],dfn[b[i]],1);
        add(dfn[b[i]],dfn[a[i]],1);
    }
    dij(dfn[1]);
    cout<<dis[dfn[n]];
    return 0;
}

后记

翻盘题。