2024 睿抗机器人开发者大赛CAIP-编程技能赛-本科组(国赛) 解题报告 | 珂学家

前言

题解

2024 睿抗机器人开发者大赛CAIP-编程技能赛-本科组(国赛)。

国赛比省赛难一些，做得汗流浃背，T_T.

RC-u1 大家一起查作弊

分值: 15分

这题真的太有意思，看看描述

在今年的睿抗比赛上，有同学的提交代码如下：

public void asfiasfgwef12() {
	int tsadflas=3;
	int masf11233=2;
	int[]wasdf1213= new int[10 +1];
	int[] vasf124l = new int[10 + I];
	int[][] ddasf1234p= new int[masf11233

你肯定很奇怪，这看上去代码似乎不像是正常写出来的代码呀？没错，这是这位同学在网络上购买了所谓的“保研综测套餐”，商家为逃避赛后查重，给这位同学发去了经过混淆的代码。然而经过技术支持方的努力，这位同学不仅被封禁，与 TA 购买了相同“套餐”的同学也利用技术手段全部查出，目前主办方已向警方报案，这些同学的“保研”梦很有可能会转变为“案底”梦……因此如果你在比赛前也购买了类似的服务，现在迷途知返还来得及——毕竟这个商家起码还做了一些努力，许多商家号称“一对一”，实际上将一份代码发给了数十位同学……

题外话，这个混淆方式是不是挺眼熟。

言归正传，这题已经构建一个模型，只要按要求编写即可，模拟。

#include <bits/stdc++.h>

using namespace std;

int judge(char c) {
    if (c >= 'a' && c <= 'z') return 1;
    else if (c >= 'A' && c <= 'Z') return 2;
    else if (c >= '0' && c <= '9') return 4;
    return 0;
}

int main() {
    int score = 0;
    int tot = 0, cnt = 0;
    string line;
    while (getline(cin, line)) {
        int i = 0;
        int n = line.size();
        while (i < n) {
            if (judge(line[i]) == 0) {
                i++;
                continue;
            }
            int j = i + 1;
            while (j < n && judge(line[j]) != 0) {
                j++;
            }
            int mask = 0;
            for (int t = i; t < j; t++) {
                mask |= judge(line[t]);
            }
            if (mask == 7) {
                score += 5;
            } else if (mask == 6 || mask == 5) {
                score += 3;
            } else if (mask == 3) {
                score += 1;
            }

            cnt++;
            tot += (j - i); 
            i = j;
        }
    }
    cout << score << '\n';
    cout << tot << " " << cnt << '\n';
    return 0;
}

RC-u2 谁进线下了？II

分值: 20分

题型: 阅读理解 + 模拟

需要注意:

1. 不要输出未参赛的队伍分数

#include <bits/stdc++.h>

using namespace std;

int tabs[] = {0, 25, 21, 18, 16, 15, 14, 13, 12, 11, 10,
    9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

int main() {
    int t;
    cin >> t;

    vector<int> vis(30);
    vector<int> scores(30);
    while (t-- > 0) {
        for (int i = 0; i < 20; i++) {
            int c, r;
            cin >> c >> r;
            scores[c - 1] += tabs[r];
            vis[c - 1] = 1;
        }
    }
    vector<array<int, 2>> arr;
    for (int i = 0; i < 30; i++) {
        arr.push_back({i, scores[i]});
    }
    sort(arr.begin(), arr.end(), [](auto &a, auto &b) {
       if (a[1] != b[1]) return a[1] > b[1];
        return a[0] < b[0];
    });
    int m = arr.size();
    for (int i = 0; i < m;i++) {
        if (vis[arr[i][0]] == 1) {
            cout << (arr[i][0] + 1) << " " << arr[i][1] << '\n';
        }
    }
    
    return 0;
}

RC-u3 势均力敌

分值: 25 分

思路: 枚举 + 折半查找(meet in middle)

利用 c++自带的permutation函数簇，生成所有的排列

当n=4时，排列最多为24个

此时有常规的思路，0-1背包，但值域太大的

考虑到24个，可以运用位运算枚举，然后折半加速

#include <bits/stdc++.h>

using namespace std;

struct K {
    int64_t k;
    int v;
    bool operator<(const K&lhs) const {
        if (k != lhs.k) return k < lhs.k;
        return v < lhs.v;
    }
};

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int& x: arr) cin >> x;

    sort(arr.begin(), arr.end());

    int64_t sum = 0;
    vector<int> vals;
    do {
        int w = 0;
        for (auto &v: arr) w = w * 10 + v;
        vals.push_back(w);
        sum += (int64_t)w * w;
    } while(next_permutation(arr.begin(), arr.end()));
    
    if (sum % 2 == 1) {
        return 0;
    }

    // meet in middle 的枚举技巧
    int cnt = vals.size() / 2;
    int mask = 1 << cnt;
    map<K, int> hp;
    for (int i = 0; i < mask; i++) {
        int64_t tsum = 0, z = 0;
        for (int j = 0; j < cnt; j++) {
            if ((i & (1 << j)) != 0) {
                tsum += (int64_t)vals[j+cnt] * vals[j + cnt];
                z ++;
            }
        }
        hp[K(tsum, z)] = i;
    }

    int ans1 = -1, ans2 = -1;
    for (int i = 0; i < mask; i++) {
        int64_t tsum = 0, z = 0;
        for (int j = 0; j < cnt; j++) {
            if ((i & (1 << j)) != 0) {
                tsum += (int64_t)vals[j] * vals[j];
                z ++;
            }
        }
        if (hp.find(K(sum/2 - tsum, cnt - z)) != hp.end()) {
            ans1 = i;
            ans2 = hp[K(sum/2 - tsum, cnt - z)];
            break;
        }
    }

    for (int i = 0; i < cnt; i++) {
        if ((ans1 & (1 << i)) != 0) {
            cout << vals[i] << '\n';
        }
    }
    for (int i = 0; i < cnt; i++) {
        if ((ans2 & (1 << i)) != 0) {
            cout << vals[i + cnt] << '\n';
        }
    }
    
    return 0;
}

RC-u4 City 不 City

分值: 30分

题型: 图论

其实就是变形版的Dijkstra，权值为(最短路径, 最小热度)

这边采用二分最小热度 + 最短路径验证

#include <bits/stdc++.h>

using namespace std;

struct K {
    int cost, idx;
    bool operator<(const K &lhr) const {
        return cost > lhr.cost;
    }
};

int main() {

    int n, m, s, e;
    cin >> n >> m >> s >> e;
    s--; e--;

    vector<int> arr(n);
    for (int &x: arr) cin >> x;

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

    // 引入二分算了
    int inf = 0x3f3f3f3f;
    function<int(int)> solve = [&](int limit) {
        vector<int> dp(n, inf);
        dp[s] = 0;
        priority_queue<K, vector<K>> pq;
        pq.push(K(0, s));
        
        while (!pq.empty()) {
            K cur = pq.top(); pq.pop();
        
            if (dp[cur.idx] < cur.cost) continue;
            if (cur.idx != s && arr[cur.idx] > limit) continue;
            
            for (auto &e: g[cur.idx]) {
                if (dp[e[0]] > cur.cost + e[1]) {
                    dp[e[0]] = cur.cost + e[1];
                    pq.push(K(dp[e[0]], e[0]));
                }
            }
        }
        return dp[e];
    };
    
    int base = solve(inf);
    if (base == inf) {
        cout << "Impossible\n"; 
    } else {
        int l = 0, r = inf;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int ret = solve(mid);
            if (ret == base) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        cout << base << " " << l << "\n";
    }
   
    return 0;
}

RC-u5 贪心消消乐

分值: 30分

思路: 前缀和+最大子数组和问题转化

不过我觉得这题，

在消除格子后，上面的物体下滑规则没有述说清晰

这时间复杂度，其实我把控不住了，每次贪心获取最大子矩阵的和，已经优化到$O(n^3)$

剩下的就是操作的次数了，感觉还是数据弱了

#include <bits/stdc++.h>

using namespace std;

const int64_t inf = 0x3f3f3f3f;
int solve(vector<vector<int>> &g, vector<int> &choice) {
    int n = g.size();

    // n * n
    vector<vector<int64_t>> pre(n + 1, vector<int64_t>(n + 1, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j];
            if (g[i][j] == 0) pre[i + 1][j + 1] += -inf * 2;
            else pre[i + 1][j + 1] += g[i][j];
        }
    }

    int64_t ansW = 0;

    // O(n^3)
    for (int j = 0; j < n; j++) {
        for (int k = 0; k <= j; k++) {
            int64_t acc = 0;
            int up = 0;
            for (int i = 0; i < n; i++) {
                int64_t d = pre[i+1][j+1] - pre[i+1][k] - pre[i][j+1] + pre[i][k];
                acc += d;
                if (acc < 0) {
                    acc = 0;
                    up = i + 1;
                    continue;
                }
                
                vector<int> tmp = {k+1, up + 1, j+1, i+1};
                if (acc > ansW) {
                    ansW = acc;
                    choice = {k+1, up + 1, j+1, i+1};
                } else if (acc == ansW && tmp < choice) {
                    choice = {k+1, up+1, j+1, i+1};
                }

            }
        }
    }

    return ansW;
}

void fall(vector<vector<int>> &g, vector<int> &choice) {
    int n = g.size();

    for (int i = choice[1] - 1; i <= choice[3] - 1; i++) {
        for (int j = choice[0] - 1; j <= choice[2] -1 ; j++) {
            g[i][j] = 0;
        }
    }  
    
    int h = choice[3] - choice[1] + 1;
    for (int i = choice[1] - 2; i >= 0; i--) {
        for (int j = choice[0] - 1; j <= choice[2] -1 ; j++) {
            g[i + h][j] = g[i][j];
            g[i][j] = 0;
        }
    }
}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    
    vector<vector<int>> g(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }

    int64_t acc = 0;
    while (true) {
        vector<int> choice;
        int64_t ans = solve(g, choice);
        if (ans == 0) {
            break;
        }
        cout << "(" << choice[0] << ", " << choice[1] << ") (" << choice[2] << ", " << choice[3] << ") " << ans << '\n';
        acc += ans;
        fall(g, choice);
    }
    cout << acc << '\n';

    return 0;
}

写在最后