---

前言

---

題解

2024 睿抗機器人開發者大賽CAIP-編程技能賽-本科組(國賽)。

國賽比省賽難一些，做得汗流浹背，T_T.

---

RC-u1 大家一起查作弊

分值: 15分

這題真的太有意思，看看描述

在今年的睿抗比賽上，有同學的提交代碼如下：

public void asfiasfgwef12() {int tsadflas=3;int masf11233=2;int[]wasdf1213= new int[10 +1];int[] vasf124l = new int[10 + I];int[][] ddasf1234p= new int[masf11233

你肯定很奇怪，這看上去代碼似乎不像是正常寫出來的代碼呀？沒錯，這是這位同學在網絡上購買了所謂的“保研綜測套餐”，商家為逃避賽后查重，給這位同學發去了經過混淆的代碼。然而經過技術支持方的努力，這位同學不僅被封禁，與 TA 購買了相同“套餐”的同學也利用技術手段全部查出，目前主辦方已向警方報案，這些同學的“保研”夢很有可能會轉變為“案底”夢……因此如果你在比賽前也購買了類似的服務，現在迷途知返還來得及——畢竟這個商家起碼還做了一些努力，許多商家號稱“一對一”，實際上將一份代碼發給了數十位同學……

題外話，這個混淆方式是不是挺眼熟。

言歸正傳，這題已經構建一個模型，只要按要求編寫即可，模擬。

#include <bits/stdc++.h>using namespace std;int judge(char c) {if (c >= 'a' && c <= 'z') return 1;else if (c >= 'A' && c <= 'Z') return 2;else if (c >= '0' && c <= '9') return 4;return 0;
}int main() {int score = 0;int tot = 0, cnt = 0;string line;while (getline(cin, line)) {int i = 0;int n = line.size();while (i < n) {if (judge(line[i]) == 0) {i++;continue;}int j = i + 1;while (j < n && judge(line[j]) != 0) {j++;}int mask = 0;for (int t = i; t < j; t++) {mask |= judge(line[t]);}if (mask == 7) {score += 5;} else if (mask == 6 || mask == 5) {score += 3;} else if (mask == 3) {score += 1;}cnt++;tot += (j - i); i = j;}}cout << score << '\n';cout << tot << " " << cnt << '\n';return 0;
}

---

RC-u2 誰進線下了？II

分值: 20分

題型: 閱讀理解 + 模擬

需要注意:

1. 不要輸出未參賽的隊伍分數

#include <bits/stdc++.h>using namespace std;int tabs[] = {0, 25, 21, 18, 16, 15, 14, 13, 12, 11, 10,9, 8, 7, 6, 5, 4, 3, 2, 1, 0};int main() {int t;cin >> t;vector<int> vis(30);vector<int> scores(30);while (t-- > 0) {for (int i = 0; i < 20; i++) {int c, r;cin >> c >> r;scores[c - 1] += tabs[r];vis[c - 1] = 1;}}vector<array<int, 2>> arr;for (int i = 0; i < 30; i++) {arr.push_back({i, scores[i]});}sort(arr.begin(), arr.end(), [](auto &a, auto &b) {if (a[1] != b[1]) return a[1] > b[1];return a[0] < b[0];});int m = arr.size();for (int i = 0; i < m;i++) {if (vis[arr[i][0]] == 1) {cout << (arr[i][0] + 1) << " " << arr[i][1] << '\n';}}return 0;
}

---

RC-u3 勢均力敵

分值: 25 分

思路: 枚舉 + 折半查找(meet in middle)

利用 c++自帶的permutation函數簇，生成所有的排列

當n=4時，排列最多為24個

此時有常規的思路，0-1背包，但值域太大的

考慮到24個，可以運用位運算枚舉，然后折半加速

#include <bits/stdc++.h>using namespace std;struct K {int64_t k;int v;bool operator<(const K&lhs) const {if (k != lhs.k) return k < lhs.k;return v < lhs.v;}
};int main() {int n;cin >> n;vector<int> arr(n);for (int& x: arr) cin >> x;sort(arr.begin(), arr.end());int64_t sum = 0;vector<int> vals;do {int w = 0;for (auto &v: arr) w = w * 10 + v;vals.push_back(w);sum += (int64_t)w * w;} while(next_permutation(arr.begin(), arr.end()));if (sum % 2 == 1) {return 0;}// meet in middle 的枚舉技巧int cnt = vals.size() / 2;int mask = 1 << cnt;map<K, int> hp;for (int i = 0; i < mask; i++) {int64_t tsum = 0, z = 0;for (int j = 0; j < cnt; j++) {if ((i & (1 << j)) != 0) {tsum += (int64_t)vals[j+cnt] * vals[j + cnt];z ++;}}hp[K(tsum, z)] = i;}int ans1 = -1, ans2 = -1;for (int i = 0; i < mask; i++) {int64_t tsum = 0, z = 0;for (int j = 0; j < cnt; j++) {if ((i & (1 << j)) != 0) {tsum += (int64_t)vals[j] * vals[j];z ++;}}if (hp.find(K(sum/2 - tsum, cnt - z)) != hp.end()) {ans1 = i;ans2 = hp[K(sum/2 - tsum, cnt - z)];break;}}for (int i = 0; i < cnt; i++) {if ((ans1 & (1 << i)) != 0) {cout << vals[i] << '\n';}}for (int i = 0; i < cnt; i++) {if ((ans2 & (1 << i)) != 0) {cout << vals[i + cnt] << '\n';}}return 0;
}

