2022 RoboCom 世界机器人开发者大赛(睿抗 caip) -高职组（国赛）解题报告 | 科学家

---

前言

---

题解

2022 RoboCom 世界机器人开发者大赛(睿抗 caip) -高职组（国赛）。
最后一题还考验能力，需要找到合适的剪枝。

---

RC-v1 智能管家

分值: 20分

签到题，map的简单实用

#include <bits/stdc++.h>using namespace std;int main() {int n, m;ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cin >>n >> m;vector<int> hp(n + 1);for (int i = 0; i < n; i++) {int id; cin >> id;hp[i + 1] = id;} int q;cin >> q;while (q-- > 0) {map<int, int> cnt;int w;while ( cin >> w && w > 0) {cnt[hp[w]]++;}bool f = false;for (auto &e: cnt) {if (f) cout << " ";f = true;cout << "B" << e.first << "-" << e.second;}cout << "\n";}return 0;
}

---

RC-v2 智能陪护

分值: 25分

具体可查看

RC-v2 智能陪护 争议解读

#include <bits/stdc++.h>using namespace std;struct T {string name;int op;string at;T(string name, int op, string at): name(name), op(op), at(at) {}
};int main() {int n, m;cin >> n >> m;deque<string> man;deque<string> robot;for (int i = 1; i <= n; i++) robot.push_back(to_string(i));vector<T> seq;for (int i = 0; i < m; i++) {string name, at;int op;cin >> name >> op >> at;seq.push_back(T(name, op, at));}sort(seq.begin(), seq.end(), [](auto &a, auto &b) {if (a.at != b.at) return a.at < b.at;if (a.op != b.op) return a.op < b.op;return a.name < b.name;});int idx = 0;map<string, int> hp;int ptr = 0;vector<array<string, 2>> res;for (auto &e: seq) {        if (e.op == 1) {hp[e.name] = idx++;if (robot.empty()) {res.push_back({e.name, ""});}else {string v = robot.front(); robot.pop_front();res.push_back({e.name, v});cout << e.name << " - " << v << "\n";}} else {           int pos = hp[e.name];string v = res[pos][1];if (v == "") {// passres[pos][1] = "NONE";cout << res[pos][0] << " - " << "NONE" << "\n";} else {robot.push_back(v);while (!robot.empty() && ptr < res.size()) {if (res[ptr][1] != "") {ptr++;} else {string v = robot.front(); robot.pop_front();res[ptr][1] = v;cout << res[ptr][0] << " - " << v << "\n";ptr++;}}}}}    while (!robot.empty()) {string v = robot.front(); robot.pop_front();cout << v;cout << " \n"[robot.empty()];}return 0;
}

RC-v3 智能护理中心统计

分值：25分

考察点: 建树(指向父节点+子节点)

因为关系链最多m($m\le 10^5$), 操作次数$10^2$, 因此每次操作全量遍历即可，整个时间复杂度最多$10^7$

#include <bits/stdc++.h>using namespace std;struct Node {int v = 0;string fa = "";set<string> childs;Node() {}Node(int v) : v(v) {}
};map<string, Node> mp;bool isNum(const string &v) {return v[0] >= '0' && v[0] <= '9';
}int dfs(const string &u) {int res = mp[u].v;for (const string &v: mp[u].childs) {res += dfs(v);}return res;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);int n, m;cin >> n >> m;for (int i = 0; i < m; i++) {string u, v;cin >> u >> v;if (!mp.count(u)) {mp[u] = Node(isNum(u)?1:0);}if (!mp.count(v)) {mp[v] = Node(0);}mp[v].childs.insert(u);mp[u].fa = v;}// 处理操作string op;while (cin >> op && op != "E") {if (op == "T") {string u, v;cin >> u >> v;if (!mp.count(v)) {mp[v] = Node(0);}if (!mp.count(u)) {mp[u] = Node(1);}if (!mp[u].fa.empty()) {mp[mp[u].fa].childs.erase(u);}     mp[v].childs.insert(u);mp[u].fa = v;} else {string u;cin >> u;if (mp.count(u) == 0) cout << (isNum(u) ? 1 : 0) << "\n";else {cout << dfs(u) << "\n";}}}return 0;
}

---

RC-v4 情人节的蜜语

分值: 30分

思路: dfs + 剪枝

说白了在n*m的矩阵中，寻找长度为p的模式，$n,m\le 100,p\le 20$

纯dfs搜索的话，拿不到满分，大概是25/30的样子。

那这边就需要考虑如何优化的问题了。

$$引入类似布隆过滤器的机制$$

引入$can[i][x][y],表示第i匹配，xy坐标开始可能性，这个can不追求去重$

如何理解这个不去重呢？

1. 如果can为true，精确结果不保证一定为true
2. 如果can为false，最终结果一定为false

这就是所谓的 False Positive

这个预处理后，在dfs优化，可以大大减低搜索量，就能30/30。

#include <bits/stdc++.h>
using namespace std;int m, n, L;
vector<string> grid;
string target;
// can[i][x][y]: 从 (x,y) 匹配到 target[i] 起，能否完成剩余匹配
bool can_[21][100][100];
bool vis[100][100];
vector<pair<int,int>> path;
int dx[8]={-1,-1,-1,0,0,1,1,1}, dy[8]={-1,0,1,-1,1,-1,0,1};
bool found=false;// 剪枝后的 DFS
void dfs(int x, int y, int idx){if(found) return;path.emplace_back(x,y);if(idx+1 == L){found = true;return;}vis[x][y] = true;for(int d=0; d<8; d++){int nx = x+dx[d], ny = y+dy[d];if(nx<0||nx>=m||ny<0||ny>=n) continue;if(vis[nx][ny]) continue;if(grid[nx][ny] != target[idx+1]) continue;if(!can_[idx+1][nx][ny]) continue;  // 剪掉不可能完成的dfs(nx, ny, idx+1);if(found) break;}if(!found){vis[x][y]=false;path.pop_back();}
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> m >> n;grid.resize(m);for(int i=0;i<m;i++) cin >> grid[i];cin >> target;L = target.size();// 1) 后向可达性 DPmemset(can_, 0, sizeof(can_));// 最后一层for(int x=0;x<m;x++){for(int y=0;y<n;y++){if(grid[x][y] == target[L-1])can_[L-1][x][y] = true;}}// 反向递推for(int i=L-2; i>=0; i--){for(int x=0;x<m;x++){for(int y=0;y<n;y++){if(grid[x][y] != target[i]) continue;for(int d=0; d<8; d++){int nx=x+dx[d], ny=y+dy[d];if(nx<0||nx>=m||ny<0||ny>=n) continue;if(can_[i+1][nx][ny]){can_[i][x][y] = true;break;}}}}}// 2) 从可达的起点开始 DFSfor(int x=0; x<m && !found; x++){for(int y=0; y<n && !found; y++){if(grid[x][y]==target[0] && can_[0][x][y]){dfs(x,y,0);}}}// 输出vector<string> out(m, string(n,'.'));for(auto &p: path){out[p.first][p.second] = grid[p.first][p.second];}for(int i=0;i<m;i++){cout << out[i] << "\n";}return 0;
}

---

写在最后