Skip to content

洛谷 - P2906 Cow Neighborhoods G

题解约 1.1 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

测试数据可以在 Luogu/P2906/data 目录下获得,与洛谷上的测试点顺序有偏差。

#题面

#题目描述

了解奶牛的人都知道奶牛是如何组成「奶牛社区」的。他们观察了 Farmer John 的 NN 头奶牛(编号为 1N1 \sim N),它们在 XXYY 坐标范围为 11 的牧场上放牧,每头奶牛都在自己唯一的整数直线坐标上。

如果满足以下两个标准中的至少一个,则两头奶牛是邻居:

  1. 两只奶牛的曼哈顿距离不超过 CC,即 Xixi+YiyiC|X_i - x_i| + |Y_i - y_i| \leq C
  2. 两只奶牛有共同的邻居。即存在一只奶牛 kk,使 iikkjjkk 均同属一个群。

给定奶牛的位置和距离 CC,确定「奶牛社区」的数量和最大的「奶牛社区」中的奶牛数量。

例如,考虑下面的牧场。 当 C=4C = 4 时,这个牧场有四个社区:左边的一个大社区,两个大小为 1 的社区,右边有一个巨大的社区,里面有 6060 头不同的奶牛。

.....................................*.................
....*...*..*.......................***.................
......*...........................****.................
..*....*..*.......................*...*.******.*.*.....
........................*.............***...***...*....
*..*..*...*..........................*..*...*..*...*...
.....................................*..*...*..*.......
.....................................*..*...*..*.......
...*................*..................................
.*..*............................*.*.*.*.*.*.*.*.*.*.*.
.*.....*..........................*.*.*.*.*.*.*.*.*.*.*
....*..................................................

#输入格式

11 行包含两个用空格分隔的整数 N,CN, C

22 到第 N+1N + 1 行每行包含两个用空格分隔的整数 Xi,YiX_i, Y_i,表示一头牛的坐标。

#输出格式

共一行,为两个用空格分隔的整数,为「奶牛社区」的数量和最大的「奶牛社区」内牛的数量。

#输入输出样例

样例输入 #1

4 2
1 1
3 3
2 2
10 10

样例输出 #1

2 3

样例说明 #1

样例中有 22 个社区,一个由前三头奶牛组成,另一个是最后一头奶牛。因此,最大的社区大小为 33

#数据范围与约定

对于 100%100\% 的数据,1N1051 \leq N \leq 10^51C1091 \leq C \leq 10^91Xi,Yi1091 \leq X_i, Y_i \leq 10^9Xi,YiX_i, Y_i 均为整数。

#思路

机房巨佬于队曾经教过我们一个小 trick:曼哈顿距离和切比雪夫距离之间的转化。

曼哈顿坐标系是通过将切比雪夫坐标系旋转 π4\frac{\pi}{4} 后再缩小到原来的一半得到的。那么可以通过将 (x,y)(x, y) 变为 (x+y,xy)(x + y, x - y) 得到曼哈顿坐标系。

记题中第 ii 个点 (Xi,Yi)(X_i, Y_i) 的切比雪夫坐标为 (xi,yi)(x_i, y_i),那么限制 11 可以改写成:

  • 两只奶牛的切比雪夫距离不超过 CC,即 max(x1x2,y1y2)C\max(|x_1 - x_2|, |y_1 - y_2|) \leq C

那么可以先以 xx 轴坐标为第一关键字,yy 轴坐标为第二关键字从小到大排序,并使用并查集合并同一群的奶牛。然后使用 set 维护 yy 轴坐标的值,在插入每个点之前将 xx 轴坐标不合法的删除,然后使用 lower_bound 找到 yiy_i 的前驱和后继,如果满足限制则将其与 yiy_i 合并。最后统计连通块个数和最大连通块大小即可。

#代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <algorithm>
#include <set>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e5 + 5;

int n, c, fa[N], cnt[N], ans, max;
std::pair<int, int> points[N];
std::set<std::pair<int, int>> set;

int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline void merge(int x, int y) {
fa[find(x)] = find(y);
}

int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);

cin >> n >> c;

for (int i = 1, x, y; i <= n; i++) {
cin >> x >> y;

points[i] = std::make_pair(x + y, x - y);
fa[i] = i;
}

std::sort(points + 1, points + 1 + n);

set.insert(std::make_pair(points[1].second, 1));
for (int i = 2, l = 1; i <= n; i++) {
while (points[i].first - points[l].first > c) {
set.erase(std::make_pair(points[l].second, l));
l++;
}

auto it = set.lower_bound(std::make_pair(points[i].second, 0));

if (it != set.end() && it->first - points[i].second <= c) {
merge(i, it->second);
}

if (it != set.begin() && points[i].second - (--it)->first <= c) {
merge(i, it->second);
}

set.insert(std::make_pair(points[i].second, i));
}

for (int i = 1; i <= n; i++) {
if (find(i) == i) ans++;

max = std::max(max, ++cnt[find(i)]);
}

cout << ans << ' ' << max << endl;

return 0;
}