---

前言

---

题解

今日心血来潮，试了下2024年睿抗CAIP的本科组（省赛），2个小时而言，感觉难度适中。

如果亲们要准备睿抗算法赛，可以试试 牛客周赛 & 蓝桥杯周赛，和这个难度差不多，但是可能睿抗算法赛码量更大一些。

3个模拟题 + 1个图论 + 动态规划， 后三题已经兼具一定思维。

---

RC-u1 热҈热҈热҈

分值: 10分

题型: 模拟题

题意: 统计一个数组中，大于等于35的个数(需要过滤某个同余的项)

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, w;
    cin >> n >> w;
    int ans = 0, ans2 = 0;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        if (v >= 35) {
            if (w == 4) ans2++;
            else ans++;
        }
        w = (w + 1) >= 8 ? 1 : w + 1;
    }
    cout << ans << " " << ans2 << endl;
    return 0;
}

---

RC-u2 谁进线下了？

分值: 15分

题型: 模拟

题意: 给予不同排名不同的分值，同时一个kill的得分，统计最终每个队伍的得分

#include <bits/stdc++.h>

using namespace std;

int rank_score(int r) {
    if (r == 1) return 12;
    else if (r == 2) return 9;
    else if (r == 3) return 7;
    else if (r == 4) return 5;
    else if (r == 5) return 4;
    else if (r >= 6 && r <= 7) return 3;
    else if (r >= 8 && r <= 10) return 2;
    else if (r >= 11 && r <= 15) return 1;
    return 0;
}

int main() {
    int t;
    cin >> t;
    vector<int> arr(20, 0);
    while (t-- > 0) {
        for (int i = 0; i < 20; i++) {
            int r, k;
            cin >> r >> k;
            arr[i] += rank_score(r) + k;
        }
    }
    for (int i = 0; i < 20; i++) {
        cout << (i + 1) << " " << arr[i] << '\n';
    }
    return 0;
}

---

RC-u3 暖炉与水豚

分值： 20分

题型： 模拟

题意: 其实该题应该来自于 扫雷，然后显示的数字反推 未确定的格子，只不过这边用了可爱的青蛙。

这边的模拟，已经带上一定的思维了，而且代码量不少。

从最多只有一个 反常的青蛙(温暖的青蛙，但是周边没暖炉）出发，这样遍历的格子最多8个。

然后在check，用cold的青蛙去验证这个格子是否满足需求。

#include <bits/stdc++.h>

using namespace std;

// 按特定的顺序排列，已经特定的顺序枚举
int dirs[8][2] = {
    {-1, -1}, {0,-1}, {1,-1},
    {-1, 0}, {1, 0},
    {-1, 1}, {0,1}, {1,1},
};

bool check(vector<string> &g, int r, int c) {
    int n = g.size(), m = g[0].size();
    for (int i = 0; i < 8; i++) {
        int y = r + dirs[i][0];
        int x = c + dirs[i][1];
        if (y>=0&&y<n && x>=0 &&x<m) {
            if (g[y][x] == 'm') return false;
        }
    }
    return true;
}

bool verify(vector<string> &g, int r, int c) {
    int n = g.size(), m = g[0].size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j]=='c') {
                if (abs(r - i) <= 1 && abs(c - j) <=1) {
                    return false;
                }
            }
        }
    }
    return true;
}

int main() {

    // 需要优化, r, c
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n;i ++) {
        cin >> g[i];
    }
    
    // 找特殊的位子
    vector<array<int, 2>> ans;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'w' && check(g, i, j)) {
                for (int k = 0; k < 8; k++) {
                    int y = i + dirs[k][1];
                    int x = j + dirs[k][0];
                    if (y>=0&&y<n && x>=0 &&x<m && g[y][x] == '.') {
                        if (verify(g, y, x)) {
                            ans.push_back({y + 1, x + 1});
                        }
                    }
                }
                break;
            }
        }
    }
    if (ans.size() == 0) {
        cout << "Too cold!" << endl;
    } else {
        for (auto &e: ans) {
            cout << e[0] << " " << e[1] << endl;
        }
    }
    
    return 0;
}

---

RC-u4 章鱼图的判断

分值: 25

题型: 图论

这边的章鱼图很有意思，要么是环，要么是基环树

基环树，就用经典的拓扑排序求解

需要注意这题，属于森林，因此这次属于入门的图论题，但是码量不小。

思路:

1. 通过bfs，找出连通图
2. 对于每个连通图，通过拓扑排序技巧，去掉分枝(链/树), 再判断剩下是否是环（所有节点度都是2）

#include <bits/stdc++.h>

using namespace std;

vector<int> bfs(vector<vector<int>> &g, int v, vector<int> &vis) {
    vector<int> graph;
    deque<int> que;
    que.push_back(v);
    vis[v] = 1;
    graph.push_back(v);
    
    while (!que.empty()) {
        int u = que.front(); 
        que.pop_front();
        for (int v: g[u]) {
            if (vis[v] == 0) {
                vis[v] = 1;
                que.push_back(v);
                graph.push_back(v);
            }
        }
    }
    return graph;
}

int topology(vector<vector<int>> &g, vector<int> &deg, vector<int> &graph) {
    deque<int> que;
    for (int &u: graph) {
        if (deg[u] == 1) {
            que.push_back(u);
        }
    }
    
    while (!que.empty()) {
        int u = que.front(); 
        que.pop_front();
        for (int v: g[u]) {
            if (--deg[v] == 1) {
                que.push_back(v);
            }
        }
    }

    int cnt = 0;
    for (int u: graph) {
        if (deg[u] > 2) return -1;
        if (deg[u] == 2) cnt++;
    }
    
    return cnt;
}

int main() {

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

        int max = 0;
        int ans = 0;
        vector<int> vis(n);
        for (int i = 0; i < n;i ++) {
            if (vis[i] == 0) {
                vector<int> graph = bfs(g, i, vis);
                int tmp = topology(g, deg, graph);
                if (tmp > 0) {
                    max = tmp;
                    ans++;
                }
            }
        }

        if (ans == 1) {
            cout << "Yes " << max << endl;
        } else {
            cout << "No " << ans << endl;
        }
        
    }

    return 0;
}

---

RC-u5 工作安排

分值: 30
题型: 需要思维的DP

这种类型的题，往往和贪心有关，挺难处理的。

这边是基于贪心策略，来保证dp的无后效性。

按截止时间排序每个task，然后按
$$dp[i][j],i为前i个task，j为时间点，值为最多的收益$$

然后转移方程为

$$dp[i][j]=max(dp[i-1][j-task[i].t]+task[i].p)$$
$$task[i].t\le j\le taks[i].t+task[i].d$$

最终结果为

$$maxdp[i][j]$$

这边可以借助 前缀和的技巧 来优化，同时这边需要使用滚动数组的技巧

不然会遇到 内存溢出的错误

#include <bits/stdc++.h>

using namespace std;

struct Span {
    int t, d, p;
    Span(int t, int d, int p) : t(t), d(d), p(p) {}
};

void solve() {
    int n;
    cin >> n;
    vector<Span> ps;
    for (int i = 0; i < n; i++) {
        int t, d, p; cin >> t >> d >> p;
        ps.push_back(Span(t, d, p));
    }
    // 按时间序排序，保证dp的无后效性
    sort(ps.begin(), ps.end(), [](auto &a, auto &b) {
        return a.d < b.d;
    });

    // 这边的5000为时间的上限
    vector<int> dp(5001, 0);

    for (int i = 0; i < n; i++) {
        vector<int> dp2(5001, 0);
        int d = ps[i].d, t = ps[i].t;
        for (int j = 0; j <= d - t; j++) {
            dp2[j + t] = max(dp2[j + t], dp[j] + ps[i].p);
        }
        
        for (int j = 0; j <= 5000; j++) {
            dp2[j] = max(dp2[j], dp[j]);
            if (j > 0) dp2[j] = max(dp2[j], dp2[j - 1]);
        }
        dp.swap(dp2);
    }

    cout << dp[5000] << endl;
    
}

int main() {

    int t;
    cin >> t;
    while (t-- > 0) {
        solve();
    }

    return 0;
}

---

写在最后