P6399 [COI 2008] TAMNICA 在没有打破墙的时候，任意两点 x,y 的距离应该是 |x-y|，所以走破了的墙一定是最优的，那我们就可以把起点、终点和打破了的墙的两侧作为关键点跑一遍最短路。 现在问题在于怎么求墙的另一侧，如图： 我们把数字按 2,4,6,8,\cdots 的长度分组，每一组又分为左右两个部分。 设当前数字为 x，x 所在的组为 c，那就满足 c^2-c+1\le x\le c^2+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; }`
P6399 [COI 2008] TAMNICA
笔记