Hướng dẫn giải của Số lớn nhất (đề KS2 ĐH 2024)
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.
Hướng dẫn giải
Cần tổng của $\max(al, \dots, ar)$ trên mọi đoạn $l \le r$. Đếm xem mỗi $ai$ là giá trị lớn nhất của bao nhiêu đoạn, rồi cộng $ai$ nhân số đoạn đó. Để mỗi đoạn chỉ được tính một lần, khi hai phần tử cùng giá trị lớn nhất thì chỉ lấy phần tử xuất hiện đầu tiên.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Với mỗi $l$, duyệt $r$ tăng dần, giữ giá trị lớn nhất hiện tại và cộng dồn vào đáp số.
Nếu chỉ nộp sub này: đúng 8/20 test (12 test lớn quá giờ).
Sub 2: Ngăn xếp đơn điệu — ~O(n)~
Với mỗi $i$, tìm $pli$ là chỉ số $j < i$ gần nhất có $aj \ge ai$ và $nri$ là chỉ số $j > i$ gần nhất có $aj > ai$ (bằng ngăn xếp). Số đoạn mà $ai$ là max đúng một lần là $(i - pli)(nri - i)$. Đáp số là $\sum ai (i - pli)(nri - i)$.
Bẫy: đáp số có thể lên tới khoảng $5 \cdot 10^{17}$ nên dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu, nếu $n \le 1000$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Sub 1: vet can O(n^2), dung khi n <= 1000.
// Voi moi l, duyet r tang dan, giu max(a_l..a_r) roi cong vao tong.
void sub1() {
long long total = 0;
for (int l = 0; l < n; l++) {
long long mx = 0;
for (int r = l; r < n; r++) {
mx = max(mx, a[r]);
total += mx;
}
}
cout << total << "\n";
}
// Sub 2: O(n) bang ngan xep don dieu. Voi moi i, dem so doan ma a_i la phan tu lon nhat:
// trai den pl[i] (phan tu >= a_i gan nhat ben trai), phai den nr[i] (phan tu > a_i gan nhat ben phai).
// Moi doan duoc tinh dung mot lan (tinh cho phan tu lon nhat dau tien trong doan).
void sub2() {
vector<int> pl(n), nr(n);
stack<int> st;
for (int i = 0; i < n; i++) { // pl[i]: chi so j < i gan nhat, a_j >= a_i
while (!st.empty() && a[st.top()] < a[i]) st.pop();
pl[i] = st.empty() ? -1 : st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n - 1; i >= 0; i--) { // nr[i]: chi so j > i gan nhat, a_j > a_i
while (!st.empty() && a[st.top()] <= a[i]) st.pop();
nr[i] = st.empty() ? n : st.top();
st.push(i);
}
long long total = 0;
for (int i = 0; i < n; i++) {
long long cnt = (long long)(i - pl[i]) * (nr[i] - i);
total += a[i] * cnt;
}
cout << total << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (auto &x : a) cin >> x;
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận