2025年睿抗机器人开发者大赛CAIP-编程技能赛本科组（省赛）解题报告 | 珂学家

2025年睿抗机器人开发者大赛省赛题解

珂朵莉酱

2573人浏览 · 2025-07-15 00:07:00

珂朵莉酱 · 2025-07-15 00:07:00 发布

前言

在这里插入图片描述

题解

2025年睿抗机器人开发者大赛CAIP-编程技能赛（省赛）
RoboCom 世界机器人开发者大赛-本科组

t5真的是满满地回忆，这游戏n久年前写过，我记得当时用了一种2.5D的技巧，来实现2维图形实现伪3D的效果。

整体真不难，纯算法的含量低于前几年，但码量真的不小。

pta平台2025年省赛本科组真题

在这里插入图片描述

RC-u1 早鸟价

分数: 10分
题型: 签到


#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int m, d, c;
        cin >> m >> d >> c;
        if (m > 7 || (m == 7 && d > 11)) {
            cout << "Too late!\n";
        } else if (m == 7 || (m == 6 && d > 20)) {
            if (c > 2000) {
                cout << "^_^\n";
            } else if (c == 2000) {
                cout << "Ok!\n";
            } else {
                cout << "Need more!\n";
            }
        } else {
            if (c > 1800) {
                cout << "^_^\n";
            } else if (c == 1800) {
                cout << "Ok!\n";
            } else {
                cout << "Need more!\n";
            }
        }
    }

    return 0;
}

注: 需要注意tuple类元素大小比较的细节，多元的时候，最好写成类，然后重载< 操作符。

RC-u2 谁进线下了？III

分数: 15
题型：签到
感觉这题，比t1更加的签到, 纯阅读理解


#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        int n, s;
        cin >> n >> s;

        int one = 0, tot = 0;
        for (int i = 0; i < n; i++) {
            int r, c;
            cin >> r >> c;
            if (r==1) {
                one++;
            }
            tot += c;
        }
        int r1 = 0, r2 = 0;
        if (one >= (n + 1) / 2) r1 = 1;
        if (tot >= s + 50) r2 = 1;

        cout << r1 << " " << r2 << "\n";
    }
    return 0;
}

RC-u3 点格棋

分数: 20
思路: 枚举 + 模拟

在这里插入图片描述
需要理顺不合符条件的步骤

点和边限制

(x1, y1) 和 (x2, y2) 数据不合法，包括越界
(x1, y1) 和 (x2, y2) 两点不是水平/垂直相邻
重复添加连边

轮换次序限制

没有按照玩家的轮换次序，获得奖励会保持操作，不得分会轮换
小A先行
得分相等，则小B获胜

