ooliver

P6399 [COI 2008] TAMNICA

ooliver OI

P6399 [COI 2008] TAMNICA

在没有打破墙的时候，任意两点 x,y 的距离应该是 |x-y|，所以走破了的墙一定是最优的，那我们就可以把起点、终点和打破了的墙的两侧作为关键点跑一遍最短路。

现在问题在于怎么求墙的另一侧，如图：

我们把数字按 2,4,6,8,⋯ 的长度分组，每一组又分为左右两个部分。

设当前数字为 x，x 所在的组为 c，那就满足 c2-c+1[PARSE ERROR: Undefined("Command(\"le\")")]x[PARSE ERROR: Undefined("Command(\"le\")")]c2+c，解得 $c=\lfloor \frac{\sqrt{4x-3}+1}{2}\rfloor $。观察图不难发现，如果 x 在当前组的左边部分，那墙后面的数字就应该是 x-(4c-5)；如果 x 在当前组的右边部分，那墙后面的数字就应该是 x-(4c-3)，就可以得到代码：

C++

int geta(int x){
    int c=((int)(sqrtl(4*x-3))+1)/2;
    int l=c*c-c+1,r=c*c+c;
    if(x*2

`int geta(int x){
    int c=((int)(sqrtl(4*x-3))+1)/2;
    int l=c*c-c+1,r=c*c+c;
    if(x*2l+r) return x-(4*c-5);
    else return x-(4*c-3);
}`

之后就是建图，因为关键点比较大，所以要把关键点存下来后离散化：

C++

a[++n]=1,b[n]=1;
a[++n]=ed,b[n]=ed;
for(int i=1;i>x;
    y=geta(x);
    a[++n]=x,b[n]=x,a[++n]=y,b[n]=y;
}
sort(b+1,b+1+n);

`a[++n]=1,b[n]=1;
a[++n]=ed,b[n]=ed;
for(int i=1;ik;i++){
    int x,y;
    cin>>x;
    y=geta(x);
    a[++n]=x,b[n]=x,a[++n]=y,b[n]=y;
}
sort(b+1,b+1+n);`

然后建边，破了的墙的两侧直接连边权为 1 的边，然后所有关键点排序一下，相邻的连边：

C++

for(int i=3;i

`for(int i=3;in;i+=2){
    int x=lower_bound(b+1,b+1+n,a[i])-b,y=lower_bound(b+1,b+1+n,a[i+1])-b;
    g[x].push_back({y,1});
    g[y].push_back({x,1});
}
for(int i=2;in;i++){
    g[i].push_back({i-1,b[i]-b[i-1]});
    g[i-1].push_back({i,b[i]-b[i-1]});
}`

最后跑一边最短路，输出答案即可。

完整代码：

C++

#include
using namespace std;

#define int long long
const int N=2e5+5;
int ed,k,n;
int a[N],b[N],dis[N];
struct node{
    int v,w;
    bool operatorx.w;}
};
vector g[N];

int geta(int x){
    int c=((int)(sqrtl(4*x-3))+1)/2;
    int l=c*c-c+1,r=c*c+c;
    if(x*2 q;
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    q.push({1,0});
    while(q.size()){
        int u=q.top().v,d=q.top().w;
        q.pop();
        if(d>dis[u]) continue;
        for(auto x:g[u]){
            int v=x.v,w=x.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({v,d+w});
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>ed>>k;
    a[++n]=1,b[n]=1;
    a[++n]=ed,b[n]=ed;
    for(int i=1;i>x;
        y=geta(x);
        a[++n]=x,b[n]=x,a[++n]=y,b[n]=y;
    }
    sort(b+1,b+1+n);
    for(int i=3;i

`#include
using namespace std;

#define int long long
const int N=2e5+5;
int ed,k,n;
int a[N],b[N],dis[N];
struct node{
    int v,w;
    bool operatorconst node &x)const{return w>x.w;}
};
vectornode> g[N];

int geta(int x){
    int c=((int)(sqrtl(4*x-3))+1)/2;
    int l=c*c-c+1,r=c*c+c;
    if(x*2l+r) return x-(4*c-5);
    else return x-(4*c-3);
}

void dj(){
    priority_queuenode> q;
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    q.push({1,0});
    while(q.size()){
        int u=q.top().v,d=q.top().w;
        q.pop();
        if(d>dis[u]) continue;
        for(auto x:g[u]){
            int v=x.v,w=x.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                q.push({v,d+w});
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>ed>>k;
    a[++n]=1,b[n]=1;
    a[++n]=ed,b[n]=ed;
    for(int i=1;ik;i++){
        int x,y;
        cin>>x;
        y=geta(x);
        a[++n]=x,b[n]=x,a[++n]=y,b[n]=y;
    }
    sort(b+1,b+1+n);
    for(int i=3;in;i+=2){
        int x=lower_bound(b+1,b+1+n,a[i])-b,y=lower_bound(b+1,b+1+n,a[i+1])-b;
        g[x].push_back({y,1});
        g[y].push_back({x,1});
    }
    for(int i=2;in;i++){
        g[i].push_back({i-1,b[i]-b[i-1]});
        g[i-1].push_back({i,b[i]-b[i-1]});
    }
    dj();
    coutdis[lower_bound(b+1,b+1+n,ed)-b];
    return 0;
}`