Hướng dẫn giải của Lớn nhất (Đề chọn ĐTQG Phú Thọ 2014-2015)
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Cho dãy ~w_1, \dots, w_n~ và ~Q~ truy vấn ~(u, v)~, mỗi truy vấn hỏi giá trị lớn nhất của ~w_u, \dots, w_v~ (bài RMQ cơ bản).
Sub 1: Duyệt thẳng — ~O(n \cdot Q)~, dùng khi ~n \cdot Q \le 4 \cdot 10^6~
Với mỗi truy vấn, duyệt từ ~u~ đến ~v~ lấy max. Nếu chỉ nộp sub này: đúng 10/32 test.
Sub 2: Bảng thưa (sparse table) — xây ~O(n \log n)~, truy vấn ~O(1)~
Gọi ~sp[k][i]~ là max của đoạn dài ~2^k~ bắt đầu tại ~i~; ~sp[k][i] = \max(sp[k-1][i], sp[k-1][i + 2^{k-1}])~. Truy vấn ~[u, v]~ lấy ~k = \lfloor \log_2 (v-u+1) \rfloor~ rồi ~\max(sp[k][u], sp[k][v-2^k+1])~ (hai đoạn chồng nhau không ảnh hưởng max). Nếu chỉ nộp sub này: đúng 32/32 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; nếu ~n \cdot Q~ nhỏ thì 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.
#include <bits/stdc++.h>
using namespace std;
int n, q;
int w[50005];
int sp[17][50005];
// Sub 1: duyệt thẳng từ u đến v, O(n) mỗi truy vấn, dùng khi n * q <= 4 triệu
void sub1() {
while (q--) {
int u, v;
scanf("%d %d", &u, &v);
int mx = 0;
for (int i = u; i <= v; i++) mx = max(mx, w[i]);
printf("%d\n", mx);
}
}
// Sub 2: bảng thưa (sparse table) - xây O(n log n), mỗi truy vấn O(1)
void sub2() {
for (int i = 1; i <= n; i++) sp[0][i] = w[i];
for (int k = 1; (1 << k) <= n; k++)
for (int i = 1; i + (1 << k) - 1 <= n; i++)
sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << (k - 1))]);
while (q--) {
int u, v;
scanf("%d %d", &u, &v);
int k = 31 - __builtin_clz(v - u + 1);
printf("%d\n", max(sp[k][u], sp[k][v - (1 << k) + 1]));
}
}
int main() {
freopen("CAU6.INP", "r", stdin);
freopen("CAU6.OUT", "w", stdout);
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
if ((long long)n * q <= 4000000) sub1();
else sub2();
return 0;
}
Bình luận