2024CAIP省赛

title: 2024CAIP省赛

date: 2024-07-16 22:13:50

tags: 总结

categories: 比赛

文章目录

• • • RC-u1 热҈热҈热҈
    • • 思路
      • RC-u2 谁进线下了？
      • • 思路
        • RC-u3 暖炉与水豚
        • • 思路
          • RC-u4 章鱼图的判断
          • • 思路
            • 代码
            • RC-u5 工作安排
            • • 思路

                总结写在前面，就一句话

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

                RC-u1 热҈热҈热҈

                思路

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

                RC-u2 谁进线下了？

                思路

                按题意模拟即可。

                RC-u3 暖炉与水豚

                思路

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

                RC-u4 章鱼图的判断

                思路

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

                代码

                vector 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 q;
                	for(int i = 1; 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 
                		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 
                		if(d[i] && d[i] != 2){
                			dfs(i);
                		}
                	}
                	
                	ans = cnt = 0;
                    //
                	for(int i = 1 ; i 
                		if(d[i] == 2){
                			cnt = 1;
                			dfs(i);
                			ans ++;
                		}
                	}
                	
                	if(ans == 1) cout 
                		g[i].clear();
                	}
                	
                }
                int main()
                {
                	int t; cin  t;
                	while(t --) solve();
                	return 0;
                }
                
                    int n;
                	cin  n;
                	vector
                		int t,d,p;
                		cin  t  d  p;
                		vec[i] = {d,t,p};
                	}
                	sort(vec.begin() + 1,vec.end());
                	vector l(n + 1),v(n + 1),w(n + 1);
                	for(int i = 1; i 
                		l[i] = vec[i][0];
                		v[i] = vec[i][1];
                		w[i] = vec[i][2];
                	}
                	vector
                		for(int j = 5000; j = 0; j --){
                			if(j = v[i] && j 
                				dp[j] = max(dp[j - v[i]] + w[i],dp[j]);
                			}
                		}
                	}
                	ll maxx = 0;
                	for(int i = 1; i 
                	int t; 
                	t = 1;
                	cin  t;
                	while(t --){
                		solve();
                	}
                	return 0;
                }