而对于边，根据方向，采用水平和垂直二维数组来维护。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, m, s;
    cin >> n >> m >> s;

    vector<vector<int>> h(n, vector<int>(m));
    vector<vector<int>> v(m, vector<int>(n));

    // 当前走的玩家
    int side = 0;
    int as = 0, bs = 0;
    // 记录错误的操作编号
    vector<int> wrong;
    for (int i = 0; i < s; i++) {
        int p, y1, x1, y2, x2;
        cin >> p >> y1 >> x1 >> y2 >> x2;
        y1--; x1--; y2--; x2--;

        bool c1 = (y1 < 0 || y1 >= n) || (x1 < 0 || x1 >= m);
        bool c2 = (y2 < 0 || y2 >= n) || (x2 < 0 || x2 >= m);
        if (c1 || c2) {
            wrong.push_back(i);
            continue;
        }

        // 不是预期的玩家
        if (p != side) {
            wrong.push_back(i);
            continue;
        }

        bool flag = false;
        if (y1 == y2 && abs(x1 - x2) == 1) {
            if (x1 > x2) swap(x1, x2);

            if (h[y1][x1] == 1) {
                wrong.push_back(i);
                continue;
            }
            h[y1][x1] = 1;

            if (y1 > 0 && h[y1 - 1][x1] == 1 && v[x1][y1 - 1] == 1 && v[x2][y1 - 1] == 1) {
                if (p == 0) as++; else bs++;
                flag = true;
            }

            if (y1 + 1 < n && h[y1 + 1][x1] == 1 && v[x1][y1] == 1 && v[x2][y1] == 1) {
                if (p == 0) as++; else bs++;
                flag = true;
            }

        } else if (x1 == x2 && abs(y1 - y2) == 1) {
            if (y1 > y2) swap(y1, y2);

            if (v[x1][y1] == 1) {
                wrong.push_back(i);
                continue;
            }
            v[x1][y1] = 1;

            if (x1 > 0 && v[x1 - 1][y1] == 1 && h[y1][x1 - 1] == 1 && h[y1+1][x1 - 1] == 1) {
                if (p == 0) as++; else bs++;
                flag = true;
            }

            if (x1 + 1 < m && v[x1 + 1][y1] == 1 && h[y1][x1] == 1 && h[y1+1][x1] == 1) {
                if (p == 0) as++; else bs++;
                flag = true;
            }
        } else {
            wrong.push_back(i);
            continue;
        }
        if (!flag) side = 1 - side;
    }

    if (wrong.empty()) {
        cout << -1 << "\n";
    } else {
        for (int i = 0; i < wrong.size(); i++) {
            cout << (wrong[i] + 1) << " \n"[i == wrong.size() - 1];
        }
    }
    if (as > bs) {
        cout << 0 << " " << as << "\n";
    } else {
        cout << 1 << " " << bs << "\n";
    }

    return 0;
}

RC-u4 Tree Tree 的

分数: 25
思路：找圈

在这里插入图片描述
本题的核心，就是理解1,2两条件

从特殊到一般，其实可以手玩几个特殊的图形

链
菊花图
圈
完全图

然后玩着玩着，你就会发现：
$才满足这些特殊条件（n\ge 3)$
所以本题，就是给你一个无向图，然后寻找一个圈

需要特别注意：

空集和单点是特殊的 $G^{'}$
2个节点以及彼此相连的边，也构成一个特殊的 $G^{'}$

这边其实有两个思路：

二进制枚举参与圈的节点，然后dfs找圈
直接dfs找圈

时间复杂度评估: $O(n * 4^{n})$ , $\le 10, 题目保证一个节点最多4条边$



#include <bits/stdc++.h>

using namespace std;

bool dfs(int u, int start, vector<vector<int>> &g, int mask, int state) {
    if (state == mask) {
        for (int v: g[u]) {
            if (v == start) {
                return true;
            }
        }
        return false;
    }
    for (int v: g[u]) {
        if (((1 << v) & mask) != 0 && ((1 << v) & state) == 0) {
            if (dfs(v, start, g, mask, state | (1 << v))) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        int n, m;
        cin >> n >> m;
        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);
        }
        
        set<int> tree = {0, 1};
        if (m >= 1) {
            tree.insert(2);
        }
        
        // 枚举二进制的子集
        int range = 1 << n;
        for (int i = 1; i < range; i++) {
            int cnt = 0;
            
            // 需要一个起点，以及集合的大小
            int start = -1;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    if (start == -1) start = j;
                    cnt++;
                }
            }

            // 避免相同的集合大小
            if (tree.find(cnt) == tree.end()) {
                if (dfs(start, start, g, i, 1 << start)) {
                    tree.insert(cnt);
                }
            }
        }
        
        // 逆序拿到2个最大, 次大的结果
        auto iter = tree.rbegin();
        cout << *iter << " ";
        iter++;
        cout << *iter << "\n";
        
    }
    return 0;
}

直接dfs找圈

#include <bits/stdc++.h>

using namespace std;

struct Solution {
    vector<bool> vis;
    vector<vector<int>> g;
    int n, m;
    
