[NOI2019] 弹跳
2022/2/8 23:50:19
本文主要是介绍[NOI2019] 弹跳,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
板题二号?
题目
UOJ
洛谷
LOJ
讲解
可以发现这个就是K-D树优化最短路建图板题?
K-D树上的点对应一个矩形区间,当然还有平凡的 \(n\) 个点就表示单点。
然后跑 dijkstra,因为 dijkstra 的点只会出队一次,所以其实挺快的。
注意这道题卡空间,所以我们不能显示地把图建出来,要在 dijkstra 过程中在线求。
交洛谷,过了,交 UOJ,T了。十分疑惑,于是去 U群问:
很快 EI 就回复我了:
那没办法了啊,人家专门卡的。(现在知道我为什么前面打问号了吧)
于是老师换了个链接,改成 LOJ,我就拿到了一血。/xyx
不是很会算时间复杂度。
代码
LOJ要freopen
//12252024832524 #include <bits/stdc++.h> #define TT template<typename T> using namespace std; typedef long long LL; const int MAXN = 70005 << 1; const int INF = 0x3f3f3f3f; int n,m,w,h,dis[MAXN]; int nxt[2] = {1,0}; bool vis[MAXN]; LL Read() { LL x = 0,f = 1;char c = getchar(); while(c > '9' || c < '0'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x*10) + (c^48);c = getchar();} return x * f; } TT void Put1(T x) { if(x > 9) Put1(x/10); putchar(x%10^48); } TT void Put(T x,char c = -1) { if(x < 0) putchar('-'),x = -x; Put1(x); if(c >= 0) putchar(c); } TT T Max(T x,T y){return x > y ? x : y;} TT T Min(T x,T y){return x < y ? x : y;} TT T Abs(T x){return x < 0 ? -x : x;} struct tec{int t,L,R,D,U;}cur; vector<tec> G[MAXN]; struct spot { int x,d; bool operator < (const spot &px)const{ return d > px.d; } }tmp; priority_queue<spot> q; int tot,rt,mode; struct point{int x,y;}; bool operator < (point A,point B){if(!mode) return A.x < B.x;return A.y < B.y;} struct Info{point p;int ID;}c[MAXN]; bool operator < (Info A,Info B){return A.p < B.p;} #define lc t[x].ch[0] #define rc t[x].ch[1] struct node { Info info; point l,r; int ch[2]; }t[MAXN]; void up1(int x,int son) { if(!son) return; t[x].l.x = Min(t[x].l.x,t[son].l.x); t[x].l.y = Min(t[x].l.y,t[son].l.y); t[x].r.x = Max(t[x].r.x,t[son].r.x); t[x].r.y = Max(t[x].r.y,t[son].r.y); } void up(int x) { t[x].l = t[x].r = t[x].info.p; up1(x,lc); up1(x,rc); } void Build(int &x,int l,int r,int now) { x = ++tot; mode = now; int mid = (l+r) >> 1; nth_element(c+l,c+mid,c+r+1); t[x].info = c[mid]; if(l < mid) Build(lc,l,mid-1,nxt[now]); if(mid < r) Build(rc,mid+1,r,nxt[now]); up(x); } int nowdis; void inq(int x,int d){if(d < dis[x]) q.push(spot{x,dis[x] = d});} void Add_Edge(int x) { if(vis[x]) return; if(cur.L <= t[x].l.x && t[x].r.x <= cur.R && cur.D <= t[x].l.y && t[x].r.y <= cur.U) {inq(x,nowdis); return;} if(cur.L <= t[x].info.p.x && t[x].info.p.x <= cur.R && cur.D <= t[x].info.p.y && t[x].info.p.y <= cur.U) inq(t[x].info.ID,nowdis); if(t[x].l.x > cur.R || t[x].r.x < cur.L || t[x].l.y > cur.U || t[x].r.y < cur.D) return; if(lc) Add_Edge(lc); if(rc) Add_Edge(rc); } int main() { freopen("jump.in","r",stdin); freopen("jump.out","w",stdout); n = Read(); m = Read(); w = Read(); h = Read(); for(int i = 1;i <= n;++ i) c[i].p.x = Read(),c[i].p.y = Read(),c[i].ID = i; for(int i = 1;i <= m;++ i) { int pos = Read(),t = Read(),L = Read(),R = Read(),D = Read(),U = Read(); G[pos].emplace_back(tec{t,L,R,D,U}); } tot = n; Build(rt,1,n,0); for(int i = 1;i <= tot;++ i) dis[i] = INF; q.push(spot{1,dis[1] = 0}); while(!q.empty()) { tmp = q.top(); q.pop(); int x = tmp.x; if(tmp.d > dis[x]) continue; vis[x] = 1; if(x <= n) { for(int i = 0,len = G[x].size();i < len;++ i) cur = G[x][i],nowdis = dis[x]+cur.t,Add_Edge(rt); } else { nowdis = dis[x]; inq(t[x].info.ID,nowdis); if(lc) inq(lc,nowdis); if(rc) inq(rc,nowdis); } } for(int i = 2;i <= n;++ i) Put(dis[i],'\n'); return 0; }
这篇关于[NOI2019] 弹跳的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)