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

---

前言

---

题解

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

vp了下，题目挺好的，难度也适中，但是彻底红温了。

第二题，题意不是那么清晰，$Min(K_1,K_2)$容易求，但是题目最后要求真的很难get到点（缺乏对case的必要解释）。

第四题，是一道裸的拓扑排序，但是卡内存，关于这个仁者见仁智者见智。

如果再备战 睿抗 CAIP 编程赛，需要学习一些内存优化的技巧。

---

RC-u1 睿抗，启动！

分值: 15分

思路: 分组循环

这题，有一处地方有点小意外

如果 S 为 yourname，请将 S 改为你的名字的拼音拼写

其实我还是觉得太突兀了，这种莫名SPJ的元素

#include <bits/stdc++.h>using namespace std;int tag(char c) {if (c >= 'A' && c <= 'Z') return 0;else if (c >= 'a' && c <= 'z') return 1;return 2;
}int main() {int n;cin >> n;string s;cin >> s;if (s == "yourname") s = "zhangsan";string ns = s;for (int i = 0; i < n; i++) {int m = ns.size();for (int j = 0; j < m; j++) {int x = tag(ns[j]);if (x == 0) {ns[j] = (char)((ns[j] - 'A' + 1) % 26 + 'A');} else if (x == 1) {ns[j] = (char)((ns[j] - 'a' + 25) % 26 + 'a');}}int k = 0;while (k < m) {int x = tag(ns[k]);int k2 = k + 1;while (k2 < m && tag(ns[k2]) == x) {k2 ++;}if (k2 - k >= 3) {for (int j = k; j < k2; j++) {if (x == 0) {ns[j] = tolower(ns[j]);} else if (x == 1) {ns[j] = toupper(ns[j]);}}}k = k2;}}cout << s << endl;cout << ns << endl;return 0;
}

---

RC-u2 桌游猜谜

分值: 20分

考点: 集合论(二进制) + 枚举技巧

题目其实相当的晦涩

1. 选择3种颜色，并选择[L, R]范围，其$min(K_1,K_2)$ 最大化
2. 最后求的结果为，在1的基础上，$max(K_1,K_2)\ast (8-n{)}^3$

这题难在阅读理解， T_T.

代码的话，其实分了2个阶段

1. 二进制枚举划分集合
2. 穷举各种可能性，然后枚举[L, R]区间的方案数

#include <bits/stdc++.h>using namespace std;int main() {int t;cin >> t;while (t-- > 0) {int n;cin >> n;vector<vector<bool>> vis(6, vector<bool>(9, false));for (int i = 0; i < n; i++) {for (int j = 0; j < 6; j++) {int v; cin >> v;vis[j][v] = true;}}int target = -1;int ans = 0;int range = 1 << 6;for (int i = 0; i < range; i++) {int cnt = __builtin_popcount(i);if (cnt != 3) continue;vector<int> stat(24 + 1);function<void(int,int,int)> dfs;dfs = [&](int s, int acc, int mask) {if (s == 6) {stat[acc]++;return;}if (((1 << s) & mask) != 0) {dfs(s + 1, acc, mask);} else {for (int j = 1; j <= 8; j++) {if (!vis[s][j]) {dfs(s + 1, acc + j, mask);}}}};dfs(0, 0, i);int pow3 = (8 - n) * (8 - n) * (8 - n); // 枚举 L-R for (int s = 0; s <= 24; s++) {int acc = 0;for (int e = s; e <= 24; e++) {acc += stat[e];int tmp = min(pow3 - acc, acc);if (target < tmp) {target = tmp;ans = max(pow3 - acc, acc) * pow3;}}}            }cout << ans << "\n";}return 0;
}

---

RC-u3 兰州拉面派餐系统

分值: 25分

思路: 模拟

这类调度模型题，其实很有技巧性

因为任务是一开始预定的，所以这题相对容易些

引入优先队列，对煮面篮子(worker)进行调度

需要注意的是

1. 按是否空闲有限调度
2. 都空闲的提前下，按编号大小调度

#include <bits/stdc++.h>using namespace std;struct E {int id; // 编号int at; // 时间点E() {}E(int id, int at) : id(id), at(at) {}bool operator<(const E& lhs) const {if (at != lhs.at) return at < lhs.at;return id < lhs.id;}
};int main() {int n, m, q;cin >> n >> m >> q;vector<int> cost(n + 1);for (int i = 1; i <= n; i++) {cin >> cost[i];}// 用优先队列驱动，事件调度auto comp = [](auto &a, auto &b) { return b < a; };priority_queue<E, vector<E>, decltype(comp)> pq;for (int i = 1; i <= m; i++) pq.push(E(i, 0));vector<array<int, 2>> ans;vector<int> rec(m + 1, 0);for (int i = 1; i <= q; i++) {int v; cin >> v;E e = pq.top(); pq.pop();rec[e.id]++;ans.push_back({e.at + cost[v], i});pq.push(E(e.id, e.at+cost[v]));}sort(ans.begin(), ans.end());for (int i = 0; i < q; i++) {auto &e = ans[i];cout << e[1] << ":" << e[0] << " \n"[i == q - 1];}for (int i = 1; i <= m; i++) {cout << rec[i] << " \n"[i == m];}return 0;
}

