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

前言

题解

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

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

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

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

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

RC-u1睿抗，启动！

分值: 15分

思路: 分组循环

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

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

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

#include 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(K1,K2)min(K_1, K_2)min(K1​,K2​) 最大化
2. 最后求的结果为，在1的基础上，max(K1,K2)∗(8−n)3max(K_1, K_2) * (8-n)^3max(K1​,K2​)∗(8−n)3

这题难在阅读理解， T_T.

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

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

#include 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 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 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 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; // erase  acc -= 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; // erase  acc -= 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;}

写在最后