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; string 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;
    booloperator<(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;
}