2025 年睿抗机器人开发者大赛 CAIP-编程技能赛本科组国赛解题报告

RC-u2 理包

分值: 20 分

思路: 模拟

枚举包裹的空坐标，然后以物品坐标系，以相对偏移向量尝试填充匹配。感觉码量有点大，看起来简单，但写起来稍头痛。

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, m, q; cin >> n >> m >> q;
    vector<string> g(n);
    for(int i = 0; i < n; i++){ g[i].resize(m, '.'); }
    while(q-- > 0){
        int r, c; cin >> r >> c;
        vector<string> mat(r);
        int sy = -1, sx = -1;
        for(int i = 0; i < r; i++){
            cin >> mat[i];
            if(sy == -1){
                for(int j = 0; j < c; j++){
                    if(mat[i][j] == '*'){ sy = i; sx = j; break; }
                }
            }
        }
        // 以物品坐标去匹配包裹，oy/ox 是相对偏移向量
        auto check = [&](int oy, int ox)->bool{
            for(int i = 0; i < r; i++){
                for(int j = 0; j < c; j++){
                    if(mat[i][j] == '*'){
                        if(i + oy >= 0 && i + oy < n && j + ox >= 0 && j + ox < m){
                            if(g[i + oy][j + ox] == '*'){ return false; }
                        } else { return false; }
                    } else { return false; }
                }
            }
            return true;
        };
        // 以物品坐标去填充包裹，oy/ox 是相对偏移向量
        auto fill = [&](int oy, int ox){
            for(int i = 0; i < r; i++){
                for(int j = 0; j < c; j++){
                    if(mat[i][j] == '*'){ g[i + oy][j + ox] = '*'; }
                }
            }
        };
        // 从包裹坐标出发，寻找空格去，查询是否放入物品
        auto solve = [&](int& ay, int& ax)->bool{
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(g[i][j] == '.'){
                        if(check(i - sy, j - sx)){ ay = i; ax = j; fill(i - sy, j - sx); return true; }
                    }
                }
            }
            return false;
        };
        int ay = 0, ax = 0;
        if(solve(ay, ax)){ cout << (ay + 1) << " " << (ax + 1) << "\n"; }
        else{ cout << -1 << " " << -1 << "\n"; }
    }
    return 0;
}

RC-u3 删除屏蔽词

分值: 25 分

思路: 模拟 + 栈

这题限定模式串固定为 2，如果为 k，那这题就麻烦了。就是当前字符，以及栈顶元素，是否构成模式串。

注意：需要输出删除次数，不是最后文本的长度。

#include<bits/stdc++.h>
using namespace std;

int main(){
    string p, s;
    getline(cin, p);
    getline(cin, s);
    int del = 0;
    stack<char> stk;
    for(char c: s){
        // 核心代码，就是这一行
        if(c == p[1] && !stk.empty() && stk.top() == p[0]){ stk.pop(); del++; }
        else{ stk.push(c); }
    }
    string buf;
    while(!stk.empty()){ buf.push_back(stk.top()); stk.pop(); }
    reverse(buf.begin(), buf.end());
    cout << del << " " << buf << "\n";
    return 0;
}

RC-u4 穷游

分值: 30 分

思路: 二分 + Dijkstra

可以先确定最小的住宿费用，再求解此基础上的最小时长。这个套路在睿抗编程赛中多次出现。

二分 check 的核心逻辑是连通性，为了简化代码，可以复用带限制的求时长 Dijkstra。这样在追求编码效率和代码 AC 之间达到一个好的平衡。

#include<bits/stdc++.h>
using namespace std;
struct E{ int v, w; E(){} E(int v, int w):v(v),w(w){} };
struct P{ int u, c; P(){} P(int u, int c):u(u),c(c){} };

