2024睿抗本科组省赛解析_睿抗2022国赛csdn本科组

1.热热热，判断就行

2.谁进线下了，排序处理就行

3.暖炉与水豚，首先把暖炉旁的水豚标记为已访问，最后遍历一遍查找哪些没有标记的，周围表示点的格子便可能是暖炉位置，注意湿漉漉的水豚周围八个不能放，最后判断没有的话输出too cold

4.章鱼图，利用并查集，sz表示环的数量，最后判断大小的时候注意边即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
int n,m,st,en;
int sz[100010],d[100010],p[100010];
int find(int x){
	if(p[x]==x)return x;
	return p[x]=find(p[x]);
}
vector<int>e[100010];
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		e[i].clear(),p[i]=i,sz[i]=0,d[i]=-1;
	}
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		e[a].push_back(b);
		e[b].push_back(a);
		int fa=find(a),fb=find(b);
		if(fa!=fb){
			sz[fb]+=sz[fa];
			p[fa]=fb;
		}
		else{
			sz[fa]++;
			st=a,en=b;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(find(i)==i&&sz[i]==1){
			ans++;
		}
	}
	if(ans!=1){
		cout<<"No "<<ans<<endl;
		return;
	}
	queue<int>q;
	q.push(st);
	d[st]=1;
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int v:e[u]){
			if(u==st&&v==en)continue;
			if(d[v]==-1){
				d[v]=d[u]+1;
				q.push(v);
			}
		}
	}
	cout<<"Yes "<<d[en]<<endl;
}
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

5.工作安排，把截止时间按升序排列，01背包模板即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
struct ed{
	int t,d,p;
	bool operator<(const ed &a)const{
		return d<a.d;
	}
};
void solve(){
	ll d[100010];
	memset(d,0,sizeof(d));
	ll ans=0;
	int n;cin>>n;
	vector<ed> e(n);
	for (int i = 0; i < n; i++) {
		cin >> e[i].t >> e[i].d >> e[i].p;
	}
	sort(e.begin(),e.end());
	for(ed i:e){
		for(int j=i.d;j>=i.t;j--)
		{
			d[j]=max(d[j],d[j-i.t]+i.p);
			ans=max(ans,d[j]);
		}
	}
	cout<<ans<<endl;
}
int main(){
	// ios::sync_with_stdio(0);
	// cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}