中考完以来打的第一场网络赛
话说什么时候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 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com ,欢迎提问~