1 条题解

  • 0
    @ 2026-4-30 14:57:41

    这道题是真的人少但还是挺好的题目！

    题目介绍

    给定初始点与结束点，以及一些矩阵，有一小球从起始点出发，只能平行于坐标轴移动，不能穿过矩阵中间，一次移动需要碰到矩阵边缘或边界才停止，求到结束点所需的最小的折线数。

    解题思路

    首先，看到矩阵的范围，先把其离散化，又可以发现小球的移动只能是通过起点或终点或沿矩阵边缘通过。考虑建图，在图上跑 01bfs。由此思路后，继续能发现这样可走的边其实不多，并且这些边即是通过延长至碰到边界或是碰到矩阵所形成的边，可以通过扫描线加上 set 求出。但是边上节点数量却依旧很多，直接建图会导致 TLE。但继续思考，发现其实建图，是在边与边的交点可连，而在排序后，这样的连边就是区间连边，可以用线段树优化建图去做，这样以后，再考虑一下第一杆和最后一杆与在矩阵里走时的关系，这道题就做完了。

    时间复杂度 O(nlog⁡n)O(n\log n)。

    既然这道题需要线段树优化建图，那就再说一下线段树优化的做法，这里的线段树的叶子节点看为图上的原点，而非叶子节点则看为新造的虚点，所有的虚点连向它的子节点即可，而原本一个点连向几个连续的点的操作可以看成直接连向它们的线段树上的父节点，以父节点代替子树中的点，这样就可以建出图，简单可证时间复杂度为 O(log⁡n)O(\log n)。

    若有错误，请各位大佬指正。

    Tips

    1. 在建图时要用链式前向星存图，若用 vector 存图的话容易爆空间。
    2. 在离散化时，要把 xx 轴和 yy 轴分开进行离散化，不然会导致爆时间或者空间。

    代码

    #include<bits/stdc++.h>
