CF1681E Labyrinth Adventures题解

分析

图中矩阵被分为了 n n n 层，不难看出：

同一层中任意两个位置之间的最短路都是它们的曼哈顿距离 ( ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ |x_1-x_2|+|y_1-y_2| ∣x1−x2∣+∣y1−y2∣)。这个距离一定是最优的。也就是说要去同一层中另一个位置，绕到别的层肯定不会更优。

我们假设每次都是从较低的层走到较高的层，每次移动最多只能向上一层，结合上面结论，我们可以得出:

每一次移动一定是在当前层中移动或向上一层，不可能向下走。

n n n 是 1 0 5 10^5 105 级别的，肯定不能将图中每个位置存下来，因为层与层之间只有两个固定入口相同（暂且称之为门）。所以如果我们要从第 i i i 层某位置走到第 j j j 层某位置，一定要先到第 i i i 层的一个门，向上走到第 j − 1 j-1 j−1 层的一个门，再上到第 j j j 层走到终点。起点和终点部分的曼哈顿距离可以直接计算，所以只要记录门与门之间的最短路即可。而门的数量是 O ⁡ ( n ) operatorname O(n) O(n) 的。

解法 1

考虑用朴素的方法求解最短路。 d i s t i , j , 0 / 1 , 0 / 1 dist_{i,j,0/1,0/1} disti,j,0/1,0/1 表示以第 i i i 层某个门作为起点，到第 j j j 层某个门的最短路。每次询问都要固定起点完整跑一遍，单次复杂度达到 O ⁡ ( n ) operatorname O(n) O(n)。

我们可以用倍增算法优化这个问题。设 d i s t i , j , 0 / 1 , 0 / 1 dist_{i,j,0/1,0/1} disti,j,0/1,0/1 表示以第 i i i 层某个门作为起点，到第 i + 2 j i+2^j i+2j 层某个门的最短路。这样对于单个起点，跑一遍最短路的复杂度是 O ⁡ ( log ⁡ n ) operatorname O(log n) O(logn)，每次询问都可以把原区间分解成不超过 log ⁡ n log n logn 个已知区间求解。

转化成多个区间后，维护 d p i , 0 / 1 dp_{i,0/1} dpi,0/1 表示考虑到第 i i i 个区间，当前层的 0 / 1 0/1 0/1 号门到起点的距离，处理出终点的距离即可。

时间复杂度： O ⁡ ( n log ⁡ n ) operatorname O(nlog n) O(nlogn)
空间复杂度： O ⁡ ( n log ⁡ n ) operatorname O(nlog n) O(nlogn)

Code

