题解：P11454 [USACO24DEC] 2D Conveyer Belt S

这题一眼和连通性相关，就是看能不能连到矩阵外。

我们发现 Farmer John 的一次操作代表着将一个点的

4

连通变成了

1

连通，也就是说我们删掉了与一个点相连的

3

条边。

然后我们发现连通性和删边这一组关键词似曾相识。

于是我们想到了[JSOI2008] 星球大战的做法，开始~~挥舞造物主的魔法棒~~时光倒流。

具体来说，我们可以求出将所有操作处理完后的答案，再一步一步的将操作倒过来进行。

这样，我们就可以把删边改成加边，就可以好维护一些。

我们首先考虑如何求出所有操作完后的答案。

我们可以对于边界上的点看看能不能连出边界，如果可以就以它为起点，dfs 遍历所有能到达它的点，并打上标记，打过标记的点就不用遍历了。

然后等于询问的时光倒流，我们就看解放的那个点周围有没有可以走到外界的点（即之前打过标记的点）或是否在边界，如果有，那么这个点与所有能到达它的点都能走到外界。

时间复杂度

\mathcal{O}(m+n)

。

code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Q=2e5+10;
int n,m,sum;
int ans[Q];
char s[1010][1010];
int v[1010][1010];
int to[1010][1010][4];
struct Qu{
	int x,y;
	char ch;
}r[Q];
const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};
void dfs(int x,int y){
	v[x][y]=1,sum++;
	for(int i=0;i<4;++i){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx<1||xx>n||yy<1||yy>n||v[xx][yy]) continue;
		if(!to[xx][yy][i^1]) continue;//左^1为右，其他同理，处理能达到x点的点
		dfs(xx,yy);
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) s[i][j]='?';//一开始全部为？
	for(int i=1;i<=m;i++){
		cin>>r[i].x>>r[i].y>>r[i].ch;
		s[r[i].x][r[i].y]=r[i].ch;//m次操作后的矩阵
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){//处理出每个点是否能向每个方向走
            //0代表左，1代表右，2代表上，3代表下
			if(s[i][j]=='?'||s[i][j]=='L') to[i][j][0]=1;
			if(s[i][j]=='?'||s[i][j]=='R') to[i][j][1]=1;
			if(s[i][j]=='?'||s[i][j]=='U') to[i][j][2]=1;
			if(s[i][j]=='?'||s[i][j]=='D') to[i][j][3]=1;
		}
	}
	for(int i=1;i<=n;i++){//处理第一行
		if(v[1][i]||!to[1][i][2]) continue;
		dfs(1,i);
	}
	for(int i=1;i<=n;i++){//处理第n行
		if(v[n][i]||!to[n][i][3]) continue;
		dfs(n,i);
	}
	for(int i=1;i<=n;i++){//处理第一列
		if(v[i][1]||!to[i][1][0]) continue;
		dfs(i,1);
	}
	for(int i=1;i<=n;i++){//处理第n列
		if(v[i][n]||!to[i][n][1]) continue;
		dfs(i,n);
	}
	for(int w=m;w>=1;w--){
		ans[w]=sum;
		int x=r[w].x,y=r[w].y;
		s[x][y]='?';
		for(int i=0;i<4;i++) to[x][y][i]=1;//解放这个点
		if(v[x][y]) continue;
		int p=0;
		for(int i=0;i<4;i++){//看看周围有没有已解放的点或是否在边界
			int xx=x+dx[i],yy=y+dy[i];
			if(xx<1||xx>n||yy<1||yy>n) {p=1;break;}
			if(v[xx][yy]) {p=1;break;}
		}
		if(!p) continue;
		dfs(x,y);//以这个点为起点dfs
	}
	for(int i=1;i<=m;i++) cout<<n*n-ans[i]<<"\n";//sum记录的是能走出去的点，所以要用总点数减去
	return 0;
}

题解：P11454 [USACO24DEC] 2D Conveyer Belt S

文章操作

code

相关推荐

评论

题解：P11454 [USACO24DEC] 2D Conveyer Belt S