---

前言

---

題解

2024 睿抗機器人開發者大賽CAIP-編程技能賽-專科組（國賽），陳越姐姐出題。

國賽比省賽，難度增強了不少，題目就剩下4個題了。

涉及堆棧，hash表，優先隊列等高階數據結構的使用，也有搜索等算法的使用。

---

RC-v1 簡版2048

分值: 20

思路: 棧的使用

一維2048游戲，需要注意級聯反應, 退出條件

#include <bits/stdc++.h>using namespace std;int main() {int n, m;cin >> n >> m;vector<int> stk;for (int i = 0; i < n; i++) {int v; cin >> v;// 級聯反應while (!stk.empty() && stk.back() == v) {stk.pop_back();v++;}if (stk.size() < m) stk.push_back(v);else break;  // 這個break很關鍵}for (int i = 0; i < stk.size(); i++) {cout << stk[i] << " \n"[i == stk.size() - 1];}return 0;
}

---

RC-v2 為 i 做 e

分值: 25分

思路：模擬 + hash表運用

#include <bits/stdc++.h>using namespace std;int main() {int n;cin >> n;map<string, int> mp;for (int i = 0; i < n; i++) {string s, x;cin >> s >> x;mp[s] = (x[0] == 'i' ? 0 : 1);}vector<int> ans;int m;cin >> m;for (int i = 0; i < m; i++) {int k; cin >> k;int acc = 0;for (int j = 0; j < k; j++) {string s;cin >> s;acc += mp[s];}if (acc == 0) ans.push_back(i + 1);}if (ans.empty()) cout << "None" << endl;else {for (int i = 0; i < ans.size(); i++) {cout << ans[i] << " \n"[i== ans.size() - 1];}}return 0;
}

---

RC-v3 乘法小宇宙

分值: 25分

思路： 搜索

從圖中挖掘限制條件:

1. a有n位
2. b是2位
3. c是n+1位
4. d是n+1位
5. p是n+2位

同時abcdp都是基于s集合

因為集合s最多5個元素，因此可以暴力全枚舉，即$O(5^{10}<10^7)$

#include <bits/stdc++.h>using namespace std;bool check(int64_t v, vector<int> &vis) {while (v > 0) {int r = (int)(v % 10);if (vis[r] == 0) return false;v /= 10;}return true;
}bool check2(int64_t v, int n) {int cnt = 0;while (v > 0) {v /= 10;cnt++;}return cnt == n;
}int n, k;
vector<int> s;
vector<int> vis(10);
vector<array<int, 2>> bs;vector<array<int, 2>> res;void dfs(int i, int av) {if (i == n) {for (auto &e: bs) {int64_t cv = (int64_t)av * e[1];int64_t dv = (int64_t)av * e[0];if (check(cv, vis) && check2(cv, n + 1) && check(dv, vis) && check2(dv, n + 1) && check(dv * 10 + cv, vis) && check2(dv * 10 + cv, n + 2)) {res.push_back({av, e[0] * 10 + e[1]});}}return;} for (int &v: s) {dfs(i + 1, av * 10 + v);}
}int main() {cin >> n >> k;for (int i = 0; i < k; i++) {int v;cin >> v;vis[v] = 1;s.push_back(v);}sort(s.begin(), s.end());for (auto &b1: s) {for (auto &b2: s) {bs.push_back({b1, b2});}}dfs(0, 0);if (res.empty()) {cout << "No Solution\n";} else {for (auto &e: res) {cout << e[0] << " " << e[1] << "\n";}}return 0;
}

---

RC-v4 實時中位線

分值: 30分

思路: 對頂堆

這是對頂堆的板子題，不過其值域被范圍被限定100，其實是道值域統計題

#include <bits/stdc++.h>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n;cin >> n;// 利用對頂堆來實現吧priority_queue<int, vector<int>, less<int>> pq1;priority_queue<int, vector<int>, greater<int>> pq2;for (int i = 0; i < n; i++) {int v;cin >> v;if (i % 2 == 0) {if (!pq2.empty() && pq2.top() < v) {pq1.push(pq2.top()); pq2.pop();pq2.push(v);} else {pq1.push(v);    }cout << pq1.top() << ".0" << '\n';} else {if (!pq1.empty() && pq1.top() > v) {pq2.push(pq1.top()); pq1.pop();pq1.push(v);} else {pq2.push(v);}cout << fixed << setprecision(1) <<  (pq1.top() + pq2.top()) / 2.0 << '\n';}}return 0;
}

---

寫在最后