题解 P2906 【[USACO08OPEN]牛的街区Cow Neighborhoods】

Siyuan

2019-02-08 11:25:18

Solution

[$$\Large\texttt{My Blog}$$](https://hydingsy.github.io/articles/problem-Luogu-2906-Cow-Neighborhoods/) --- ## Description > 题目链接:[Luogu 2906](https://www.luogu.org/problemnew/show/P2906) 了解奶牛们的人都知道,奶牛喜欢成群结队。观察约翰的 $n$ 只奶牛,你会发现她们已经结成了几个“群”。每只奶牛在吃草的时候有一个独一无二的位置坐标 $(X_i,Y_i)$。当满足下列两个条件之一,两只奶牛 $i$ 和 $j$ 是属于同一个群的: 1. 两只奶牛的曼哈顿距离不超过 $C$,即 $|X_i-X_j|+|Y_i-Y_j|\le C$。 2. 两只奶牛有共同的邻居。即存在一只奶牛 $k$,使 $i$ 与 $k$、$j$ 与 $k$ 均同属一个群。 请计算有多少个牛群,以及最大的牛群里有多少奶牛。 数据范围:$1\le n\le 10^5$,$1\le X_i,Y_i,C\le 10^9$,$X_i,Y_i,C\in \mathbb{Z}$ ------ ## Solution 首先我们有一个转化:**曼哈顿距离**转**切比雪夫距离**。将一个点的坐标 $(x,y)$ 转化成 $(x+y,x-y)$,设新点的坐标为 $(x',y')$,那么原来的曼哈顿距离 $\vert x_1-x_2\vert +\vert y_1-y_2\vert$ 就等于现在的切比雪夫距离 $\max(\vert x'_1-x'_2\vert,\vert y'_1-y'_2\vert)$。可以通过分类讨论或几何法简单证明成立。 设第 $i$ 个点的新坐标为 $(X_i+Y_i,X_i-Y_i)$,记为 $(x_i,y_i)$。那么第 $1$ 个限制会变为: - 两只奶牛的切比雪夫距离不超过 $C$,即 $\max(\vert x_1-x_2\vert,\vert y_1-y_2\vert)\le C$。 由于有 $\max$,我们可以将 $(x_i,y_i)$ 以 $x_i$ 为第一个关键字,$y_i$ 为第二关键字,从小到大排序。对于同一群的奶牛我们用并查集合并。 我们用 $\text{set}$ 维护 $y_i$(每个点)的值,我们每次在插入第 $i$ 个点时,先把 $\text{set}$ 中所有满足 $\vert x_i-x_j\vert>C$ 的点都删除,然后用 $\text{lower_bound}$ 找到第一个大于等于 $y_i$ 的点,如果满足约束条件就将这两个点合并起来。再找到最后一个小于 $y_i$ 的点,进行相同合并操作。 最后我们证明其他的点不需要和 $i$ 合并。 对于大于等于 $y_j$ 的点 $k$ 满足约束条件 $y_k-y_i\le C$,那么 $y_k-y_j\le y_k-y_i\le C$,那么在处理 $j$ 或 $k$ 时一定会把 $k$ 合并进来(这取决于 $x_j$ 和 $x_k$ 的大小),所以不必合并了。对于小于的部分证明同理。 **时间复杂度**:$O(n\cdot\alpha(n)\log n)$ ------ ## Code ```cpp #include <cstdio> #include <algorithm> #include <set> typedef std::pair<long long,int> pli; typedef std::pair<long long,long long> pll; #define mk std::make_pair const int N=1e5+5; int n,C,fa[N],cnt[N]; pll a[N]; std::set<pli> s; int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); } void merge(int x,int y) { fa[find(x)]=find(y); } int main() { scanf("%d%d",&n,&C); for(int i=1;i<=n;++i) { int X,Y; scanf("%d%d",&X,&Y); a[i]=mk(X+Y,X-Y),fa[i]=i; } std::sort(a+1,a+n+1); s.insert(mk(-1LL<<60,0)),s.insert(mk(1LL<<60,0)); s.insert(mk(a[1].second,1)); for(int l=1,i=2;i<=n;++i) { while(a[i].first-a[l].first>C) s.erase(mk(a[l].second,l)),++l; std::set<pli>::iterator it=s.lower_bound(mk(a[i].second,0)); if(it->first-a[i].second<=C) merge(i,it->second); --it; if(a[i].second-it->first<=C) merge(i,it->second); s.insert(mk(a[i].second,i)); } int ans=0,mx=0; for(int i=1;i<=n;++i) ans+=(find(i)==i),mx=std::max(mx,++cnt[find(i)]); printf("%d %d\n",ans,mx); return 0; } ```