Hướng dẫn giải của Số lớn nhất (Minh họa TS chuyên PT 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
Tính tổng giá trị lớn nhất của mọi đoạn con ~[i, j]~ của dãy. Kết quả có thể lớn (đến khoảng ~5 \cdot 10^{17}~) nên dùng long long.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Với mỗi đầu trái ~l~, tăng dần ~r~ và duy trì giá trị lớn nhất đang có, cộng vào tổng. Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 2: Ngăn xếp đơn điệu — ~O(n)~
Mỗi phần tử ~a_i~ là giá trị lớn nhất của đúng ~(i - L_i) \cdot (R_i - i)~ đoạn, trong đó ~L_i~ là vị trí gần nhất bên trái có giá trị lớn hơn ~a_i~, ~R_i~ là vị trí gần nhất bên phải có giá trị lớn hơn hoặc bằng ~a_i~ (lệch một bên để các phần tử bằng nhau không bị đếm trùng). Tính ~L, R~ bằng ngăn xếp, đáp án là ~\sum a_i (i-L_i)(R_i-i)~. Nộp riêng sub này đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm ~main~ đọc dữ liệu; nếu ~n \le 1000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước. Chương trình đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[1000005];
int L[1000005], R[1000005];
// Sub 1: vét cạn O(n^2) — với mỗi l, mở rộng r và giữ max đang có, dùng khi n <= 1000
void sub1() {
long long sum = 0;
for (int l = 1; l <= n; l++) {
long long mx = 0;
for (int r = l; r <= n; r++) {
mx = max(mx, a[r]);
sum += mx;
}
}
cout << sum << "\n";
}
// Sub 2: ngăn xếp đơn điệu — a[i] là max của (i-L[i]) * (R[i]-i) đoạn, O(n)
void sub2() {
vector<int> st;
for (int i = 1; i <= n; i++) { // L[i]: vị trí gần nhất bên trái có a > a[i]
while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
L[i] = st.empty() ? 0 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n; i >= 1; i--) { // R[i]: vị trí gần nhất bên phải có a >= a[i]
while (!st.empty() && a[st.back()] < a[i]) st.pop_back();
R[i] = st.empty() ? n + 1 : st.back();
st.push_back(i);
}
long long sum = 0;
for (int i = 1; i <= n; i++) sum += a[i] * (long long)(i - L[i]) * (R[i] - i);
cout << sum << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận