前言
做的最轻松的一场，50分钟AK。
录屏在：https://www.bilibili.com/video/BV1KBfTB2E81
题目总览
题目细览
第1题 A-1 Maximum Product
思路
由于可能存在有负数，考虑预处理两个后缀数组suf1和suf2，分别表示后缀最大值和后缀最小值，然后枚举下标i，每次输出std::max(a[i] * suf1[i], a[i] * suf2[i])。
我的AC代码
#include <bits/stdc++.h>using i64 = long long;constexpr int inf = 1E9;void solve() {int n;std::cin >> n;std::vector<int> a(n + 1);for (int i = 1; i <= n; i++) {std::cin >> a[i];}std::vector<int> suf1(n + 2), suf2(n + 2);suf1[n + 1] = -inf, suf2[n + 1] = inf;for (int i = n; i >= 1; i--) {suf1[i] = std::max(suf1[i + 1], a[i]);suf2[i] = std::min(suf2[i + 1], a[i]);}for (int i = 1; i <= n; i++) {std::cout << (std::max(a[i] * suf1[i], a[i] * suf2[i])) << " \n"[i == n];}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T = 1;// std::cin >> T;for (int Ti = 0; Ti < T; Ti++) {solve();}return 0;
}
第2题 A-2 The Best Grouping Balance
思路
贪心考虑，将原数组升序排序后，每次拿当前数组的第一个和最后一个组队是最佳的，再将这些队伍的权值都丢进set中，最后set中最大值减去set中最小值就是答案。
我的AC代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}std::sort(a.begin(), a.end());std::set<int> set;for (int i = 0; i < n / 2; i++) {set.insert(a[i] + a[n - 1 - i]);}std::cout << (*set.rbegin() - *set.begin()) << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T = 1;// std::cin >> T;for (int Ti = 0; Ti < T; Ti++) {solve();}return 0;
}
第3题 A-3 The Farthest Distance in the World
思路
其实就是求树的直径，两次dfs即可。
我的AC代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<std::vector<int>> adj(n + 1);int rt = -1;for (int i = 1; i <= n; i++) {int par;std::cin >> par;if (par == -1) {rt = i;} else {adj[par].push_back(i);adj[i].push_back(par);}}std::vector<int> dep(n + 1);std::function<void(int, int)> dfs = [&](int u, int fa) {for (const auto& v : adj[u]) {if (v == fa) {continue;}dep[v] = dep[u] + 1;dfs(v, u);}};dfs(rt, -1);int max = *std::max_element(dep.begin() + 1, dep.end());int t = -1;for (int i = 1; i <= n; i++) {if (dep[i] == max) {t = i;break;}}dep[t] = 0;dfs(t, -1);max = *std::max_element(dep.begin() + 1, dep.end());std::cout << max << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T = 1;// std::cin >> T;for (int Ti = 0; Ti < T; Ti++) {solve();}return 0;
}
第4题 A-4 Both Expensive and Inexpensive Travel Plan
思路
题目的意思是相邻两个节点走权值最大的路径，从起点到终点则走总权值最小的路径，如果存在总权值最小相等的路径，走含interest更多的路径，输出路径或者输出"Sorry"。那么很自然地想到存邻接表的时候只存相邻节点权值最大的边(u, v, w)，用dijktra求最短路时多加一个判断，使得走含interest更多的路径，然后再开一个prev的哈希表（或者map）来记录转移过来的路径。
我的AC代码
#include <bits/stdc++.h>using i64 = long long;constexpr int inf = 1E9;void solve() {int n, m;std::cin >> n >> m;std::vector<int> a(n + 1);for (int i = 1; i <= n; i++) {std::cin >> a[i];}std::map<std::array<int, 2>, int> map;std::vector<std::vector<std::array<int, 2>>> adj(n + 1);for (int i = 0; i < m; i++) {int u, v, w;std::cin >> u >> v >> w;if (v > u) {std::swap(u, v);}map[ {u, v}] = std::max(map[ {u, v}], w);}for (const auto& [t, w] : map) {auto [u, v] = t;adj[u].push_back({v, w});adj[v].push_back({u, w});}int st = -1, ed = -1;std::cin >> st >> ed;std::map<int, int> prev;std::vector<int> dist(n + 1, inf);auto dijkstra = [&]() {std::vector<bool> vis(n + 1);using Node = std::array<int, 2>;std::priority_queue<Node, std::vector<Node>, std::greater<>> heap;heap.push({0, st});dist[st] = 0;while (heap.size()) {auto [distance, u] = heap.top();heap.pop();if (vis[u]) {continue;}vis[u] = true;for (const auto& [v, w] : adj[u]) {if (distance + w < dist[v]) {dist[v] = distance + w;heap.push({dist[v], v});prev[v] = u;} else if (distance + w == dist[v] && a[u]) {prev[v] = u;}}}};dijkstra();if (dist[ed] == inf) {std::cout << "Sorry\n";return;}std::cout << dist[ed] << "\n";std::vector<int> ans;ans.push_back(ed);while (ed != st) {ed = prev[ed];ans.push_back(ed);}std::reverse(ans.begin(), ans.end());for (int i = 0; i < ans.size(); i++) {std::cout << ans[i] << (i + 1 == ans.size() ? "\n" : "->");}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T = 1;// std::cin >> T;for (int Ti = 0; Ti < T; Ti++) {solve();}return 0;
}