更差的閱讀體驗

袋鼠題。

考慮先暴力模擬一輪中每個袋鼠的運動。我們假設位于 \((i, j)\) 的袋鼠，經過一輪之后到達 \((i', j')\)，那么我們連邊 \((i, j) \to (i', j')\)，形成一個內基環樹。

那么我們考慮一個格子在多少輪以前會有袋鼠。我們發現，一輪以后，每一個袋鼠都會向父親跳一步。而到了最后，就只有一些袋鼠在環上一直跳。對于非環上的點 \(u\)，假設 \(u\) 子樹內離 \(u\) 最遠的葉子到 \(u\) 的距離為 \(d\)，那個點為 \(v\)，則 \(u\) 這個位置在 \(v\) 跳到 \(u\) 父親之前都會有袋鼠，即在前 \(d+1\) 輪會有袋鼠。假設對于 \(u\)，有 \(tim_u = d+1\)。

當兩個袋鼠到達同一個位置，可以認為是發生了合并，因為這兩個袋鼠以后的運動軌跡都完全相同，可以讓有袋鼠的格子數量 \(-1\)。那么我們考慮兩個格子 \(x, y\) 合并的影響。我們發現，在 \(\min(tim_x, tim_y)\) 的時間內，這兩個格子都會有袋鼠，合并的時間很好計算。所以我們可以存下所有合并事件發生的時間，再用 \(\max(tim_x, tim_y)\) 去更新當前格子有袋鼠的時間，因為雖然發生了合并，但是有袋鼠的最晚時間沒有變。

那么這道題就做完了，復雜度 \(O(nmk)\)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 200006
#define fi first
#define se second
using namespace std;
using pii=pair<int,int>;
vector<int> mp[N],G[N];
vector<pii> v[N];
int n,m,k,cnt,tot,to[N],vis[N],ring[N],mxd[N],now[N],tmp[N],tim[N],ans[N];
char op[N],ch[N];
inline int id(int x,int y){return (x-1)*m+y;}
void find_ring(int u,int col)
{
	vis[u]=col;
	if(!vis[to[u]])find_ring(to[u],col);
	else if(vis[to[u]]==col) {
		int v=u;
		do {
			ring[v]=1,v=to[v];
		} while(v^u);
	}
}
void dfs(int u)
{
	mxd[u]=1;
	for(int v:G[u])if(!ring[v])
		dfs(v),mxd[u]=max(mxd[u],mxd[v]+1);
}
main()
{
	scanf("%lld%lld%lld%s",&n,&m,&k,op+1);
	for(int i=1;i<=n;i++)
		mp[i].resize(m+5),v[i].resize(m+5);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",ch+1);
		for(int j=1;j<=m;j++)mp[i][j]=ch[j]^48;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)if(mp[i][j])
			v[i][j]={i,j},cnt++;
	for(int l=1;l<=k;l++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)if(mp[i][j])
			{
				int &x=v[i][j].fi,&y=v[i][j].se;
				if(op[l]=='U'&&x>1&&mp[x-1][y])x--;
				else if(op[l]=='D'&&x<n&&mp[x+1][y])x++;
				else if(op[l]=='L'&&y>1&&mp[x][y-1])y--;
				else if(op[l]=='R'&&y<m&&mp[x][y+1])y++;
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)if(v[i][j].fi)
			to[id(i,j)]=id(v[i][j].fi,v[i][j].se),
			G[id(v[i][j].fi,v[i][j].se)].push_back(id(i,j));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(mp[i][j]&&!vis[id(i,j)])find_ring(id(i,j),id(i,j));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(ring[id(i,j)])dfs(id(i,j)),mxd[id(i,j)]=1e15;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)now[id(i,j)]=mxd[id(i,j)];
	for(int l=1;l<=k;l++)
	{
		memset(tmp,0,sizeof(tmp));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)if(mp[i][j])
			{
				int x=i,y=j;
				if(op[l]=='U'&&x>1&&mp[x-1][y])x--;
				else if(op[l]=='D'&&x<n&&mp[x+1][y])x++;
				else if(op[l]=='L'&&y>1&&mp[x][y-1])y--;
				else if(op[l]=='R'&&y<m&&mp[x][y+1])y++;
				int t=min(tmp[id(x,y)],now[id(i,j)]);
				for(int o=0;o<t;o++)tim[++tot]=o*k+l;
				tmp[id(x,y)]=max(tmp[id(x,y)],now[id(i,j)]);
			}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)now[id(i,j)]=tmp[id(i,j)];
	}
	sort(tim+1,tim+tot+1);
	for(int i=1;i<=cnt-tot-1;i++)ans[i]=-1;
	for(int i=1;i<=tot;i++)ans[cnt-i]=tim[i];
	for(int i=1;i<=n*m;i++)printf("%lld\n",ans[i]);
	return 0;
}