---

RC-u4 拆积木

分值: 30 分

思路：拓扑排序

积木依赖于上下相邻关系，抓住这个关键点即可

这边需要使用到链式前向星来建图，不然最后2个case会MLE。

内存优化点:

1. 滚动数组
2. 链式前向星

#include <bits/stdc++.h>using namespace std;const int M = 1'000'000 + 5;int idx = 0;
int h[M];
struct Edge {int to;int next;
} edges[M];
int degree[M];void addEdge(int u, int v) {edges[idx].to = v;edges[idx].next = h[u];h[u] = idx;idx++;
}int mat[2][M];int main() {int n, m;cin >> n >> m;memset(h, -1, sizeof(int) * M);memset(degree, -1, sizeof(int) * M);int cnt = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> mat[i&1][j];int v = mat[i&1][j];if (degree[v] == -1) {degree[v] = 0;cnt++;}if (i > 0 && mat[1^(i&1)][j] != mat[i&1][j]) {addEdge(mat[1^(i&1)][j], mat[i&1][j]);degree[v]++;}}}priority_queue<int, vector<int>, greater<int>> pq;for (int i = 0; i < M; i++) {if (degree[i] == 0) {pq.push(i);}}vector<int> ans;while (!pq.empty()) {int u = pq.top(); pq.pop();ans.push_back(u);for (int i = h[u]; i != -1; i = edges[i].next) {int v = edges[i].to;if (--degree[v] == 0) {pq.push(v);}}}int rn = ans.size();if (cnt != ans.size()) {for (int i = 0; i < ans.size(); i++) {cout << ans[i] << " ";}cout << "Impossible\n";} else {for (int i = 0; i < ans.size(); i++) {cout << ans[i] << " \n"[i == ans.size() - 1];}}return 0;
}

---

RC-u5 栈与数组

分值: 30分

思路: 预处理， 二分+DP校验

$对于C1，C2的前i和j项，pre[i][j],其最终留下的数个数是确定的$

因此利用$O(n\ast m)$来构建pre数组

后续的二分+DP校验，就相对容易了

本质就是检查

$$dp[i-1][j]\wedge pre[i-1][j]+1\le threshold\text{\hspace{1em}(1)}$$
$$dp[i][j-1]\wedge pre[i][j-1]+1\le threshold\text{\hspace{1em}(2)}$$
$$(1),(2)任意一个满足，同时pre[i][j]\le threshold,那么dp[i][j]=true$$

这样整体的时间复杂度为

$$O(n\ast m\ast log(n+m))$$

#include <bits/stdc++.h>using namespace std;const int inf = 0x3f3f3f3f;int main() {int t;cin >> t;while (t-- > 0) {int n, m, k;cin >> n >> m >> k;vector<int> c1(n), c2(m);for (int &x: c1) cin >> x;for (int &x: c2) cin >> x;// *) // 预处理状态vector<vector<int>> pre(n+1, vector<int>(m + 1, inf));    fill(pre[0].begin(), pre[0].end(), 0);for (int i = 0; i <= n; i++) {map<int, int> cnt;int acc = 0;for (int j = 1; j <= i; j++) {int v = c1[j - 1];cnt[v]++;acc++;if (cnt[v] == k) {cnt[v] = 0; // eraseacc -= k;}}pre[i][0] = acc;for (int j = 1; j <= m; j++) {int v = c2[j - 1];cnt[v]++;acc++;if (cnt[v] == k) {cnt[v] = 0; // eraseacc -= k;}pre[i][j] = acc;}}function<bool(int)> check = [&](int up) {vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));dp[0][0] = 1;for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {if (i == 0 && j == 0) continue;if (pre[i][j] > up) continue;if (i - 1 >= 0 && pre[i - 1][j] + 1 <= up && dp[i - 1][j] == 1) dp[i][j] = 1;if (j - 1 >= 0 && pre[i][j - 1] + 1 <= up && dp[i][j - 1] == 1) dp[i][j] = 1;}}return dp[n][m] == 1;};// 二分 + dp(布尔)int l = 1, r = n + m;while (l <= r) {int mid = l + (r - l) / 2;if (check(mid)) {r = mid - 1;} else {l = mid + 1;}}cout << l << "\n";}return 0;
}

---

写在最后