#define int long long
#define pl p<<1
#define pr p<<1|1
#define up(i,x,y) for(int i=x;i<=y;i++)
#define dn(i,y,x) for(int i=y;i>=x;i--)
#define mst(x,y) memset(x,y,sizeof x)
#define D(x) cout<<#x<<": "<<x<<endl;
#define DE(x) cout<<#x<<": "<<x<<" ";
#define MAXSIZE 1<<21
using namespace std;
namespace lry{
	char buf[MAXSIZE],*p1=buf,*p2=buf;
	char pbuf[MAXSIZE],*pp=pbuf;
	inline int gc(){
		#if faster
			return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
		#else
			return getchar();
		#endif
	}
	inline void pc(const char &c){
		#if faster
			if(pp-pbuf==MAXSIZE) fwrite(pbuf,1,MAXSIZE,stdout),pp=pbuf;*pp++=c;
		#else
			putchar(c);
		#endif
	}
	inline void read(double& rdx){double t=0;int x=0,s=0,f=1;char c;do c=gc();while(!isdigit(c)&&c!='-'&&c!='.');if (c=='-')f=-1,c=gc();while(isdigit(c)&&c!='.')x=(c^48)+(x<<1)+(x<<3),c=gc();if(c=='.')c=gc();else{rdx=x*f;return;}while(c>='0'&&c<='9')t=t*10+(c^48),s=-~s,c=gc();while(s--)t/=10;rdx=(x+t)*f;}
	inline void read(string& s){char ch=gc();while(ch=='\n')ch=gc();while(ch!='\n'){s+=ch;ch=gc();}}
	inline void read(int &x){int ret=0,f=0;char ch=gc();while(!isdigit(ch)){if(ch=='-')f=1;ch=gc();}while(isdigit(ch)){ret=(ret<<1)+(ret<<3)+(ch^48);ch=gc();}x=(f?-ret:ret);}
	inline void write(int x){if(x<0)pc('-'),x=-x;if(x>9)write(x/10);pc(x%10+48);}
	template<typename t,typename ...T>
	inline void read(t &x,T&...y){read(x),read(y...);}
	inline void writeln(int x){write(x),pc('\n');}
	inline void writetr(int x){write(x),pc(' ');}
}
using namespace lry;
constexpr int N=100000+10,M=30000000+10,inf=0x3f3f3f3f3f3f3f3f;
int sx,sy,ex,ey;
int n,a[N],b[N],c[N],d[N],t[N*2],tot,m1,m2,rt[N<<3],dis[M],cnt;
array<int,3> hang[N*2],lie[N*2];
vector<int> del[N*2],add[N*2];
int he[M],nxt[M*2],to[M*2],val[M*2],ccnt;
set<int> s;
bool vis[M];
inline void addedge(int x,int y,int v){
	ccnt++;
	nxt[ccnt]=he[x];
	to[ccnt]=y;
	val[ccnt]=v;
	he[x]=ccnt;
}
inline void change(int p,int L,int R,int x,int k){
	if(L==R){
		rt[p]=k;
		return;
	}
	int mid=(L+R)>>1;
	if(x<=mid) change(pl,L,mid,x,k);
	else change(pr,mid+1,R,x,k);
	rt[p]=++cnt;
	if(rt[pl]) addedge(rt[p],rt[pl],0);
	if(rt[pr]) addedge(rt[p],rt[pr],0);
}
inline void update(int p,int L,int R,int l,int r,int x){
	if(l<=L&&R<=r){
		if(rt[p]) addedge(x,rt[p],1);
		return;
	}
	int mid=(L+R)>>1;
	if(l<=mid) update(pl,L,mid,l,r,x);
	if(r>mid) update(pr,mid+1,R,l,r,x);
}
signed main(){
	read(sx,sy,ex,ey,n);
	for(int i=1;i<=n;i++) read(a[i],b[i],c[i],d[i]);
	n++; a[n]=sx; b[n]=sx; c[n]=sy; d[n]=sy;
	n++; a[n]=ex; b[n]=ex; c[n]=ey; d[n]=ey;
	tot=0;
	for(int i=1;i<=n;i++){
		t[++tot]=a[i]; t[++tot]=b[i];
	}
	sort(t+1,t+1+tot);
	tot=unique(t+1,t+1+tot)-t-1;
	sx=lower_bound(t+1,t+1+tot,sx)-t;
	ex=lower_bound(t+1,t+1+tot,ex)-t;
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(t+1,t+1+tot,a[i])-t;
		b[i]=lower_bound(t+1,t+1+tot,b[i])-t;
	}
	tot=0;
	for(int i=1;i<=n;i++){
		t[++tot]=c[i]; t[++tot]=d[i];
	}
	sort(t+1,t+1+tot);
	tot=unique(t+1,t+1+tot)-t-1;
	sy=lower_bound(t+1,t+1+tot,sy)-t;
	ey=lower_bound(t+1,t+1+tot,ey)-t;
	for(int i=1;i<=n;i++){
		c[i]=lower_bound(t+1,t+1+tot,c[i])-t;
		d[i]=lower_bound(t+1,t+1+tot,d[i])-t;
	}
	for(int i=1;i<=n;i++){
		if(i<=n-2) add[c[i]].push_back(i);
		del[d[i]].push_back(i);
	}
	for(int i=1;i<=n*2;i++){
		for(int j:del[i]) s.erase(a[j]),s.erase(b[j]);
		for(int j:del[i]){
			auto it1=s.upper_bound(a[j]),it2=s.lower_bound(b[j]);
			int x,y;
			if(it1==s.begin()) x=1;
			else x=*(--it1);
			if(it2==s.end()) y=n*2;
			else y=*it2;
			hang[++m1]={i,x,y};
		}
		for(int j:add[i]){
			auto it1=s.upper_bound(a[j]),it2=s.lower_bound(b[j]);
			int x,y;
			if(it1==s.begin()) x=1;
			else x=*(--it1);
			if(it2==s.end()) y=n*2;
			else y=*it2;
			hang[++m1]={i,x,y};
		}
		for(int j:add[i]) s.insert(a[j]),s.insert(b[j]);
	}
	for(int i=1;i<=n*2;i++) del[i].clear(),add[i].clear();
	s.clear();
	for(int i=1;i<=n;i++){
		if(i<=n-2) add[a[i]].push_back(i);
		del[b[i]].push_back(i);
	}
	for(int i=1;i<=n*2;i++){
		for(int j:del[i]) s.erase(c[j]),s.erase(d[j]);
		for(int j:del[i]){
			auto it1=s.upper_bound(c[j]),it2=s.lower_bound(d[j]);
			int x,y;
			if(it1==s.begin()) x=1;
			else x=*(--it1);
			if(it2==s.end()) y=n*2;
			else y=*it2;
			lie[++m2]={i,x,y};
		}
		for(int j:add[i]){
			auto it1=s.upper_bound(c[j]),it2=s.lower_bound(d[j]);
			int x,y;
			if(it1==s.begin()) x=1;
			else x=*(--it1);
			if(it2==s.end()) y=n*2;
			else y=*it2;
			lie[++m2]={i,x,y};
		}
		for(int j:add[i]) s.insert(c[j]),s.insert(d[j]);
	}
	for(int i=1;i<=n*2;i++) del[i].clear(),add[i].clear();
	sort(hang+1,hang+1+m1); sort(lie+1,lie+1+m2);
	cnt=m1+m2;
	for(int i=1;i<=m2;i++){
		add[lie[i][1]].push_back(i); del[lie[i][2]].push_back(i);
	}
	for(int i=1,j=1;i<=n*2;i++){
		for(int k:add[i]) change(1,1,m2,k,k+m1);
		while(j<=m1&&hang[j][0]<=i){
			int x=lower_bound(lie+1,lie+1+m2,(array<int,3>){hang[j][1],0,0})-lie;
			int y=upper_bound(lie+1,lie+1+m2,(array<int,3>){hang[j][2],0,0})-lie-1;
			update(1,1,m2,x,y,j);
			j++;
		}
		for(int k:del[i]) change(1,1,m2,k,0);
	}
	for(int i=1;i<=n*2;i++) del[i].clear(),add[i].clear();
	s.clear();
	memset(rt,0,sizeof rt);
	for(int i=1;i<=m1;i++){
		add[hang[i][1]].push_back(i); del[hang[i][2]].push_back(i);
	}
	for(int i=1,j=1;i<=n*2;i++){
		for(int k:add[i]) change(1,1,m1,k,k);
		while(j<=m2&&lie[j][0]<=i){
			int x=lower_bound(hang+1,hang+1+m1,(array<int,3>){lie[j][1],0,0})-hang;
			int y=upper_bound(hang+1,hang+1+m1,(array<int,3>){lie[j][2],0,0})-hang-1;
			update(1,1,m1,x,y,j+m1);
			j++;
		}
		for(int k:del[i]) change(1,1,m1,k,0);
	}
	for(int i=1;i<=cnt;i++) dis[i]=inf;
	deque<int> q;
	for(int i=1;i<=m1;i++){
		if(hang[i][0]==sy&&hang[i][1]<=sx&&sx<=hang[i][2]){
			q.push_back(i); dis[i]=1;
		}
	}
	for(int i=1;i<=m2;i++){
		if(lie[i][0]==sx&&lie[i][1]<=sy&&sy<=lie[i][2]){
			q.push_back(i+m1); dis[i+m1]=1;
		}
	}
	while(!q.empty()){
		int x=q.front(); q.pop_front();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=he[x];i;i=nxt[i]){
			int y=to[i],w=val[i];
			if(dis[y]>dis[x]+w){
				dis[y]=dis[x]+w;
				if(w) q.push_back(y);
				else q.push_front(y);
			}
		}
	}
	int ans=inf;
	for(int i=1;i<=m1;i++){
		if(hang[i][0]==ey&&hang[i][1]<=ex&&ex<=hang[i][2]) ans=min(ans,dis[i]);
	}
	for(int i=1;i<=m2;i++){
		if(lie[i][0]==ex&&lie[i][1]<=ey&&ey<=lie[i][2]) ans=min(ans,dis[i+m1]);
	}
	writeln(ans);
	#if faster
		fwrite(pbuf,1,pp-pbuf,stdout);
		pp=pbuf;
	#endif
	return 0;
}
    • 1

    [JOI Open 2017] 高尔夫

    信息

    ID
    10173
    时间
    5000ms
    内存
    1024MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者
    1. Language
    2. 兼容模式
    3. 主题
    3. Worker 0, 6ms
    4. Powered by Hydro v5.0.1 Community