#include 
#define ll long long
#define pb push_back
#define pii pair
#define mp make_pair
#define F first
#define S second
#define y1 woshishabi
using namespace std;
const ll INF=1000000000000000008;
int n,m,lg[100005],to[100005][25];
ll x[100005][2],y[100005][2],dist[100005][25][2][2];
ll dis(ll x1,ll y1,ll x2,ll y2)//曼哈顿距离
{
	return abs(x1-x2)+abs(y1-y2);
}
ll solve(int s,int k1,int g,int k2)//求两个门之间的距离
{
	ll dp[2][2];
	dp[0][k1]=0;
	dp[0][k1^1]=dis(x[s][k1],y[s][k1],x[s][k1^1],y[s][k1^1]);
	int cur=s,pre=0,now=1;
	for(int i=lg[g-s]-1;i>=0;i--)//分解成多个区间
		if (to[cur][i]<=g)
		{
			for(int k=0;k<2;k++)
				dp[now][k]=min(dp[pre][0]+dist[cur][i][0][k],dp[pre][1]+dist[cur][i][1][k]);
			cur=to[cur][i];
			swap(pre,now);
		}
	return dp[pre][k2];
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
	cin>>n;
	for(int i=0;i>x[i][0]>>y[i][0]>>x[i][1]>>y[i][1],--x[i][0],--x[i][1],--y[i][0],--y[i][1];
	for(int i=1;i<=n;i++)//倍增的常数优化
		lg[i]=lg[i-1]+(1<
		to[i][0]=i+1;
		for(int j=0;j<2;j++)
		{
			dist[i][0][0][j]=dis(x[i][0]+1,y[i][0],x[i+1][j],y[i+1][j])+1;
			dist[i][0][1][j]=dis(x[i][1],y[i][1]+1,x[i+1][j],y[i+1][j])+1;
		}
	}
	for(int i=n-1;i>=0;i--)//预处理倍增数组
		for(int j=1;j<=lg[n-1-i];j++)
		{
			to[i][j]=to[to[i][j-1]][j-1];
			for(int k=0;k<2;k++)
			for(int l=0;l<2;l++)
				dist[i][j][k][l]=min(dist[i][j-1][k][0]+dist[to[i][j-1]][j-1][0][l],
				dist[i][j-1][k][1]+dist[to[i][j-1]][j-1][1][l]);
		}
	cin>>m;
	while(m--)
	{
		int sx,sy,gx,gy;
		cin>>sx>>sy>>gx>>gy;--sx,--sy,--gx,--gy;
		int sid=max(sx,sy),gid=max(gx,gy);//起始点所在层
		if (sid>gid)
			swap(sid,gid),swap(sx,gx),swap(sy,gy);
		if (sid==gid)
			cout<
			ll ans=INF;
			for(int k=0;k<2;k++)//枚举起始层分别走哪个门，求最小答案
				ans=min(ans,min(dis(sx,sy,x[sid][k],y[sid][k])+solve(sid,k,gid-1,0)+1+dis(x[gid-1][0]+1,y[gid-1][0],gx,gy),
				dis(sx,sy,x[sid][k],y[sid][k])+solve(sid,k,gid-1,1)+1+dis(x[gid-1][1],y[gid-1][1]+1,gx,gy)));
			cout< 
 
Solution 2 
除了倍增，还有一种数据结构可以把大区间分解成不超过 
    
     
      
       
        log
       
       
        ⁡
       
       
        n
       
      
      
       log n
      
     
    logn 个小区间求解最短路。当然是通过线段树。 
线段树上每个节点维护一个区间 
    
     
      
       
        [
       
       
        l
       
       
        ,
       
       
        r
       
       
        ]
       
      
      
       [l,r]
      
     
    [l,r]，里面储存第 
    
     
      
       
        l
       
      
      
       l
      
     
    l 层的每个门到第 
    
     
      
       
        r
       
      
      
       r
      
     
    r 层每个门的最短路。每个大区间是左右两个相邻子区间合并的结果。而相邻区间的合并则要枚举中间进出哪个门来求最小距离。每次询问一个区间，就在线段树上分解为不超过 
    
     
      
       
        log
       
       
        ⁡
       
       
        n
       
      
      
       log n
      
     
    logn 个区间，将他们按顺序合并得到要求的门与门距离。 
时间复杂度：
    
     
      
       
        O
       
       
        ⁡
       
       
        (
       
       
        n
       
       
        log
       
       
        ⁡
       
       
        n
       
       
        )
       
      
      
       operatorname O(nlog n)
      
     
    O(nlogn) 
空间复杂度： 
    
     
      
       
        O
       
       
        ⁡
       
       
        (
       
       
        n
       
       
        )
       
      
      
       operatorname O(n)
      
     
    O(n) 
#include 
#define ll long long
#define pb push_back
#define pii pair
#define mp make_pair
#define F first
#define S second
#define y1 IronManSucks
using namespace std;
const ll INF=1000000000000000008;
int n,m;
ll x[100005][2],y[100005][2];
ll dis(ll x1,ll y1,ll x2,ll y2)//曼哈顿距离
{
	return abs(x1-x2)+abs(y1-y2);
}
struct node//线段树节点
{
	int l,r;
	ll d[2][2];//门与门之间最短路
	bool flag;
	node(){
		l=r=flag=0;
		memset(d,0,sizeof(d));
	}
	node operator+(node &b){//区间合并
		if (flag)return b;//如果当前一个区间为空，则合并结果为另一个区间
		if (b.flag)return *this; 
		node c;
		c.l=l,c.r=b.r;
		for(int i=0;i<2;i++)
		for(int j=0;j<2;j++)
		{
			c.d[i][j]=INF;
			for(int k=0;k<2;k++)//枚举中间进出的门
				c.d[i][j]=min(c.d[i][j],min(d[i][0]+1+dis(x[r][0]+1,y[r][0],x[r+1][k],y[r+1][k])+b.d[k][j],
				d[i][1]+1+dis(x[r][1],y[r][1]+1,x[r+1][k],y[r+1][k])+b.d[k][j]));
		}
		return c;
	}
};
struct segtree//非递归线段树
{
	node seg[200005];
	void build()//建树
	{
		for(int i=0;i
			seg[i+n].l=seg[i+n].r=i;
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
					seg[i+n].d[j][k]=dis(x[i][j],y[i][j],x[i][k],y[i][k]);
		}
		for(int i=n-1;i>0;i--)//合并子区间
			seg[i]=seg[i<<1]+seg[i<<1|1];
	}
	node query(int l,int r)//区间查询
	{
		node resl,resr;//从左端和右端两边开始合并的答案
		resl.flag=resr.flag=1;
		for(l+=n,r+=n;l>=1,r>>=1)
		{
			if (l&1) resl=resl+seg[l++];
			if (r&1) resr=seg[--r]+resr;
		}
		return resl+resr;
	}
}t;
int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
	cin>>n;
	for(int i=0;i>x[i][j]>>y[i][j],--x[i][j],--y[i][j];
	t.build();
	cin>>m;
	while(m--)
	{
		int sx,sy,gx,gy;
		cin>>sx>>sy>>gx>>gy;--sx,--sy,--gx,--gy;
		int sid=max(sx,sy),gid=max(gx,gy);
		if (sid>gid)
			swap(sx,gx),swap(sy,gy),swap(sid,gid);
		if (sid==gid)
			cout<
			node res=t.query(sid,gid);
			ll ans=INF;
			for(int i=0;i<2;i++)
				ans=min(ans,min(dis(sx,sy,x[sid][i],y[sid][i])+res.d[i][0]+1+dis(x[gid-1][0]+1,y[gid-1][0],gx,gy),
				dis(sx,sy,x[sid][i],y[sid][i])+res.d[i][1]+1+dis(x[gid-1][1],y[gid-1][1]+1,gx,gy)));
			cout< 
另：关于我的非递归线段树，如果理解不了的可以见 codeforces 的这篇 blog。传送门。

CF1681E Labyrinth Adventures题解

C/C++/C#相关栏目本月热门文章