题解 P5962 【[BOI2004]ships 船】

SUNCHAOYI · 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 语句)。

如果该行只有一个 ;，那么没有需要处理的船，直接跳过即可。
如果遇到数字，那么转化成 int 类型进行存储。
如果遇到分隔符 -，说明有连续一段，标记并记录 - 左边的数 a = num。
如果遇到结束的标志 , 或 ;，根据之前的标记进行判断是一个数还是一段区间，然后记录下来 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{并查集操作}

合并：如果不是同一个父亲结点上的就把结点与连通块数量一起合并。
```
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]);//查询根结点 
}

\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]);//查询根结点 
}