当前位置：首页 > news >正文

2024CAIP省赛

news 来源：原创 2024/9/21 1:45:28

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<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;
}