2024CAIP省赛

title: 2024CAIP省赛
date: 2024-07-16 22:13:50
tags: 总结
categories: 比赛

总结写在前面，就一句话

状态的保持胜过少女的娇羞

RC-u1 热҈热҈热҈

思路

按题意，大于35的，判断是否为星期四，统计数量即可

RC-u2 谁进线下了？

思路

按题意模拟即可。

RC-u3 暖炉与水豚

思路

枚举每一个暖炉，将合法的水豚标记，最后会剩一个不合法的，然后搜索这个不合法的水豚周围3x3，记录合法的隐藏的位置

RC-u4 章鱼图的判断

思路

建无向图，记录每个点的度，拓扑去每个环的枝条，最后枚举每一个环，有一种特殊情况，就是多环共点，这个情况是需要去除。

代码

vector<int> g[N];
int d[N];
int cnt,ans;
int n,m;

//搜环
void dfs(int x){
	d[x] = 0;
	for(auto v : g[x]){
		if(d[v]){
			dfs(v);
			cnt ++;
		}
	}
}
//tuopu去支
void DAG()
{
	queue<int> q;
	for(int i = 1; i <= n ; i ++){
		if(d[i] == 1){
			q.push(i);
		}
	}
	while(!q.empty()){
		int t = q.front();
		q.pop();
		d[t] --;
		for(auto v : g[t]){
			d[v] --;
			if(d[v] == 1){
				q.push(v);
			}
		}
	}
}
void solve(){
	cin >> n >> m;
	
	memset(d,0,sizeof d);
	for(int i = 1; i <= m ; i ++){
		int u,v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		d[u] ++,d[v] ++;
	}
	DAG();
	
	//多环一点情况下，4 2 2，去除该情况
	for(int i = 1; i <= n; i ++){
		if(d[i] && d[i] != 2){
			dfs(i);
		}
	}
	
	ans = cnt = 0;
    //
	for(int i = 1 ; i <= n; i ++){
		if(d[i] == 2){
			cnt = 1;
			dfs(i);
			ans ++;
		}
	}
	
	if(ans == 1) cout << "Yes " << cnt << "\n";
	else cout << "No " << ans << "\n";
	for(int i = 1; i <= n ; i ++){
		g[i].clear();
	}
	
}
int main()
{
	int t; cin >> t;
	while(t --) solve();
	return 0;
}

RC-u5 工作安排

思路

题意可以转换为01背包，这是一个典型的01背包模型。外循环枚举事件，内循环枚举体积，最后遍历求最大值即可。

void solve()
{
    int n;
	cin >> n;
	vector<array<int,3>> vec(n + 1);
	for(int i = 1; i <= n ; i ++){
		int t,d,p;
		cin >> t >> d >> p;
		vec[i] = {d,t,p};
	}
	sort(vec.begin() + 1,vec.end());
	vector<int> l(n + 1),v(n + 1),w(n + 1);
	for(int i = 1; i <= n ;  i++){
		l[i] = vec[i][0];
		v[i] = vec[i][1];
		w[i] = vec[i][2];
	}
	vector<int> dp(5050);
	for(int i = 1;i <= n ; i ++){
		for(int j = 5000; j >= 0; j --){
			if(j >= v[i] && j <= l[i]){
				dp[j] = max(dp[j - v[i]] + w[i],dp[j]);
			}
		}
	}
	ll maxx = 0;
	for(int i = 1; i <= 5000; i ++) maxx = max(maxx,dp[i]);
	cout << maxx << endl;
}
signed main()
{
	int t; 
	t = 1;
	cin >> t;
	while(t --){
		solve();
	}
	return 0;
}