OI题解 - Must Be Rectangular! [ABC131 F]

中考完以来打的第一场网络赛

话说什么时候ABC也变成 $6$ 道题而且参与分数线都涨到 $1\text~1999$ 了?题也难了许多,F题感觉还不错,发现了并查集的新用法~


· 题意

平面上有 $n$ 个点,给出每个点的坐标——第$i$个点坐标为 $(x_i,y_i)$。

若存在 $3$ 个点 $(x_1,y_1),(x_1,y_2),(x_2,y_1)$ ($x_1\not=x_2且y_1\not=y_2$),则根据这$3$个点在$(x_2,y_2)$ 处新建一个点(如果该位置原本没有点)。这样的$4$个点就围成了一个矩形。

你想要建立尽可能多的点,注意新建立的点也可以和其他点构成新矩形,举个例子:

问你最多能够新建多少个点(注意是新建)。


· 题解

- 系

我们定义一个“系”,一个系由若干个点构成。点 $(x,y)$ 属于 系$A$ 当且仅当存在点 $(x’,y’)\in A$ 使得 $x’=x或y’=y$(或者 系$A$ 中不包含任何点)。

一个点属于恰好一个系。

然后我们就会发现一个性质:如果我们把系中的所有点的横轴、纵轴都画出来,我们可以得到一个网格,网格的所有交汇点要么是已知的点,要么是可以新建的点,且新建的点仍属于这个系。比如:

对于一个系,我们定义 $cntx$ 表示系内所有点中不同的横坐标的个数,$cnty$ 表示系内所有点中不同的纵坐标的个数。(比如上图中 $cntx=5,cnty=4$)

则网格中就会出现 $cntx\times cnty$ 个交汇点,也就是上图中橙色点与白色点的个数之和为 $cntx\times cnty$ 。

我们可以发现不同的系中的点不可能构成新建的点。那么如果我们把所有 $n$ 个点划分为 $m$ 个系$\{G_1,G_2,…,G_m\}$,并且令 $S_i$ 表示 $G_i$ 中包含的点的个数、$cntx_i$ 表示系 $G_i$ 内所有点中不同的横坐标的个数、$cnty_i$ 表示系 $G_i$ 内所有点中不同的纵坐标的个数,那么我们能够构造 $\sum_{i=1}^m(cntx_i\times cnty_i)-n$ 个新点。

- 并查集

现在我们需要求出上述的系,于是可以想到用一个并查集储存一个系。

但是这个并查集里面储存的并不是系里的点,而是系里的点的 横、纵坐标——因为一个点可以用横坐标和纵坐标表示,而且根据之前的结论,一个系里所有能够新建出来的点和原本的点的总个数是 $cntx\times cnty$ —— 如果我们将横、纵坐标储存在一个并查集里,我们可以迅速算出 $cntx$ 和 $cnty$ ,从而得到解。

具体实现见代码。


· 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5;
int n;
int pre[2*N+5],cntX[2*N+5],cntY[2*N+5];
int Find(int u){return pre[u]=(pre[u]==u? u:Find(pre[u]));}
int main(){
scanf("%d",&n);
for(int i=1;i<=2*N;i++) pre[i]=i;
for(int i=1;i<=n;i++){
int x,y;scanf("%d%d",&x,&y);
int Fx=Find(x),Fy=Find(N+y);
if(Fx!=Fy) pre[Fx]=Fy;
}
for(int i=1;i<=2*N;i++){
int Fi=Find(i);
if(i<=N) cntY[Fi]++;
else cntX[Fi]++;
}
ll ans=0;
for(int i=1;i<=2*N;i++)
ans+=1ll*cntX[i]*cntY[i];
printf("%lld\n",ans-n);
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%