专栏文章

题解：P13096 [FJCPC 2025] 难以控制的滑板火箭

HHPXXZYY
P13096题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmkdv9
此快照首次捕获于
2025/12/02 04:51
3 个月前
此快照最后确认于
2025/12/02 04:51
3 个月前
查看原文
[Problem Discription]\color{blue}{\texttt{[Problem Discription]}}
给定一张图，11 表示可以到达，00 表示障碍。你一次移动可以向相邻八个方向运动，但不能碰到障碍物。单位时间内你可以且进行 [l,r][l,r] 次移动（在区间内即可，具体多少次可以选择）。
求从 (1,1)(1,1) 到 (n,m)(n,m) 需要的最少时间，注意必须在进行完单位时间内所有移动后停留在 (n,m)(n,m) 才算到达。
[Analysis]\color{blue}{\texttt{[Analysis]}}
第一眼，肯定和 bfs 求最短路有关。假设最短路长度是 LL。
第二眼，时间最短肯定开始阶段都进行 rr 次操作。
所以答案就是 ⌈Lr⌉\left \lceil \frac{L}{r} \right \rceil？当然不是。
不过这个肯定是答案的下界，我们考虑一下什么情况下可以达到这个下界。
首先，如果 LL 恰好是 rr 的倍数当然就是这个答案，这种情况太平凡。下面都假设 LL 不是 rr 的倍数。
设 tmp=⌈Lr⌉\text{tmp}=\left \lceil \frac{L}{r} \right \rceil。由于 LL 不是 rr 的倍数，因此如果在 tmp\text{tmp} 的时间内每步都移动 rr 次肯定会出现的这样的情况：在 tmp\text{tmp} 时间的某次移动到达了终点，但是后续还需要进行移动。
怎么消耗掉这些多余的步骤呢？一个最简单的方法就是在终点和终点前一点反复横跳，这样一轮操作会消耗掉 22 次多余的移动。也就是说，通过这种反复横跳的操作可以是移动步数变成任何大于等于 LL 且与 LL 奇偶相同的数。
当然，如果 tmp×r\text{tmp}\times r 和 LL 同奇偶，那么答案还是下界 tmp\text{tmp} 不变。这是答案取下界的又一种情况。
如果 tmp×r\text{tmp}\times r 和 LL 奇偶相反，但 l≠rl \not = r，那么在第 tmp\text{tmp} 时间内只移动 (r−1)(r-1) 步是一定合法的。而 (tmp×r−1)(\text{tmp}\times r-1) 和 LL 是同奇偶的。因此 l≠rl\not = r 时依然取下界。
接下来只剩一种情况了，就是 l=rl=r 且 tmp×r\text{tmp}\times r 与 LL 奇偶不同。
l=rl=r，意味着每个时间内移动次数是确定的，总移动步数必须是 rr 的整数倍。显然只需要让 LL 每次加 22 知道它是 rr 的倍数即可。
真的即可吗？
显然不是，比如 l=r=5l=r=5，最短路为 1717，那么需要反复横跳 44 次到达 2525，也就是需要 55 的时间，但是如果存在另一条长度为 2020 的路径，只需要 44 的时间。
问题出在哪里？2020 和 1717 奇偶不同。最短路 LL 只能覆盖和 LL 同奇偶的那些路径，但是不能确定另一个奇偶的情况一定不如这个优秀。
怎么办？分别求出长度为奇数的最短路和长度为偶数的最短路分别判断即可。
在这里还遗留了一个问题：只判断最短路每次加 22 真的能覆盖所有合理的情况吗？
首先，限制只能加 22 的情况下，最短路一定最优。因为同奇偶的非最短路的长度一定比最短路至少大 22，也就是最短路一定可以覆盖其它路径能覆盖的所有情况，而且它只可能更优。
其次，为什么是需要考虑加 22？可不可能出现加 11 的情况？其实是有可能的，比如一个三角形的连通区域是可以贡献 +1+1 的。但是 +1+1 会改变奇偶性。
  • 如果最短路 +1+1 不是另一种奇偶性的最短路的情况的话，那么用另一种奇偶性的最短路更优，不需要考虑加 11；
  • 如果最短路 +1+1 是另一种奇偶性的最短路，显然求另一种情况的最短路已经经历了这条路径，也不需要你重复考虑。
