自动搬运

查看原文

来自洛谷，原作者为

	xiaolilsq 灰名不比红名好看（

搬运于2025-08-24 22:20:09，当前版本为作者最后更新于2020-04-12 17:05:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

刚开始看到这道题目没有任何思路，但是如果知道一个性质这题就很好做了：如果从第$x$列下落的路径为$a_1\dots a_y$，那么经过若干轮后，必然只有后面经过的一段连续路径会被石子覆盖。

考虑反证法，如果存在一个$t$，使得$a_t$被石子覆盖而$a_{t+1}$没有被覆盖，那么由于可以从$a_t$下落到$a_{t+1}$，$a_{t+1}$必然也被石子覆盖，与假设$a_{t+1}$没有被覆盖相矛盾，所以经过若干轮后，必然只有后面经过的一段连续路径会被石子覆盖。

那么我们可以想出一种算法：先保留从每一行下降的路径，进行某行的操作的时候，先把路径被占的部分退回去，然后再寻找一条其他的路径进行下落。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
template<typename T>void read(T &x){
	x=0;int f(1);char c(getchar());
	for(;!isdigit(c);c=getchar())if(c=='-')f=-f;
	for(; isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c-'0');
	x*=f;
}
template<typename T>void write(T x){
	if(x<0)putchar('-'),x=-x;
	if(x/10)write(x/10),x%=10;
	putchar(x+'0');
}
char map[30005][35];
int sap[35][30005],cn[35],r,c;
void push(int x){//下落函数
	while(true){
		int t=sap[x][cn[x]];
		if(map[cn[x]][t]=='O')--cn[x];//如果被占领则将路径退回
		else if(cn[x]==r)break;//到底了
		else if(map[cn[x]+1][t]=='X')break;//有墙壁不再下落
		else if(map[cn[x]+1][t]=='.')sap[x][++cn[x]]=t;//往下走
		else if(t>1&&map[cn[x]][t-1]=='.'&&map[cn[x]+1][t-1]=='.')sap[x][++cn[x]]=t-1;//往左走
		else if(t<c&&map[cn[x]][t+1]=='.'&&map[cn[x]+1][t+1]=='.')sap[x][++cn[x]]=t+1;//往右走
		else break;//无路可走
	}
	map[cn[x]][sap[x][cn[x]]]='O';//占领最后的格子
}
int main(){
	read(r),read(c);
	for(int i=1;i<=r;++i){//读入
		for(int j=1;j<=c;++j){
			char c=getchar();
			while(c!='X'&&c!='.')
				c=getchar();
			map[i][j]=c;
		}
	}
	for(int j=1;j<=c;++j)
		sap[j][0]=j;//初始每列从该列开始下落
	int n;read(n);
	while(n--){
		int tmp;read(tmp);
		push(tmp);//下落
	}
	for(int i=1;i<=r;++i,putchar('\n'))
		for(int j=1;j<=c;++j)
			putchar(map[i][j])//输出;
	return 0;
}

复杂度为什么是对的？其实我也不会证呜呜呜。

希望有大佬可以证明复杂度。