锐客网

  1. 首页 > it技术 > >

洛谷P5471 NOI2019弹跳

题解

1～8号测试点，32分做法
\qquad 暴力加边，跑 D i j s t r a Dijstra Dijstra
9～13号测试点 20分做法
\qquad 加边的时候二分或直接把点存进一个 m a p map map,暴力跑 D i j s t r a Dijstra Dijstra
14～18号测试点 20分做法
\qquad 出门左转线段树优化建图模板题
或许是实现起来最简单还不用卡常的100分做法：线段树套 s e t set set \qquad 首先这题需要发现2个很有用的性质：

  • 性质 1 1 1，用 D i j s t r a Dijstra Dijstra跑最短路时，对于每个点，都只会在堆中弹出1次
  • 【洛谷P5471 NOI2019弹跳】性质 2 2 2，对于每个弹跳装置，通过这一个弹跳装置到达的矩形中所有城市需要的时间相同（不是矩形中每个城市的最短路相同，而是通过这个装置到达它们的时间相同）
\qquad观察性质 2 2 2，我们发现可以把整个矩形放入 D i j s t r a Dijstra Dijstra中，对于每个堆顶弹出的矩形，我们只需要取其中任意一个之前没出现过的城市，都能保证这是该点的最短路径。那么，我们就把这题转换成了实现如下操作：
找到特定矩形中任意一个没有出现过的城市，跑最短路 \qquad 至于为什么只取矩形中的一个点，因为本蒟蒻太菜了，感觉不好操作，也只是常数问题。
\qquad 那么这题就被我们转换成了一道支持插入、删除任意一点、在某特定范围中查找第一个点的的二维数据结构+ D i j s t r a Dijstra Dijstra的题目。
\qquad 因为我们需要找到第一个未出现过的城市的确切位置，那么明显需要二分，所以外面就选择线段树。里面的比较随意，支持删除、可以动态开空间就行。而这题卡空间，不能用二维线段树，于是我们可以选择线段树套平衡树，为了方便，直接上 s e t set set。
时空复杂度分析 \qquad 因为小蒟蒻的写法很不优秀,可能要查询(m+n)次，线段树查询最多 l o g log log个区间，每个区间用set查询，时间复杂度 O ( ( m + n ) l o g 2 2 n ) O((m+n)log_2^2n) O((m+n)log22?n)。插入城市时，深度为 l o g ( n ) log(n) log(n),往线段树插入n个城市，所以空间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
丑陋的代码：
// luogu-judger-enable-o2 #include using namespace std; inline int read(){ int a=0; char c=getchar(); while(c>57 or c<48)c=getchar(); while(47b.t; } }; //矩阵的结构体，记录时间和大小 vectoredge[MN]; //记录每个城市的弹跳装置指向的矩形 priority_queueQ; //优先队列 void Insert(int x,int l,int r,int loc,int id,int y){ //x坐标和线段树的编号重了，改成了loc int mid=(l+r)>>1; num[x].insert(P(id,loc,y)); sum[x]++; if(l==r)return; if(mid>=loc)Insert(Ls,l,mid,loc,id,y); else Insert(Rs,mid+1,r,loc,id,y); }//在线段树中插入城市 void del(int x,int l,int r,int loc,int id,int y){ int mid=(l+r)>>1; num[x].erase(num[x].find(P(id,loc,y))); sum[x]--; if(l==r)return; if(mid>=loc)del(Ls,l,mid,loc,id,y); else del(Rs,mid+1,r,loc,id,y); }//在线段树中删除城市 int ask(int x,int l,int r,int b,int e,int L,int R){ if(!sum[x]||l>e||rR||y[tmp]>1; int tmp=ask(Ls,l,mid,b,e,L,R); if(tmp) return tmp; return ask(Rs,mid+1,r,b,e,L,R); }//找出区间中第一个点 void Dij(){ while(!Q.empty())Q.pop(); for(int i=1; i<=n; ++i)f[i]=INF; f[1]=0; Q.push(Mat(0,x[1],x[1],y[1],y[1])); while(!Q.empty()){ Mat w=Q.top(); int cur=ask(1,1,W,w.l,w.r,w.d,w.u); if(!cur){Q.pop(); continue; }//一个矩形里没有城市时再删除 del(1,1,W,x[cur],cur,y[cur]); f[cur]=w.t; cnt++; if(cnt==n)break; //松弛完直接break，因为后面的查询也需要log^2的时间但是肯定不会对结果造成影响 for(int i=0; i

    推荐阅读


    上一篇：数据库入门|Oracle--《基于Oracle的SQL优化》第一章总结回顾

    下一篇：数据库入门|Oracle--《基于Oracle的SQL优化》第二章总结回顾