自动搬运

查看原文

来自洛谷，原作者为

	kIG7Z8oP 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:25:14，当前版本为作者最后更新于2019-11-05 21:32:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

虽然这题已经有45篇题解，但没有一个人想用并查集呢~

介绍一种思考难度稍大的方法

1.Begin

（看见题面马上就知道是Floodfill

但因为一些原因，NOIP暂停，我想到了区间维护就换了种做法

注意！开始讲题（敲黑板）

样例搬运~

4  10
0234500067
1034560500
2045600671
0000000089

我们可以认为，在某行的数据可表示为（如第一行）

数值：0，2，3，4，5，0，0，0，6，7

位置：1，2，3，4，5，6，7，8，9，10

在[2,5] ， [9,10]处有数据

同理，第二行中，[1,1]，[3,6]，[8,8]有数据

你看看

这一行的[3,6]与上一行的[2,5]有交集，所以他们应该在同一联通块中

2.Naive

你要真的这么想，就图样图森破了

那么我想反问一句，为什么不从下往上连呢

当然可以

因为往下连边可以减少find次数期望，推倒不难。但笔者不会

就不用了罢

以下是代码（直接复制并粘贴有惊喜哦）

//能不用尽量别用，O(N*M) 
//27ms
#include<cstdio>
int n,m,a[101][101];//a就是地图 
int tot=0,fa[10010],stlst/*上一行的起始*/,stnow/*这一行的起始*/,qj[10010][2];
int find(int u)
{
	return u==fa[u]?u:fa[u]=find(fa[u]);//板子 
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%1d",&a[i][j]);//鸣谢最上面的题解 
	for(int i=1;(i<<1)<=n*m;i++) fa[i]=i;//最多N*M/2个块 
	for(int i=1;i<=n;i++)
	{
		stlst=stnow;
		stnow=tot;
		for(int j=1;j<=m;j++)
			if(a[i][j])
			{
				qj[tot][0]=j;
				while(a[i][j]) j++;
				qj[tot][1]=j-1;
				for(int k=stlst;k<stnow;k++)
					if(qj[k][1]>=qj[tot][0]&&qj[k][0]<=qj[tot][1]) fa[find(k)]=tot;
				tot++;
			}
	}
	int ans=0;
	for(int i=tot-1;i>=0;i--) if(fa[i]==i)/*我上面没有人*/ ans++;
	printf("%d",ans);
}
//People who copied will AK IOI!

一片苦心孤诣……可怜可怜我吧……给个赞叭~