这一题可以使用并查集来判断第 个人是否在同一个集合，如果是，就输出 ，否则输出 。
由于数据比较小，可以爆搜。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2010;
int f[N],n,d,x[N],y[N];
int fa(int x){
if(f[x]==x) return x;
return f[x]=fa(f[x]);
}
signed main(){
cin>>n>>d;
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1;i<=n;++i){
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;++i){
for(int j=1+i;j<=n;++j){
if(pow((x[i]-x[j]),2)+pow((y[i]-y[j]),2)<=d*d){
f[fa(j)]=fa(i);
}
}
}
int m=fa(1);
for(int i=1;i<=n;++i){
if(fa(i)==m){
cout<<"Yes\n";
}
else cout<<"No\n";
}
return 0;
}
这题我们需要考虑每个草莓在哪一块蛋糕上，而不是考虑每块蛋糕上有几个草莓。
统计完后可以利用离散化或 统计个数。
还有一定要特判有没有蛋糕上没有草莓！！
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,A,a[N],B,b[N],w,h,x[N],y[N],id[N];
signed main(){
cin>>w>>h;
cin>>n;
for(int i=1;i<=n;++i){
cin>>x[i]>>y[i];
}
cin>>A;
for(int i=1;i<=A;++i) cin>>a[i];
++A;
a[A]=w;
cin>>B;
for(int i=1;i<=B;++i) cin>>b[i];
++B;
b[B]=h;
for(int i=1;i<=n;++i){
int p,q;
p=upper_bound(a+1,a+A+1,x[i])-a;
q=upper_bound(b+1,b+B+1,y[i])-b;
id[i]=p*B+q;
}
int ma=0,mi=n+1,cnt=0,sum=1;
sort(id+1,id+1+n);
for(int i=2;i<=n+1;++i){
if(id[i]==id[i-1]) sum++;
else{
ma=max(ma,sum);
mi=min(mi,sum);
cnt++;
sum=1;
}
}
if(cnt<A*B) mi=0;
cout<<mi<<" "<<ma<<"\n";
return 0;
}
我们可以把相连的点理解成一个连通块， 组不相连的点理解成 个点所在的连通块互不相同。
由于题目保证是一个 good 图。所以我们只需判断 和 所在的连通块是否在 组不相连的点里。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int f[N],n,q,m,k;
set<pair<int,int> > s;
int fa(int x){
if(f[x]==x) return x;
return f[x]=fa(f[x]);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;++i) f[i]=i;
int x,y;
for(int i=1;i<=m;++i){
cin>>x>>y;
int fx=fa(x);
int fy=fa(y);
if(fx!=fy){
f[fx]=fy;
}
}
cin>>k;
for(int i=1;i<=k;++i){
cin>>x>>y;
int fx=fa(x);
int fy=fa(y);
if(fx>fy) swap(fx,fy);
s.insert(make_pair(fx,fy));
}
cin>>q;
for(int i=1;i<=q;++i){
cin>>x>>y;
int fx=fa(x);
int fy=fa(y);
if(fx>fy) swap(fx,fy);
if(s.find(make_pair(fx,fy))!=s.end()) cout<<"No\n";
else cout<<"Yes\n";
}
return 0;
}