[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Chào mọi người.
Trước tiên cho mình xin lỗi vì mình bận không đăng bài vào CN tuần trước được (và cũng do mình cảm giác chuyên mục của mình hơi bị flop ._.)
Problem 1 là một problem không khó, nhưng cũng chẳng dễ vì giới hạn "chết người" của nó.
Thì đầu tiên, cảm ơn bạn H.Bừn đã ủng hộ mình và trả lời problem nha.
Link câu trả lời: https://diendan.hocmai.vn/threads/cp-guide-101-ep-1-prologue-and-problem-1.834762/#post-4072476
Về solution của bạn thì cơ bản đã đúng, nhưng bạn quên nhập số lượng test case (Q) cho bài. Mình đã sửa lại và code bạn đã AC test của mình nhé.
Thì mình cũng đưa ra luôn solution cho các bạn.
Chúc các bạn học tốt, và hãy đón chờ problem 2 vào T7 này nha. ^^
Trước tiên cho mình xin lỗi vì mình bận không đăng bài vào CN tuần trước được (
Problem 1 là một problem không khó, nhưng cũng chẳng dễ vì giới hạn "chết người" của nó.
Thì đầu tiên, cảm ơn bạn H.Bừn đã ủng hộ mình và trả lời problem nha.
Link câu trả lời: https://diendan.hocmai.vn/threads/cp-guide-101-ep-1-prologue-and-problem-1.834762/#post-4072476
Về solution của bạn thì cơ bản đã đúng, nhưng bạn quên nhập số lượng test case (Q) cho bài. Mình đã sửa lại và code bạn đã AC test của mình nhé.
Thì mình cũng đưa ra luôn solution cho các bạn.
Yeah, như cách gọi, ta sẽ duyệt một vòng từ [TEX]l[/TEX] đến [TEX]r[/TEX], cộng lần lượt tất cả các phần tử từ [TEX]a_l[/TEX] đến [TEX]a_r[/TEX], và in ra kết quả.
Độ phức tạp: [TEX]O(N)[/TEX] cho mỗi query.
Mã:
cin >> l >> r;
int s = 0;
for (int i = l; i <= r; i++) s += a[i];
cout << s << '\n';Đây là method mà bạn H.Bừn đã sử dụng để giải problem này. Với những bài cần xử lý trong độ phức tạp [TEX]O(1)[/TEX] với mỗi case như bài này thì ta sẽ sử dụng một trong những thuật toán cơ bản được sử dụng trong CP, đó là tổng tích luỹ (hay còn gọi là tổng tiền tố - prefix sum).
Gọi [TEX]F_i[/TEX] là tổng các phần tử từ [TEX]A_1[/TEX] đến [TEX]A_i[/TEX].
Ta thấy:
[TEX] F_1 = A_1 \\ F_2 = A_1 + A_2 = F_1 + A_2 \\ F_3 = A_1 + A_2 + A_3 = F_2 + A_3\\ ... \\ F_n = A_1 + A_2 + ... + A_n = F_{n - 1} + A_n [/TEX]
Do đó, ta có thể xây dựng mảng tiền tố (prefix array) cho phần tử thứ [TEX]i[/TEX] bằng cách cộng phần tử mảng tiền tố thứ [TEX]i - 1[/TEX] cho phần tử [TEX]a_i[/TEX]:
Ngoài ra, với một số bài không cần sử dụng lại đến mảng A, ta cũng có thể tận dụng ngay mảng A làm mảng tiền tố:
Khi đó, ta có thể dễ dàng tính tổng các phần tử từ [TEX]l[/TEX] đến [TEX]r[/TEX] bằng cách tính hiệu [TEX]F_r - F_{l - 1}[/TEX]:
Độ phức tạp:
Gọi [TEX]F_i[/TEX] là tổng các phần tử từ [TEX]A_1[/TEX] đến [TEX]A_i[/TEX].
Ta thấy:
[TEX] F_1 = A_1 \\ F_2 = A_1 + A_2 = F_1 + A_2 \\ F_3 = A_1 + A_2 + A_3 = F_2 + A_3\\ ... \\ F_n = A_1 + A_2 + ... + A_n = F_{n - 1} + A_n [/TEX]
Do đó, ta có thể xây dựng mảng tiền tố (prefix array) cho phần tử thứ [TEX]i[/TEX] bằng cách cộng phần tử mảng tiền tố thứ [TEX]i - 1[/TEX] cho phần tử [TEX]a_i[/TEX]:
Mã:
int f[maxx];
f[1] = a[1];
for (int i = 2; i <= n; i++) f[i] = f[i - 1] + a[i];Ngoài ra, với một số bài không cần sử dụng lại đến mảng A, ta cũng có thể tận dụng ngay mảng A làm mảng tiền tố:
Mã:
for (int i = 2; i <= n; i++) a[i] += a[i - 1];Khi đó, ta có thể dễ dàng tính tổng các phần tử từ [TEX]l[/TEX] đến [TEX]r[/TEX] bằng cách tính hiệu [TEX]F_r - F_{l - 1}[/TEX]:
Mã:
cin >> l >> r;
cout << f[r] - f[l - 1];Độ phức tạp:
- Setup: [TEX]O(N)[/TEX]
- Mỗi query: [TEX]O(1)[/TEX]
Chúc các bạn học tốt, và hãy đón chờ problem 2 vào T7 này nha. ^^
