专栏文章

你说得对，但是我认为这是 implemention

NNATO
P11593题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miq8hsg6
此快照首次捕获于
2025/12/04 00:41
3 个月前
此快照最后确认于
2025/12/04 00:41
3 个月前
查看原文
提供一种纯并查集的做法。

思路浅析：

考虑我们走到一个点 (i,j)(i,j) 上，我们没有超过它的限制 di,jd_{i,j}，但是我们可能因为其它点限制更小就走不出去了，所以这个限制不够严，考虑求出 di,j′d'_{i,j} 表示我走到这个点上，在能够走出去的条件下最多能够持有的金币数量。
怎么搞出来这个东西呢？容易想到可以值域扫描线+并查集。
具体地，我们做一个从大到小的值域扫描线，保留所有 d≥xd\ge x 的点，扫到大小 xx 时就把所有 d=xd=x 的点和四周的 d≥xd\ge x 的点合并，一个未碰到边缘的连通块和碰到边缘的连通块合并的时候就是未碰到边缘的连通块内那些点的 d′d'。
现在，我们就去掉了走回来这个过程。
考虑如何求出答案。考虑求出 dpi,jdp_{i,j} 表示走到 (i,j)(i,j) 可以获得的金币数量。
考虑一个和上面恰好相反的从小到大的扫描线，保留所有 d′≥xd'\ge x 的点，不过现在我们就不需要考虑走出去了。我们每次求出 d′=xd'=x 的 dpi,jdp_{i,j}。
发现如果在 d′=xd'=x 时有一个 dpi,jdp_{i,j}，我们就需要给它所在的连通块的每个位置的 dpdp 值和它取 max⁡\max。
转换一下，我们记录整个连通块的 dpdp 值即可。
转移是容易的，d′=xd'=x 时 dpu=min⁡(x,dpu+sumu,x)dp_u=\min(x,dp_u+sum_{u,x})，其中 sumu,xsum_{u,x} 表示以 uu 为代表的联通块内 d′=xd'=x 的点数。
然后随着 xx 的增大，联通块会发生分裂，分裂这个过程可以通过做一次从大到小的扫描线变成合并，记录一下怎么合并的即可实现分裂。
考虑分裂出了两个分别以 u,vu,v 为代表的联通块（uu 为原来连通块的代表点），在此之前对于这两个连通块我可以拿了 uu 中 d′>xd'>x（≤x\le x 的已经考虑过了）位置的金币再走到 vv，反之亦然，但是我不能拿超过 xx 个金币，不然我就走不了了。
于是有转移：
dpu=min⁡(x,dpu+∑i>xsumv,i)dp_u=\min(x,dp_u+\sum\limits_{i>x}sum_{v,i})
dpv=min⁡(x,dpu+∑i>xsumu,i)dp_v=\min(x,dp_u+\sum\limits_{i>x}sum_{u,i})
sumsum 和其后缀和在做那次维护分裂过程的扫描线时是容易维护的。
上述过程实质应该和其他题解重构树是本质相同的吧。。。
时间复杂度 O(nmlog⁡nm)O(nm\log{nm})，瓶颈在于记录合并需要使用启发式合并（这样改变父亲的点只有一个），应该有更好的实现方式做到更优秀的复杂度，不过懒得想了（。

参考代码：

CPP
#include<bits/stdc++.h>
#define ll int
using namespace std;
ll n,m;
struct px
{
	ll x,y;
};
px where[1000005];
ll f[1000005],sz[1000005],tsz[1000005];
vector<ll>uid[1000005];
vector<ll>hid[1000005];
vector<ll>d[1000005];
ll find(ll x)
{
	return f[x]==x?x:find(f[x]);
}
ll dx[]={0,0,0,1,-1};
ll dy[]={0,1,-1,0,0};
struct xp
{
	ll u,szu,szv;
};
vector<xp>cf[1000005];
void merge(ll u,ll v,ll i,bool ok=0)
{
	u=find(u);v=find(v);
	if(u==v)return;
	if(!u||!v)
	{
		if(u)swap(u,v);
		f[v]=0;
		for(auto it:uid[v])
		d[where[it].x][where[it].y]=i;
	}
	else
	{
		if(tsz[u]<tsz[v])swap(u,v);
		f[v]=u;tsz[u]+=tsz[v];
		if(!ok)
		{
			for(auto it:uid[v])uid[u].emplace_back(it);
			uid[v].clear();
		}
		if(ok)cf[i].emplace_back((xp){v,sz[u],sz[v]});
		sz[u]+=sz[v];
	}
}
ll maxn[1000005];
int main()
{
	//freopen("treasure.in","r",stdin);
	//freopen("treasure.out","w",stdout);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(ll i=1;i<=n;++i)
	{
		d[i].emplace_back(0);
		for(ll j=1;j<=m;++j)
		{
			ll ls;
			cin>>ls;
			d[i].emplace_back(ls);
		}
	}
	for(ll i=1;i<=n;++i)
		for(ll j=1;j<=m;++j)
		{
			f[(i-1)*m+j]=(i-1)*m+j;
			uid[(i-1)*m+j].emplace_back((i-1)*m+j);
			where[(i-1)*m+j]=(px){i,j};
			hid[d[i][j]].emplace_back((i-1)*m+j);
			tsz[(i-1)*m+j]=1;
		}
	for(ll i=1000000;i;--i)
	{
		for(auto it:hid[i])
		{
			px now=where[it];
			for(ll k=1;k<=4;++k)
			{
				px ls=(px){now.x+dx[k],now.y+dy[k]};
				if(ls.x>n||ls.y>m||!ls.x||!ls.y)ls=(px){1,0};
				if(ls.y&&d[ls.x][ls.y]<i)continue;
				merge(it,m*(ls.x-1)+ls.y,i); 
			}
		}
		hid[i].clear();
	}	
	for(ll i=1;i<=n;++i)
		for(ll j=1;j<=m;++j)
		{
			f[(i-1)*m+j]=(i-1)*m+j;
			uid[(i-1)*m+j].clear();
			uid[(i-1)*m+j].emplace_back((i-1)*m+j);
			hid[d[i][j]].emplace_back((i-1)*m+j);
		}
	for(ll i=1000000;i;--i)
	{
		for(auto it:hid[i])
		{
			px now=where[it];
			for(ll k=1;k<=4;++k)
			{
				px ls=(px){now.x+dx[k],now.y+dy[k]};
				if(ls.x>n||ls.y>m||!ls.x||!ls.y)continue;
				if(d[ls.x][ls.y]<i)continue;
				merge(it,m*(ls.x-1)+ls.y,i,1); 
			}
		}
		for(auto it:hid[i])++sz[find(it)];
	}
	for(ll i=1;i<=1000000;++i)
	{
		for(auto it:hid[i])
		{
			ll u=find(it);
			maxn[u]=min(maxn[u]+1,i);
		}
		while(!cf[i].empty())
		{
			xp id=*cf[i].rbegin();cf[i].pop_back();
			ll u=id.u;
			ll uf=find(u);
			maxn[u]=min(i,maxn[uf]+id.szu);
			maxn[uf]=min(i,maxn[uf]+id.szv);
			f[u]=u;
		}
	}
	ll res=0;
	for(ll i=1;i<=n*m;++i)res=max(res,maxn[i]);
	cout<<res;
}

评论

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

正在加载评论...