自动搬运

查看原文

来自洛谷，原作者为

	SUNCHAOYI 报名个人赛 https://www.luogu.com.cn/contest/44296

搬运于2025-08-24 22:16:02，当前版本为作者最后更新于2020-07-30 18:50:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这道题目让我们从大到小输出连通块的大小及其对应的个数。

首先最容易想到的是开个二维数组，然后就是很裸的搜索题目。但是一看 $n$ 的数据范围是 $1 \le n \le 3 \times 10 ^ 4$，所以 $n$ 较大是肯定会 $\texttt{MLE}$，只能拿到部分分。(应该能过前 $18$ 个点，但 $72$ 分我觉得也挺多的)

其次我们就要想着如何把二维降到一维，单纯的搜索肯定是过不去了，再次读题发现船舶总数和船舶吨位都不超过 $10^3$，这便是本题的突破口。我们可以用并查集，每次记录当前行和上一行，如果与上一行的船有相交，则将其合并。下面详细来讲该做法：

• $\textbf{输入}$

题目中描述的共有两种情况：单独的一个船--用单独的一个数表示，连续的若干个船--用 x - y 的形式表示。这两个不同的情况之间用 , 隔开；行与行之间用 ; 表示结束。

for (int i = 1;i <= n;++i)
{
	cin>>str;
	if (str == ";")//该行为空行 
	{
		Do something!
	} 
	for (int j = 0;j < str.size ();++j)
	{
		if ('0' <= str[j] && str[j] <= '9')//具体信息 
		{
			Do something!
		} 
		if (str[j] == '-')//分隔符 
		{
			Do something!
		}
		if (str[j] == ',' || str[j] == ';')//一个信息的结束标志 
		{
			Do something!	
		}
	}
}

根据以上程序，我们可以将处理输入分成四个部分(四个 if 语句)。

1. 如果该行只有一个 ;，那么没有需要处理的船，直接跳过即可。
2. 如果遇到数字，那么转化成 int 类型进行存储。
3. 如果遇到分隔符 -，说明有连续一段，标记并记录 - 左边的数 a = num。
4. 如果遇到结束的标志 , 或 ;，根据之前的标记进行判断是一个数还是一段区间，然后记录下来 a = b = num 或是 b = num(此处 $a$ 在分隔符的位置已经记录下来)

• $\textbf{判断相交}$

不难发现应该在第四个 if 语句中操作。开两个数组分别记录最新连通块的结点与大小，并开一个记录每个起始位置与终止位置的结构体。

fa[++cnt] = cnt,sz[cnt] = b - a + 1;//结点与大小
_now[++k] = {a,b,cnt};//结点为 cnt 的连通块的信息

然后就是判断与上一行有无相交，有相交就直接合并，用 while 循环就能解决。

//kk 上一行的结点个数
//be[i] 上一行的信息 b[i].f,b[i].s,b[i].tmp 分别表示终止，起始与结点
//w 从 1 开始循环
while (w <= kk && be[w].f < a) ++w;//与上一行没有相交 
while (w <= kk && be[w].s <= b) _union (_now[k].tmp,be[w].tmp),++w;//有相交就合并 

当然，在 $i$ 循环的时候每一次都要复制一遍上一行的信息，如果当前行为 ; 则需要清空上一行的信息。(因为下一行对应的是当前行空行，一定没有相交)

• $\textbf{并查集操作}$

1. 合并：如果不是同一个父亲结点上的就把结点与连通块数量一起合并。

int dx = find (x),dy = find (y);
if (dx != dy) fa[dy] = dx,sz[dx] += sz[dy];//合并

2. 查询：递归式查找，记得保存最新的父结点信息。

int find (int x)
{
	return fa[x] == x ? x : fa[x] = find (fa[x]);//查询根结点 
}

• $\textbf{答案的输出}$

如果一个结点的父结点是它自己，则这个结点上的连通块数量就是一个答案(说明其它连通的结点都已经被合并)，将其记录。

for (……)
	if (fa[i] == i) Record it!

题目中说明最大的连通块 $\le 10^3$，所以我们倒序循环输出即可。

for (int i = 1000;i >= 1;--i)
	if (连通块的数量为 i 时有解) cout<<i<<" "<<连通块个数为 i 的数量<<endl;

• $\textbf{完整的代码}$

#include <iostream>
#include <cstring>
using namespace std;
const int MAX = 1000005;
int n,a,b,num,cnt,k,kk,w,ans[MAX],fa[MAX],sz[MAX];
struct node
{
	int s,f,tmp;//起点，终点，结点序号 
} be[MAX],_now[MAX];
bool ty;string str;
void _union (int x,int y);
int find (int x);
int main ()
{
	cin>>n;
	for (int i = 1;i <= n;++i)
	{
		cin>>str;
		if (str == ";")
		{
			k = 0;//清零(别忘了!!!) 
			continue;
		}
		for (int j = 1;j <= k;++j) be[j] = _now[j];//上一行的记录 
		kk = k;//上一行的连块计数器 
		k = 0;//当前行的连块计数器 
		for (int j = 0;j < str.size ();++j)
		{
			w = 1;
			if ('0' <= str[j] && str[j] <= '9') num = num * 10 + str[j] - '0';
			if (str[j] == '-') a = num,num = 0,ty = 1;
			if (str[j] == ',' || str[j] == ';')	
			{
				//ty = 0 为一整段；否则为一个点 
				if (ty) b = num;
				else a = b = num;
				fa[++cnt] = cnt,sz[cnt] = b - a + 1;
				_now[++k] = {a,b,cnt};	
				while (w <= kk && be[w].f < a) ++w;//与上一行没有相交 
				while (w <= kk && be[w].s <= b) _union (_now[k].tmp,be[w].tmp),++w;//有相交就合并 
				a = b = num = ty = 0;		
			}
		}
		//for (int j = 1;j <= k;++j) cout<<_now[j].s<<" and "<<_now[j].f<<" "; 
		//cout<<endl;
		//for (int j = 1;j <= kk;++j) cout<<be[j].s<<" and "<<be[j].f<<" "; 
		//cout<<endl;
	}
	for (int i = 1;i <= cnt;++i)
		if (fa[i] == i) ++ans[sz[i]];//说明这个是根结点
	for (int i = 1000;i >= 1;--i)//船舶总数和船舶吨位都不超过 10^3
		if (ans[i]) cout<<i<<" "<<ans[i]<<endl;
	return 0;
}
void _union (int x,int y)
{
	int dx = find (x),dy = find (y);
	if (dx != dy) fa[dy] = dx,sz[dx] += sz[dy];//合并 
}
int find (int x)
{
	return fa[x] == x ? x : fa[x] = find (fa[x]);//查询根结点 
}