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

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

news 2025/5/18 14:07:39

前言

在这里插入图片描述

题解

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

最后一题是搜索+剪枝，还要注意整数溢出的问题。

在这里插入图片描述

RC-v1 另类单位圆

分值: 20分

思路: 模拟

全枚举即可，时间复杂度为 $O(10^8)$

#include <bits/stdc++.h>using namespace std;int main() {int a, b;cin >> a >> b;int minV = (int)1e9;int minX = 0, minY = 0;int maxV = 0;int maxX = 0, maxY = 0;for (int i = a; i <= b; i++) {for (int j = a; j <= b; j++) {int v = abs(i * i - i * j - j * j);if (v != 1) continue;int ov = i + j;if (minV > ov) {minV = ov;minX = i; minY = j;}if (maxV < ov) {maxV = ov;maxX = i; maxY = j;}}}cout << "(" << minX << ", " << minY << ")\n";cout << "(" << maxX << ", " << maxY << ")\n";return 0;
}

RC-v2 含茶量

分值： 25分

思路: api调用题 + 模拟

归一化，把大写字符串统一为小写字符串
用暴力匹配字符串即可，不需要用kmp，z函数，因此chatgp固定且不长

#include <bits/stdc++.h>using namespace std;struct T {string k; int v;T(string k, int v) : k(k), v(v) {}
};int main() {string line;getline(cin, line);int n = atoi(line.c_str());vector<T> vec;map<string, int> hp;while (n-- > 0) {string name;getline(cin, name);getline(cin, line);for (size_t i = 0; i < line.size();i++) {if (line[i] >= 'A' && line[i] <= 'Z') {line[i] = line[i] - 'A' + 'a';}}int cnt = 0;int pos = 0;while ((pos = line.find("chatgpt", pos)) != string::npos) {pos += 7;cnt++;}if (cnt > 0) hp[name] += cnt;}for (auto &e: hp) vec.push_back(T(e.first, e.second));sort(vec.begin(), vec.end(), [](auto &a, auto &b) {if (a.v != b.v) return a.v > b.v;return a.k < b.k;});int limit = vec.size() > 3 ? 3 : vec.size();for (int i = 0; i < limit; i++) {cout << vec[i].k << " " << vec[i].v << "\n";}return 0;
}

RC-v3 软件窗体的层级管理

分值：25分

在这里插入图片描述

思路: 层序bfs

这题的关键点在于，树的节点个数n ( $\le 1000$ ), 因此，每次查询按该节点分层bfs即可。

时间复杂度为 $O (n * q)$

#include <bits/stdc++.h>using namespace std;void solve(vector<vector<int>> &g, int s) {// 层序遍历int ans = 0, ansLevel = 0;deque<int> que;que.push_back(s);int level = 0;while (!que.empty()) {int sz = que.size();// ans = max(ans, sz);level++;if (ans < sz) {ans = sz;ansLevel = level;}for (int i = 0; i < sz; i++) {int u = que.front(); que.pop_front();for (int v: g[u]) {que.push_back(v);}}}cout << ansLevel << " " << ans << "\n";
}int main() {int n, m;cin >> n >> m;vector<vector<int>> g(n);for (int i = 0; i < m; i++) {int id, k;cin >> id >> k;for (int j = 0; j < k; j++) {int next;cin >> next;g[id].push_back(next);}}int q;cin >> q;for (int i = 0; i < q; i++) {int u; cin >> u;solve(g, u);}return 0;
}

RC-v4 加号放哪里

分值: 30分

思路: 搜索+剪枝

为何贪心不行，比如从中间切割

举个特殊的例子

100000000000001

这种形态，显然中间切割不是最佳的

所以采用搜索，同时需要引入剪枝的策略，比如贪心获得一个近似解，加速搜索。

需要注意： $10^{20} 超过int64范围$

用uint64_t，或者__int128来规避这个问题


#include <bits/stdc++.h>using namespace std;using i128 = __int128;i128 convert(string s) {i128 r = 0;for (auto &c: s) {r = r * 10 + (c - '0');}return r;
}string i128string(i128 v) {string r;while (v > 0) {r.push_back((char)(v % 10 + '0'));v /= 10;}reverse(r.begin(), r.end());return r;
}const int inf = 0x3f3f3f3f;
int gAns = inf;
int gMin = 9;void dfs(int d, string s) {i128 v = convert(s);if (v < 10) {if (gAns > d) {gAns = d;gMin = v;} else if (gAns == d && gMin > v) {gMin = v;}return;}// cutoffif (gAns < d) return;int n = s.size();for (int i = 0; i < n - 1; i++) {i128 left = convert(s.substr(0, i+1));i128 right = convert(s.substr(i + 1));i128 v = left + right;dfs(d + 1, i128string(v));}
}int main() {string s;cin >> s;dfs(0, s);cout << gAns << " " << gMin << "\n";return 0;
}