int main(){
    int n, m; cin >> n >> m;
    vector<int> prices(n);
    for(int &x: prices) cin >> x;
    vector<vector<E>> g(n);
    for(int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        u--; v--;
        g[u].push_back(E(v, w)); g[v].push_back(E(u, w));
    }
    int s, e; cin >> s >> e; s--; e--;
    auto comp = [](const P& lhs, const P& rhs){ return lhs.c > rhs.c; };
    int inf = 0x3f3f3f3f;
    auto dijkstra = [&](int limit){
        vector<int> dp(n, inf); dp[s] = 0;
        priority_queue<P, vector<P>, decltype(comp)> pq(comp);
        pq.push(P(s, 0));
        while(!pq.empty()){
            P p = pq.top(); pq.pop();
            if(p.c > dp[p.u]) continue;
            if(p.u == e){ return p.c; }
            for(E &e: g[p.u]){
                if(prices[e.v] > limit) continue;
                if(dp[e.v] > p.c + e.w){ dp[e.v] = p.c + e.w; pq.push(P(e.v, dp[e.v])); }
            }
        }
        return inf;
    };
    int l = 0, r = *max_element(prices.begin(), prices.end());
    // 二分确认最小费用
    while(l <= r){
        int mid = l + (r - l)/2;
        int ret = dijkstra(mid);
        if(ret != inf){ r = mid - 1; }
        else{ l = mid + 1; }
    }
    // 再求解最小时长
    int ret = dijkstra(l);
    cout << l << " " << ret << "\n";
    return 0;
}

RC-u5 工序优化

分值: 30

思路: 动态规划

题目可以归纳如下，更好的理解。

定义一个 merge 操作：

• 第 i 项可以和第 i-1 项合并，时间合并，工作时间按第 i-1 项为准，但需额外消耗 Ci
• 合并可以连续，即 [a, b] 的连续区间可以合并，操作次数为 (b - a) 次
• 这个操作最多 k 次

如何理解呢？ 定义把 [a, b] 连续区间进行合并，则 E[a,b] 合并的时间消耗 = (∑Pi) * Ta E[a,b] 合并的代价 = cost[a,b] = ∑Ci

能理解这个核心的概念后，那个这个 dp 就相对容易解了。

1. 定义状态 dp[i][j] 为前 i 项，使用 j 次 merge 操作的最小时间/代价
2. 转移方程 dp[i+1+s][j+s] = min(dp[i][j] + E[i+1, i+1+s])
3. 结果 ans = min(dp[n-1][j])

时间复杂度为 O(n*k^2)

#include<bits/stdc++.h>
using namespace std;
const int64_t inf = (int64_t)1e18;
struct W{ int t, p, c; W(){} W(int t, int p, int c):t(t),p(p),c(c){} };
struct E{ int64_t p = inf; int64_t c = 0;
    bool operator<(const E&rhs)const{return p != rhs.p ? p < rhs.p : c < rhs.c;}
    E operator+(const E&rhs)const{return {p+rhs.p, c+rhs.c};}
};

int main(){
    int n, k; cin >> n >> k;
    vector<W> tasks(n);
    for(int i = 0; i < n; i++){ W &w = tasks[i]; cin >> w.t >> w.p >> w.c; }
    // 预处理，时间和费用的前缀和
    vector<int64_t> pre_p(n + 1, 0); vector<int64_t> pre_c(n + 1, 0);
    for(int i = 0; i < n; i++){ pre_p[i + 1] = pre_p[i] + tasks[i].p; pre_c[i + 1] = pre_c[i] + tasks[i].c; }
    // 定义 dp[i][j], 前 i 项使用 j 次操作的最小时间/费用
    vector<vector<E>> dp(n, vector<E>(k + 1));
    for(int i = 0; i <= k && i < n; i++){ dp[i][i] = {(pre_p[i + 1] - pre_p[0]) * tasks[0].t, pre_c[i + 1] - pre_c[1]}; }
    // 刷表
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= k; j++){
            for(int s = 0; s + j <= k && i + s + 1 < n; s++){
                E tmp = {(pre_p[i + s + 2] - pre_p[i + 1]) * tasks[i + 1].t, pre_c[i + s + 2] - pre_c[i + 2]};
                E tmp2 = dp[i][j] + tmp;
                if(tmp2 < dp[i + s + 1][j + s]){ dp[i + s + 1][j + s] = tmp2; }
            }
        }
    }
    E ans = {inf, 0};
    for(int i = 0; i <= k; i++){
        if(dp[n - 1][i] < ans){ ans = dp[n - 1][i]; }
    }
    cout << ans.p << " " << ans.c << "\n";
    return 0;
}

写在最后