    void solve() {
        cin >> n >> m;
        g.resize(n);
        vis.resize(n + 1);
        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);
        }
        vis[0] = vis[1] = true;
        if (m > 0) vis[2] = true;
        for (int i = 0; i < n; i++) {
            dfs(i, i, 1 << i, 1);
        }

        int s1 = -1, s2 = -1;
        for (int i = n; i >= 0; i--) {
            if (vis[i]) {
                if (s1 == -1) s1 = i;
                else if (s2 == -1) s2 = i;
            }
        }
        cout << s1 << " " << s2 << "\n";
    }

    void dfs(int u, int s, int mask, int cnt) {
        for (int v: g[u]) {
            if (v == s) {
                vis[cnt] = true;
                continue;
            }
            
            if (((1 << v) & mask) == 0) {
                dfs(v, s, mask | (1 << v), cnt + 1);
            }
        }
    }    
};

int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        Solution solution;
        solution.solve();
    }
    return 0;
}

RC-u5 游戏设计师

分数: 30
思路: 逆向思维+bfs+离线查询
在这里插入图片描述
可以引入状态 (x, y, s) 表示在(x, y)基准坐标，以s状态，最少需要多少步。

可以从空洞出发，进行一遍bfs，把所有的结果前提保存。
而后续的在线查询，就变成 $O (1)$

#include <bits/stdc++.h>

using namespace std;

const int N = 1000;
int dp[3][N][N];


struct E {
    int x, y, s;
};

