P6399 题解

· · 题解

模拟赛结束后来写一发题解。

nflsoj || luogu

Solution

若想得知墙两面的数字分别是什么，我们先需要找到方阵的规律。由 小学数学 题目提供的图片可以看出，每一圈都对应一个完全平方数。

若以偶数平方数为一圈，设该偶数为 k，其墙对面的数字为 j，则当当前数字 n \ne 4 且 n \ne k^2 时，有 j=(k-2)^2 + (n-k^2-1) - 2 \times \left \lfloor \frac{n-k^2}{k+1} \right \rfloor。

对于墙壁塌陷的地方，可以理解为两点之间有一条距离为 1 的边。因为所有相邻点之间都有一条距离为 1 的边，所以走塌陷旁的点以及终点一定最优。此时转化为最短路问题，可以用 map 解决。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    char c=getchar();
    ll x=0;
    bool f=0;
    while(!isdigit(c)){
        f^=!(c^45);
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    if(f) x=-x;
    return x;
}
const int N=1e5+10,M=2e5+10;
struct edge{
    int next,v;
    ll w;
}e[3*M];
map<ll,int>mp;
int head[M],cnt,m,u,v,s,pos;;
ll n,dis[M],d,w,a[N],b[N],p[M];
struct node{
    int u;
    ll d;
    bool operator <(const node& r) const{return d>r.d;}
}Q;
void add(int u,int v,ll w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
priority_queue<node> q;
ll g,h,j,k;
ll check(ll g){
    k=sqrt(g);
    if(k%2==1) k--;
    if(g==4) return 1;
    if(g==k*k) return (k-2)*(k-2)+1;
    h=(g-k*k)/(k+1);
    h*=2;
    j=(k-2)*(k-2)+(g-k*k-1)-h;
    return j;
}
int main(){
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    memset(dis,0x3f,sizeof dis);
    n=read();
    scanf("%d",&m);
    mp[1]=1;
    p[++pos]=1;
    mp[n]=1;
    p[++pos]=n;
    for(int i=1;i<=m;i++){
        a[i]=read();
        b[i]=check(a[i]);
        if(!mp[a[i]]){
            mp[a[i]]=1;
            p[++pos]=a[i];
        }
        if(!mp[b[i]]){
            mp[b[i]]=1;
            p[++pos]=b[i];
        }
    }
    sort(p+1,p+pos+1);
    for(int i=1;i<=pos;i++) mp[p[i]]=i;
    for(int i=1;i<=pos-1;i++){
        add(i,i+1,p[i+1]-p[i]);
        add(i+1,i,p[i+1]-p[i]);
    }
    for(int i=1;i<=m;i++){
        add(mp[a[i]],mp[b[i]],1ll);
        add(mp[b[i]],mp[a[i]],1ll);
    }
    dis[1]=0;
    q.push((node){1,0});
    while(!q.empty()){
        Q=q.top();
        q.pop();
        u=Q.u,d=Q.d;
        if(d!=dis[u]) continue;
        for(int i=head[u];i;i=e[i].next){
            v=e[i].v;
            w=e[i].w;
            if(dis[u]+w<dis[v]){
                dis[v]=dis[u]+w;
                q.push((node){v,dis[v]});
            }
        }
    }
    printf("%lld",dis[mp[n]]);
}