2024 睿抗机器人开发者大赛CAIP-编程技能赛-本科组（省赛）

RC-u1 热҈热҈热҈

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,w;
    cin >> n >> w;

    int ans1 = 0, ans2 = 0;
    for(int i = 0;i < n;i ++){
        int x;
        cin >> x;

        if(x >= 35){
            if(w == 4) ans2 ++;
            else ans1 ++;
        }

        w ++;
        if(w > 7) w = 1;
    }

    cout << ans1 << ' ' << ans2 << '\n';

    return 0;
}

RC-u2 谁进线下了？

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int level(int x){
    if(x == 1) return 12;
    if(x == 2) return 9;
    if(x == 3) return 7;
    if(x == 4) return 5;
    if(x == 5) return 4;
    if(x <= 7) return 3;
    if(x <= 10) return 2;
    if(x <= 15) return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(20);
    for(int i = 0;i < n;i ++){
        for(int j = 0;j < 20;j ++){
            int c,p;
            cin >> c >> p;
            a[j] += level(c) + p;
        }
    }

    for(int i = 0;i < 20;i ++){
        cout << i + 1 << ' ' << a[i] << '\n';
    }

    return 0;
}

RC-u3 暖炉与水豚

思路

标记暖气周围，当一只水豚周围没有暖气时，说明它周围都有可能是隐藏的暖气，但是要注意判断不在冷水豚的周围。

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<string> s(n);
    for (auto &i : s)
        cin >> i;

    vector st(n, vector<int>(m));
    const int u[] = {1, 1, 1, -1, -1, -1, 0, 0};
    const int v[] = {1, 0, -1, 1, 0, -1, 1, -1};

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            if (s[i][j] == 'm') {
                st[i][j] = 1;
                for (int k = 0; k < 8; k ++) {
                    int x = i + u[k], y = j + v[k];
                    if (x >= 0 && x < n && y >= 0 && y < m)
                        st[x][y] = 1;
                }
            }

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            if (s[i][j] == 'c') {
                st[i][j] = 2;
                for (int k = 0; k < 8; k ++) {
                    int x = i + u[k], y = j + v[k];
                    if (x >= 0 && x < n && y >= 0 && y < m)
                        st[x][y] = 2;
                }
            }

    vector<array<int, 2>> ans;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            if (s[i][j] == 'w' && st[i][j] == 0) {
                for (int k = 0; k < 8; k ++) {
                    int x = i + u[k], y = j + v[k];
                    if (x >= 0 && x < n && y >= 0 && y < m && s[x][y] == '.' && st[x][y] != 2)
                        ans.push_back({x + 1, y + 1});
                }
            }
    sort(ans.begin(), ans.end());

    if (ans.empty()) cout << "Too cold!\n";
    else
        for (auto &[x, y] : ans)
            cout << x << ' ' << y << '\n';

    return 0;
}

RC-u4 章鱼图的判断

思路

dfs 判环是否只有一个，用个时间戳记录一下环的个数即可。

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {

        int n, m;
        cin >> n >> m;

        vector g(n + 1, vector<int>());
        for (int i = 0; i < m; i ++) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }

        int ans = 0, cnt = 0, huan = 0;
        vector<int> vis(n + 1);
        auto dfs = [&](auto & self, int u, int fa, int num)->void{
            vis[u] = num;
            for (auto v : g[u]) {
                if (v == fa) continue;
                if (vis[v]) {
                    cnt ++;
                    ans = max(ans, num - vis[v] + 1);
                } else
                    self(self, v, u, num + 1);
            }
        };

        for (int i = 1; i <= n; i ++) {
            cnt = 0;
            if (!vis[i]) {
                dfs(dfs, i, 0, 1);
                huan += (cnt / 2 == 1);
            }
        }

        if (huan == 1 && n > 2) {
            cout << "Yes" << ' ' << ans << '\n';
        } else {
            cout << "No" << ' ' << huan << '\n';
        }

    }

    return 0;
}

RC-u5 工作安排

思路

按截至日期排个序，然后就是典型的 01 背包。

#include<bits/stdc++.h>

using namespace std;

using i64 = long long;

struct node{
    int t,d,p;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {

        int n;
        cin >> n;

        vector<node> a(n);
        for(auto &i : a)
            cin >> i.t >> i.d >> i.p;

        sort(a.begin(),a.end(),[](node x,node y){
            return x.d < y.d;
        });

        const int N = 5000;
        vector<i64> dp(N + 10,INT_MIN);

        dp[0] = 0;
        for(int i = 0;i < n;i ++){
            for(int j = a[i].d;j>=a[i].t;j--)
                dp[j] = max(dp[j],dp[j-a[i].t]+a[i].p);
        }

        i64 ans = 0;
        for(int i = 0;i <= N;i ++)
            ans = max(ans,dp[i]);

        cout << ans << '\n';

    }   

    return 0;
}