---

RC-u4 City 不 City

分值: 30分

題型: 圖論

其實就是變形版的Dijkstra，權值為(最短路徑, 最小熱度)

這邊采用二分最小熱度 + 最短路徑驗證

#include <bits/stdc++.h>using namespace std;struct K {int cost, idx;bool operator<(const K &lhr) const {return cost > lhr.cost;}
};int main() {int n, m, s, e;cin >> n >> m >> s >> e;s--; e--;vector<int> arr(n);for (int &x: arr) cin >> x;vector<vector<array<int, 2>>> g(n);for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;u--; v--;g[u].push_back({v, w});g[v].push_back({u, w});}// 引入二分算了int inf = 0x3f3f3f3f;function<int(int)> solve = [&](int limit) {vector<int> dp(n, inf);dp[s] = 0;priority_queue<K, vector<K>> pq;pq.push(K(0, s));while (!pq.empty()) {K cur = pq.top(); pq.pop();if (dp[cur.idx] < cur.cost) continue;if (cur.idx != s && arr[cur.idx] > limit) continue;for (auto &e: g[cur.idx]) {if (dp[e[0]] > cur.cost + e[1]) {dp[e[0]] = cur.cost + e[1];pq.push(K(dp[e[0]], e[0]));}}}return dp[e];};int base = solve(inf);if (base == inf) {cout << "Impossible\n"; } else {int l = 0, r = inf;while (l <= r) {int mid = l + (r - l) / 2;int ret = solve(mid);if (ret == base) {r = mid - 1;} else {l = mid + 1;}}cout << base << " " << l << "\n";}return 0;
}

---

RC-u5 貪心消消樂

分值: 30分

思路: 前綴和+最大子數組和問題轉化

不過我覺得這題，

在消除格子后，上面的物體下滑規則沒有述說清晰

這時間復雜度，其實我把控不住了，每次貪心獲取最大子矩陣的和，已經優化到$O(n^3)$

剩下的就是操作的次數了，感覺還是數據弱了

#include <bits/stdc++.h>using namespace std;const int64_t inf = 0x3f3f3f3f;
int solve(vector<vector<int>> &g, vector<int> &choice) {int n = g.size();// n * nvector<vector<int64_t>> pre(n + 1, vector<int64_t>(n + 1, 0));for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j];if (g[i][j] == 0) pre[i + 1][j + 1] += -inf * 2;else pre[i + 1][j + 1] += g[i][j];}}int64_t ansW = 0;// O(n^3)for (int j = 0; j < n; j++) {for (int k = 0; k <= j; k++) {int64_t acc = 0;int up = 0;for (int i = 0; i < n; i++) {int64_t d = pre[i+1][j+1] - pre[i+1][k] - pre[i][j+1] + pre[i][k];acc += d;if (acc < 0) {acc = 0;up = i + 1;continue;}vector<int> tmp = {k+1, up + 1, j+1, i+1};if (acc > ansW) {ansW = acc;choice = {k+1, up + 1, j+1, i+1};} else if (acc == ansW && tmp < choice) {choice = {k+1, up+1, j+1, i+1};}}}}return ansW;
}void fall(vector<vector<int>> &g, vector<int> &choice) {int n = g.size();for (int i = choice[1] - 1; i <= choice[3] - 1; i++) {for (int j = choice[0] - 1; j <= choice[2] -1 ; j++) {g[i][j] = 0;}}  int h = choice[3] - choice[1] + 1;for (int i = choice[1] - 2; i >= 0; i--) {for (int j = choice[0] - 1; j <= choice[2] -1 ; j++) {g[i + h][j] = g[i][j];g[i][j] = 0;}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);int n;cin >> n;vector<vector<int>> g(n, vector<int>(n));for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {cin >> g[i][j];}}int64_t acc = 0;while (true) {vector<int> choice;int64_t ans = solve(g, choice);if (ans == 0) {break;}cout << "(" << choice[0] << ", " << choice[1] << ") (" << choice[2] << ", " << choice[3] << ") " << ans << '\n';acc += ans;fall(g, choice);}cout << acc << '\n';return 0;
}

---

寫在最后