加其它数字可以看作 +1+1 和 +2+2 的组合。因此我们的考虑是完备的，覆盖了所有路径的情况。
[Solution]\color{blue}{\texttt{[Solution]}}
  1. 通过分层图的方法求出奇偶最短路的长度。
  2. 如果 l≠rl \not = r，答案就是下界。
  3. 如果 l=rl = r。判断 ll 的奇偶性。如果 ll 为偶数，考虑偶数最短路至少加几个 22 可以变成 rr 的倍数。其实稍微思考可以发现，也就是下界。如果 ll 是奇数，则分别判断奇最短路和偶最短路。
注意到 l=rl=r 且都为奇数时，假设某最短路长度为 dd，那么答案要么是 ⌊dr⌋\left \lfloor \frac{d}{r} \right \rfloor（dd 恰好为 rr 的倍数），要么是它加 11，要么是它加 22。加 11 还是加 22 取决于 dd 和 (⌊dr⌋+1)l\left ( \left \lfloor \frac{d}{r} \right \rfloor +1 \right )l 的奇偶是否相同。
考虑到 ll 是偶数，也就是 dd 和 ⌊dr⌋\left \lfloor \frac{d}{r} \right \rfloor 的奇偶是否相同。
Code\color{blue}{\text{Code}}
CPP
const int N=1010;
const int inf=0x3f3f3f3f;

int dis[N][N][2];
bool vis[N][N][2];
int n,m,a[N][N],l,r,ans;

const int dx[]={0,0,-1,-1,-1,1,1,1};
const int dy[]={1,-1,0,1,-1,0,-1,1};

queue<int> q;

void bfs(int s,int t){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			dis[i][j][0]=dis[i][j][1]=inf;
			vis[i][j][0]=vis[i][j][1]=false;
		}
	
	while (!q.empty()) q.pop();
	
	q.push(s);q.push(t);q.push(0);
	dis[s][t][0]=0;
	vis[s][t][0]=true;
	
	while (!q.empty()){
		int u=q.front();q.pop();
		int v=q.front();q.pop();
		int d=q.front();q.pop();
		
		for(int i=0;i<8;i++){
			int x=u+dx[i],y=v+dy[i];
			
			if (x<1||x>n||y<1||y>m) continue;
			
			if (!vis[x][y][!d]&&a[x][y]){
				vis[x][y][!d]=true;
				dis[x][y][!d]=dis[u][v][d]+1;
				
				q.push(x);
				q.push(y);
				q.push(!d); 
			}
		}
	}
}//分层图最短路

int OZDY(){
	scanf("%d%d",&n,&m);
	scanf("%d%d",&l,&r);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%1d",&a[i][j]);
	
	bfs(1,1);
	
	int u=dis[n][m][0],v=dis[n][m][1];
	if (l!=r){
		if (u==inf&&v==inf) printf("-1\n");//无解
		else printf("%d\n",(min(u,v)+r-1)/r);
	}
	else{
		if (l&1){
			if (u==inf&&v==inf) puts("-1");
			else{
				ans=inf; 
				if (u!=inf){
					int tmp=u/l;
					if (u%l==0) ;
					else if (u%2==tmp%2) tmp+=2;
					else tmp++;
					
					ans=min(ans,tmp);
				}//偶最短路
				if (v!=inf){
					int tmp=v/l;
					if (v%l==0) ;
					else if (v%2==tmp%2) tmp+=2;
					else tmp++;
					
					ans=min(ans,tmp);
				}//奇最短路，两种的处理完全对称
				
				printf("%d\n",ans);
			}
		}
		else{
			if (u==inf) puts("-1");
			else printf("%d\n",(u+r-1)/r);
		}//l 为偶数，其倍数也必然是偶数，只需考虑偶最短路
	}
	
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...