自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 23:06:58，当前版本为作者最后更新于2025-02-13 00:55:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Problem Link

题目大意

给定 $n\times m$ 网格，以及长度为 $k$ 的字符串 $S$（字符集东南西北），初始每个格子为白色。

在第 $t$ 个时刻，我们选取方向 $S^{\infty}_t$，然后取出每个格子在该方向的邻居，如果某个格子 $(i,j)$ 连续 $a_{i,j}$ 个时刻都取到了一个黑色的邻居，那么这个格子也染黑。

你要选择一个格子染黑，最小化充分大时间后的黑色格子数量，并且求出有多少个取到最小值的起点。

数据范围：$n,m\le 800,k\le 10^5$。

思路分析

首先我们要快速判定一个格子是否能染黑，取出其所有黑色邻居所在的方向，记为集合 $s$，那么要求就是 $S^{\infty}$ 中存在一个长度 $\ge a_{i,j}$ 的连续段全部由 $s$ 中字符构成。

对每个 $s$ 预处理出 $S^{\infty}$ 中由 $s$ 构成的极长连续段，可以 $\mathcal O(1)$ 判定每个格子是否染黑。

那么暴力就是从每个点开始 bfs，但显然无法通过。

考虑利用一些已有的信息，例如从 $u$ 出发能染黑 $v$，那么从 $v$ 出发能染黑的点从 $u$ 出发一定也会染黑。

因此可以考虑连边 $u\to v$，则每个点的答案就是后继个数。

先对这张图缩点，那么答案只可能是无出度的强连通分量。

可以发现如果存在一条边 $u\to v$，那么 $u$ 的答案不优于 $v$ 的答案。

因此我们取出这张图的一个内向生成森林，则答案一定来自每个根所在的强连通分量。

如果求出极大的一个内向生成森林，显然一个强连通分量内不会有两个根，因此对每个根暴力 bfs 复杂度正确。

那么问题就变成了在这张图上求出一个极大内向生成森林。

稠密图上的生成树问题可以考虑 Boruvka，在这题中，我们动态维护一个内向生成森林，然后对每个根找一条连向其他树的出边，然后以任意顺序加入这条边（只要不成环）。

很显然每轮增广后连通块数量减半，那么增广轮数是 $\mathcal O(\log nm)$ 的。

每轮增广就从每个根开始 bfs，如果遇到一个和自己不同色的点就立即退出，那么每个点只会被同色的根 bfs 到，复杂度 $\mathcal O(nm)$。

时间复杂度 $\mathcal O(k+nm\log nm)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=805,MAXL=2e5+5,MAXV=1e6+5,inf=1e9,dx[]={-1,1,0,0},dy[]={0,0,-1,1};
char op[MAXL];
int n,m,q,lim[16],a[MAXN][MAXN];
int cl[MAXN][MAXN],id[MAXN][MAXN],dsu[MAXV],tot;
bool vis[MAXN][MAXN];
int ty(char c) { return c=='N'?0:(c=='S'?1:(c=='W'?2:3)); }
int find(int x) { return dsu[x]^x?dsu[x]=find(dsu[x]):x; }
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>q>>n>>m;
	for(int i=1;i<=q;++i) cin>>op[i],op[i+q]=op[i];
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>a[i][j],id[i][j]=++tot;
	for(int s=1;s<16;++s) {
		for(int i=1,j=lim[s]=-1;i<=2*q;++i) if(!(s>>ty(op[i])&1)) {
			if(~j) lim[s]=max(lim[s],i-j-1); j=i;
		}
		if(lim[s]==-1) lim[s]=inf;
	}
	iota(dsu+1,dsu+tot+1,1);
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(a[i][j]) cl[i][j]=id[i][j];
	while(true) {
		memset(vis,false,sizeof(vis));
		vector <array<int,2>> E;
		int ans=inf,cnt=0;
		for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(cl[i][j]==id[i][j]) {
			int z=0; queue <array<int,2>> Q;
			Q.push({i,j}),vis[i][j]=true;
			auto is=[&](int x,int y){ return vis[x][y]&&cl[x][y]==cl[i][j]; };
			while(Q.size()) {
				int u=Q.front()[0],v=Q.front()[1]; Q.pop(),++z;
				for(int d:{0,1,2,3}) {
					int x=u+dx[d],y=v+dy[d];
					if(!a[x][y]||is(x,y)) continue;
					int s=is(x-1,y)|is(x+1,y)<<1|is(x,y-1)<<2|is(x,y+1)<<3;
					if(a[x][y]<=lim[s]) {
						if(cl[x][y]==cl[i][j]) Q.push({x,y}),vis[x][y]=true;
						else { E.push_back({cl[i][j],cl[x][y]}); goto _; }
					}
				}
			}
			if(ans>z) ans=cnt=z;
			else if(ans==z) cnt+=z;
			_:;
		}
		if(E.empty()) return cout<<ans<<"\n"<<cnt<<"\n",0;
		for(auto e:E) if(find(e[1])!=e[0]) dsu[e[0]]=find(e[1]);
		for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(a[i][j]) cl[i][j]=find(id[i][j]);
	}
	return 0;
}