ABC304 CDE 题解 -fangyanli

fangyanli 2023-08-18 11:45:20 4

C题

题意:一张图,个点,编号为的的点可以给距离不超过的点染色,被染色的点可以继续染色;如果第个点被染色输出 否则输出

思路:bfs即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d,x[2002],y[2002],dis[2001][2001],v[2001];
queue<int> q;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j) dis[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
		}
	}
	q.push(1);
	v[1]=1;
	while(q.size()){
		int w=q.front();q.pop();
		for(int i=1;i<=n;i++){
			if(i!=w&&!v[i]&&dis[w][i]<=d*d){
				q.push(i);
				v[i]=1;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(v[i]){
			cout<<"Yes\n";
		}
		else cout<<"No\n";
	}
}

D题

题意:一个平面上有个点,沿着轴切刀,沿着轴切刀,不会切到点上 ; 问在切完后的个块上点最少为多少,最多为多少

思路:用map记录位置,统计刀最大的界限切下所剩下的点,在map大小不等于(A+1)(B+1)时特判,最小一定为0

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int h,w,n,x[200001],y[200001],a,b,cx[200001],cy[200001];
map<pair<int,int>,int> mp;
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>h>>w>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	cin>>a;
	for(int i=1;i<=a;i++){
		cin>>cx[i];
	}
	cin>>b;
	for(int i=1;i<=b;i++){
		cin>>cy[i];
	}
	sort(cx+1,cx+a+1);
	sort(cy+1,cy+b+1);
	for(int i=1;i<=n;i++){
		int xp=lower_bound(cx+1,cx+a+1,x[i])-cx;
		int yp=lower_bound(cy+1,cy+b+1,y[i])-cy;
		mp[make_pair(xp,yp)]++;
	}
	int mn=INT_MAX,mx=INT_MIN;
	if(mp.size()!=(a+1)*(b+1)) mn=0;
	for(int i=1;i<=n;i++){
		int xp=lower_bound(cx+1,cx+a+1,x[i])-cx;
		int yp=lower_bound(cy+1,cy+b+1,y[i])-cy;
		mn=min(mn,mp[pair<int,int>(xp,yp)]);
		mx=max(mx,mp[pair<int,int>(xp,yp)]);
	}
	cout<<mn<<" "<<mx;
}

E题

题意:一张图,个点,条边,个 u 和 v 有一条边,有对 X 和 Y次独立的询问,每次在 p 和 q 之间加一条边,如果对 X 和 Y联通了,输出,否则输出

思路:用并查集和map记录询问前个点的联通情况如果find(X)==find(Y)就全部输出 ; 询问时直接检查map里是否有这样的联通块即可

map存入时要保证find(X)<find(Y)

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,f[1000001],ff,k,q;
map<pair<int,int>,int> mp;
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
    	int u,v;
    	cin>>u>>v;
    	f[find(u)]=find(v);
	}
	cin>>k;
	for(int i=1;i<=k;i++){
    	int x,y;
    	cin>>x>>y;
    	x=find(x);y=find(y);
		if(x>y) swap(x,y);
    	mp[make_pair(x,y)]=1;
    	if(x==y){
    		ff=1;
		}
	}
	cin>>q;
	if(ff){
		for(int i=1;i<=q;i++) cout<<"No\n";
	}
	else {
		for(int i=1;i<=q;i++){
			int x,y;cin>>x>>y;
			x=find(x);y=find(y);
			if(x>y) swap(x,y);
			mp[make_pair(x,y)]?cout<<"No\n":cout<<"Yes\n";
		}
	}
}
{{ vote && vote.total.up }}