当前位置：首页 > news >正文

2021 RoboCom 世界机器人开发者大赛-本科组（初赛）解题报告 | 珂学家

news 2025/7/20 21:25:28

前言

在这里插入图片描述

题解

睿抗机器人开发者大赛CAIP-编程技能赛-历年真题汇总

2021 RoboCom 世界机器人开发者大赛-本科组（初赛）

早期的一场比赛，题数只有4题，但是题型风格确实一脉相承。

在这里插入图片描述

7-1 懂的都懂

分值：20分
思路：枚举+预处理

在这里插入图片描述

可以事先枚举圆图任意四点构成的所有平均值，然后查询遍历新图点是否在原图平均值集合中。

#include <bits/stdc++.h>using namespace std;int main() {int n, k;cin >> n >> k;vector<int> arr(n);for (int &x: arr) cin >> x;sort(arr.begin(), arr.end());set<int> avg;int nn = arr.size();for (int i = 0; i < nn; i++) {for (int j = i + 1; j < nn; j++) {for (int k = j + 1; k < nn; k++) {for (int s = k + 1; s < nn; s++) {int acc = arr[i] + arr[j] + arr[k] + arr[s];if (acc % 4 == 0) {avg.insert(acc / 4);}}}}}for (int i = 0; i < k; i++) {int m;cin >> m;bool f = true;for (int j = 0; j < m; j++) {int v; cin >> v;if (avg.find(v) == avg.end()) {f = false;}}cout << (f ? "Yes":"No") << "\n";}return 0;
}

7-2 芬兰木棋

分值：25分
思路: 模拟+贪心

在这里插入图片描述

按圆心，射线分组

如果要得分最高，其次投掷次数最小。
可以得到一个贪心策略
$得分大于 1 的单独投掷一次，得分为 1 相邻的需要合并$

剩下的就是模拟计算，涉及的2个技巧

分组循环
如何构建分组，向量采用最简表示法(即除以最大公约数，同时保留±符号）

这题还是偏阅读理解，不过题是真心好题。

#include <bits/stdc++.h>using namespace std;struct T {int x, y, v;T(int x, int y, int v) : x(x), y(y), v(v) {}
};int main() {int n;cin >> n;int64_t acc = 0;int cnt = 0;map<array<int64_t,2>, vector<T>> hp; for (int i = 0; i < n; i++) {int64_t x, y, v;cin >> x >> y >> v;int64_t g = __gcd(abs(x), abs(y));hp[{x/g, y/g}].push_back(T(x, y, v));}for (auto &[k, arr]: hp) {sort(arr.begin(), arr.end(), [](auto &a, auto &b) {if (a.x != b.x) return a.x < b.x;return a.y < b.y;});int in = arr.size();int i = 0;while (i < in) {if (arr[i].v != 1) {acc += arr[i].v;cnt++;i++;continue;}int j = i + 1;while (j < in && arr[j].v == 1) {j++;}acc += (j - i);cnt++;i = j;}}cout << acc << " " << cnt << "\n";return 0;
}

7-3 打怪升级

分值: 25分

思路: 最短路

在这里插入图片描述

$f l oy d + 路径回溯构造$

这边是二元，能量消耗+总回报

所以可以引入结构体，并重载小于操作符，这样floyd整体结构可以完整保留。

踩过的坑：

空降位置，是到所有的堡垒的最大值消耗值最小，而不是后续查询的堡垒集合（真的太坑了，T_T)

时间复杂度分析: $O(n3),n≤1000O(n^3), n\le 1000$ , 但是时间给了5秒

在这里插入图片描述

#include <bits/stdc++.h>using namespace std;struct W {int w1, w2;  bool operator<(const W&o) const {if (w1 != o.w1) return w1 < o.w1;return w2 > o.w2;}W operator+(const W&o) const {return {w1 + o.w1, w2 + o.w2};}
};const int inf = 1e9;void dfs(int u, int v, vector<vector<int>> &path, vector<int> &trace) {if (u == v) return;if (path[u][v] == -1) {trace.push_back(v);return;}int k = path[u][v];dfs(u, k, path, trace);dfs(k, v, path, trace);
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n, m;cin >> n >> m;vector<vector<W>> g(n, vector<W>(n, {inf, inf}));vector<vector<int>> path(n, vector<int>(n, -1));for (int i = 0; i < n; i++) g[i][i] = {0, 0};for (int i = 0; i < m; i++) {int u, v, w1, w2;cin >> u >> v >> w1 >> w2;u--; v--;g[u][v] = g[v][u] = {w1, w2};}for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {if (g[i][k].w1 == inf) continue;for (int j = 0; j < n; j++) {if (g[i][k] + g[k][j] < g[i][j]) {g[i][j] = g[i][k] + g[k][j];path[i][j] = k;}}}}int k;cin >> k;vector<int> target(k);for (int &x: target) {cin >> x;x--;}int ans = inf;int s = -1;for (int i = 0; i < n; i++) {int tmp = 0;// 到所有的点，不是查询的点for (int j = 0; j < n; j++) {tmp = max(tmp, g[i][j].w1);}if (ans > tmp) {ans = tmp;s = i;}}cout << (s + 1) << "\n";for (int v: target) {vector<int> trace = {s};dfs(s, v, path, trace);int tn = trace.size();for (int i = 0; i < tn; i++) {cout << (trace[i] + 1) << (i < tn - 1 ? "->" : "\n");}cout << g[s][v].w1 << " " << g[s][v].w2 << "\n";}return 0;
}

7-4 疫情防控

分值: 30分
思路：逆序+并查集

连通性的问题，往往可以借助并查集，删点/删边，往往可以逆序演变为加点/加边，正所谓正难则反。

这题也属于离线计算的范畴。

#include <bits/stdc++.h>using namespace std;struct Dsu {int n;vector<int> arr;Dsu(int n): n(n), arr(n, -1) {}int find(int u) {if (arr[u] == -1) return u;return arr[u] = find(arr[u]);}void merge(int u, int v) {int a = find(u), b = find(v);if (a != b) {arr[a] = b;}}bool same(int u, int v) {return find(u) == find(v);}
};struct Q {int c;vector<array<int, 2>> es;  
};int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n, m, d;cin >> n >> m >> d;// 逆序+并查集+检索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);}vector<bool> vis(n, true);vector<Q> qs;for (int i = 0; i < d; i++) {Q q;cin >> q.c;q.c--;int x; cin >> x;for (int j = 0; j < x; j++) {int u, v;cin >> u >> v; u--; v--;q.es.push_back({u, v});}vis[q.c] = false;qs.push_back(q);}// 逆序处理Dsu dsu(n);for (int i = 0; i < n; i++) {if (vis[i]) {for (int v: g[i]) {if (vis[v]) {dsu.merge(i, v);}}}}vector<int> res(d);for (int i = d - 1; i >= 0; i--) {int tmp = 0;for (auto &e: qs[i].es) {if (!dsu.same(e[0], e[1])) {tmp++;}}res[i] = tmp;vis[qs[i].c] = true;for (auto e: g[qs[i].c]) {if (vis[e]) {dsu.merge(qs[i].c, e);}}}for (int i = 0; i < d; i++) {cout << res[i] << "\n";}return 0;
}