Hướng dẫn giải của Bedao Grand Contest 16 - Kim cương
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Subtask 1: ~1 \leq x, y \leq 10^3~
Tạo mảng đánh dấu ~a~ kích thước ~10^3 \times 10^3~, ~a[i][j]~ là số lượng kim cương có tại tọa độ ~(i, j)~. Với mỗi tọa độ ~(i, j)~, giả sử đặt tâm điểm khai thác tại ~(i, j)~, ta duyệt qua tất cả ~12~ ô kề cận (theo miêu tả đề bài) để tính tổng số kim cương khai thác được tại vị trí đó.
~\Rightarrow~ Giá trị lớn nhất của mọi tổng chính là đáp án đề bài.
Subtask 2: Không có ràng buộc gì thêm
Tạo map<pair<int, int>, int> a, sử dụng ý tưởng tương tự subtask 1: a[x, y] chính là số viên kim cương có tại vị trí ~(x, y)~. Cách triển khai:
Duyệt qua tất cả ~N~ tọa độ chứa mỏ kim cương.
Với mỗi mỏ, ta duyệt qua tất cả vị trí "tâm điểm khai thác" sao cho từ tâm điểm đó, ta có thể khai được mỏ quặng hiện tại đang xét. Vị trí tương đối của các "tâm điểm khai thác" so với mỏ kim cương đang xét sẽ có dạng:
.
Với mỗi "tâm điểm khai thác" như thế, ta lại tiếp tục duyệt qua tất cả ~12~ ô mỏ mà từ "tâm điểm khai thác" có thể đi tới, lấy tổng của ~12~ ô đó. ~\Rightarrow~ Giá trị lớn nhất qua tất cả các tổng chính là đáp án đề bài.
Lưu ý: các thao tác lấy số lượng kim cương từ một ô ~(x, y)~, kiểm tra ô ~(x, y)~ có kim cương hay không,... đều sẽ thực hiện trên cấu trúc map.
#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define fi first #define se second const int N = 1e5; int n; map<pii, int> diamonds; pii d[] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -2}, {0, -1}, {0, 0}, {0, 1}, {0, 2}, {1, -1}, {1, 0}, {1, 1}, {2, 0}}; pii e[] = {{-2, 0}, {-1, -1}, {-1, 0}, {-1, 1}, {0, -2}, {0, -1}, {0, 0}, {0, 1}, {0, 2}, {1, -1}, {1, 0}, {1, 1}}; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i=1; i<=n; i++) { int x, y, w; cin >> x >> y >> w; diamonds[{x, y}] = w; } long long ans = 0; for (auto [p, w] : diamonds) { int x = p.fi, y = p.se; for (int i = 0; i < 12; i++) //tam diem khai thac { int u = x + e[i].fi, v = y + e[i].se; long long sum = 0; for (int j = 0; j < 12; j++) //vi tri khai thac { int p = u + d[j].fi, q = v + d[j].se; if (diamonds.find({p, q}) != diamonds.end()) sum += diamonds[{p, q}]; } ans = max(ans, sum); } } cout << ans; }
Bình luận
Lời giải có đoạn:
cho mình hỏi:
kiểm tra pair<p,q> có trong map diamonds ko. trong cấu trúc map có hàm count có tính chất tương tự nhg code ngắn hơn