bool support(char c1, char c2) {
    if (c1 == '0' || c1 == '3') return false;
    if (c2 == '0' || c2 == '3') return false;
    return true;
}

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

    int n, m;
    cin >> n >> m;
    vector<string> g(n);

    int tx = -1, ty = -1;
    for (int i = 0; i < n; i++) {
        cin >> g[i];
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '3') {
                tx = i;
                ty = j;
            }
        }
    }

    memset(dp, -1, sizeof(dp));
    deque<E> que;

    que.push_back({tx, ty, 0});
    dp[0][tx][ty] = 0;

    while (!que.empty()) {
        E e = que.front(); que.pop_front();
        if (e.s == 0) {
            if (e.y + 2 < m) {
                if (support(g[e.x][e.y + 1], g[e.x][e.y + 2])) {
                    if (dp[1][e.x][e.y + 1] == -1
                        || dp[1][e.x][e.y + 1] > dp[0][e.x][e.y] + 1) {
                        dp[1][e.x][e.y + 1] = dp[0][e.x][e.y] + 1;
                        que.push_back({e.x, e.y + 1, 1});
                    }
                }
            }
            if (e.y - 2 >= 0) {
                if (support(g[e.x][e.y - 1], g[e.x][e.y - 2])) {
                    if (dp[1][e.x][e.y - 2] == -1
                        || dp[1][e.x][e.y - 2] > dp[0][e.x][e.y] + 1) {
                        dp[1][e.x][e.y - 2] = dp[0][e.x][e.y] + 1;
                        que.push_back({e.x, e.y - 2, 1});
                    }
                }
            }

            if (e.x + 2 < n) {
                if (support(g[e.x + 1][e.y], g[e.x + 2][e.y])) {
                    if (dp[2][e.x + 1][e.y] == -1
                        || dp[2][e.x + 1][e.y] > dp[0][e.x][e.y] + 1) {
                        dp[2][e.x + 1][e.y] = dp[0][e.x][e.y] + 1;
                        que.push_back({e.x + 1, e.y, 2});
                    }
                }
            }
            if (e.x - 2 >= 0) {
                if (support(g[e.x - 2][e.y], g[e.x - 1][e.y])) {
                    if (dp[2][e.x - 2][e.y] == -1
                        || dp[2][e.x - 2][e.y] > dp[0][e.x][e.y] + 1) {
                        dp[2][e.x - 2][e.y] = dp[0][e.x][e.y] + 1;
                        que.push_back({e.x - 2, e.y, 2});
                    }
                }
            }

        } else if (e.s == 1) {

            if (e.y + 2 < m) {
                if (g[e.x][e.y + 2] == '1') {
                    if (dp[0][e.x][e.y + 2] == -1
                        || dp[0][e.x][e.y + 2] > dp[1][e.x][e.y] + 1) {

                        dp[0][e.x][e.y + 2] = dp[1][e.x][e.y] + 1;
                        que.push_back({e.x, e.y + 2, 0});
                    }
                }
            }
            if (e.y - 1 >= 0) {
                if (g[e.x][e.y - 1] == '1') {
                    if (dp[0][e.x][e.y - 1] == -1
                        || dp[0][e.x][e.y - 1] > dp[1][e.x][e.y] + 1) {
                        dp[0][e.x][e.y - 1] = dp[1][e.x][e.y] + 1;
                        que.push_back({e.x, e.y - 1, 0});
                    }
                }
            }

            if (e.x + 1 < n) {
                if (support(g[e.x + 1][e.y], g[e.x + 1][e.y + 1])) {
                    if (dp[1][e.x + 1][e.y] == -1
                        || dp[1][e.x + 1][e.y] > dp[1][e.x][e.y] + 1) {
                        dp[1][e.x + 1][e.y] = dp[1][e.x][e.y] + 1;
                        que.push_back({e.x + 1, e.y, 1});
                    }
                }
            }
            if (e.x - 1 >= 0) {
                if (support(g[e.x - 1][e.y], g[e.x - 1][e.y + 1])) {
                    if (dp[1][e.x - 1][e.y] == -1
                        || dp[1][e.x - 1][e.y] > dp[1][e.x][e.y] + 1) {
                        dp[1][e.x - 1][e.y] = dp[1][e.x][e.y] + 1;
                        que.push_back({e.x - 1, e.y, 1});
                    }
                }
            }
        } else {
            //
            if (e.y + 1 < m) {
                if (support(g[e.x][e.y + 1], g[e.x + 1][e.y + 1])) {
                    if (dp[2][e.x][e.y + 1] == -1
                        || dp[2][e.x][e.y + 1] > dp[2][e.x][e.y] + 1) {

                        dp[2][e.x][e.y + 1] = dp[2][e.x][e.y] + 1;
                        que.push_back({e.x, e.y + 1, 2});
                    }
                }
            }
            if (e.y - 1 >= 0) {
                if (support(g[e.x][e.y - 1], g[e.x + 1][e.y - 1])) {
                    if (dp[2][e.x][e.y - 1] == -1
                        || dp[2][e.x][e.y - 1] > dp[2][e.x][e.y] + 1) {
                        dp[2][e.x][e.y - 1] = dp[2][e.x][e.y] + 1;
                        que.push_back({e.x, e.y - 1, 2});
                    }
                }
            }

            if (e.x + 2 < n) {
                if (g[e.x + 2][e.y] == '1') {
                    if (dp[0][e.x + 2][e.y] == -1
                        || dp[0][e.x + 2][e.y] > dp[2][e.x][e.y] + 1) {
                        dp[0][e.x + 2][e.y] = dp[2][e.x][e.y] + 1;
                        que.push_back({e.x + 2, e.y, 0});
                    }
                }
            }
            if (e.x - 1 >= 0) {
                if (g[e.x - 1][e.y] == '1') {
                    if (dp[0][e.x - 1][e.y] == -1
                        || dp[0][e.x - 1][e.y] > dp[2][e.x][e.y] + 1) {
                        dp[0][e.x - 1][e.y] = dp[2][e.x][e.y] + 1;
                        que.push_back({e.x - 1, e.y, 0});
                    }
                }
            }
        }
    }

    int q;
    cin >> q;
    while (q-- > 0) {
        int x, y, s;
        cin >> x >> y >> s;
        x--; y--;
        cout << dp[s][x][y] << "\n";
    }

    return 0;
}