Mảng cộng dồn 1 chiều
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 90 phút
- Học trước
- Mảng 1 chiều
- Chủ đề
- cộng dồnmảng
- Trạng thái
Kiến thức cơ bản
Vì sao cần mảng cộng dồn
Gấu Po ghi lại số hũ mật ong thu hoạch được trong từng ngày, tất cả n ngày. Thỏ liên tục chạy đến hỏi: "Từ ngày l đến ngày r, Gấu Po thu được tất cả bao nhiêu hũ?". Cách tự nhiên nhất là dùng vòng lặp for cộng từ a[l] đến a[r].
Mỗi câu hỏi tốn tối đa n phép cộng. Với q câu hỏi, ta tốn khoảng n × q phép cộng. Khi n = q = 105, đó là 1010 phép cộng, chậm hơn quy ước 108 phép tính khi lập trình thi đấu rất nhiều. Nhưng cả q câu hỏi đều hỏi trên cùng một dãy số, nên ta chỉ cần "chuẩn bị bài" một lần rồi trả lời mỗi câu hỏi thật nhanh.
Ẩn dụ: những cột mốc trên đường mòn
Gấu Po đi trên một con đường mòn chia thành n đoạn, đoạn i dài a[i] mét. Ở mỗi chỗ nối giữa hai đoạn có một cột mốc ghi sẵn "đã đi được bao nhiêu mét kể từ cổng rừng". Muốn biết từ đoạn l đến đoạn r dài bao nhiêu mét, Thỏ không cần đi lại từng bước, chỉ cần lấy số ghi ở cột mốc cuối đoạn r trừ đi số ghi ở cột mốc ngay trước đoạn l. Dãy các cột mốc đó chính là mảng cộng dồn.
Cột mốc : 0 1 2 3 4 5
|--a[1]-|--a[2]-|--a[3]-|--a[4]-|--a[5]-|
pre : pre[0] pre[1] pre[2] pre[3] pre[4] pre[5]
Đi từ cột mốc 1 đến cột mốc 4 (tức là qua các đoạn 2, 3, 4):
quãng đường = pre[4] - pre[1]
Mảng cộng dồn một chiều
Định nghĩa
Cho dãy a[1], a[2], ..., a[n]. Mảng cộng dồn pre có n + 1 phần tử, trong đó pre[i] là tổng của i số đầu tiên:
pre[0] = 0(chưa đi đoạn nào thì quãng đường là 0).pre[i] = pre[i-1] + a[i]với i từ 1 đến n (cột mốc mới bằng cột mốc trước cộng thêm đoạn vừa đi).
i : 0 1 2 3 4 5
a[i] : 3 1 4 1 5
pre[i] : 0 3 4 8 9 14
Công thức tính tổng đoạn
Tổng các số từ vị trí l đến vị trí r là pre[r] - pre[l-1]. Ví dụ tổng a[2] + a[3] + a[4] = pre[4] - pre[1] = 9 - 3 = 6 (đúng vì 1 + 4 + 1 = 6).
Vì sao trừ pre[l-1] mà không phải pre[l]? Vì pre[l] đã bao gồm cả a[l], mà ta cần giữ lại a[l]. Ta phải trừ phần "đã đi" trước khi bước vào đoạn l, đó là cột mốc l-1. Vì thế ta đánh số mảng từ 1 và đặt sẵn pre[0] = 0, để trường hợp l = 1 vẫn dùng được công thức (pre[r] - pre[0]).
Code mẫu
#include <iostream>
using namespace std;
const int MAXN = 100005;
long long pre[MAXN]; // mảng cộng dồn, dùng long long; mảng toàn cục nên pre[0] = 0
int main() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
pre[i] = pre[i - 1] + x; // cột mốc mới = cột mốc trước + đoạn vừa đi
}
for (int t = 0; t < q; t++) {
int l, r;
cin >> l >> r;
cout << pre[r] - pre[l - 1] << endl; // trả lời trong một phép trừ
}
return 0;
}
Độ phức tạp
- Tạo mảng cộng dồn: một vòng lặp, khoảng n phép tính.
- Mỗi câu hỏi: đúng một phép trừ, không cần vòng lặp.
- Tổng cộng khoảng n + q phép tính. Với n = q = 105, đó chỉ là khoảng 2 × 105 phép tính, máy tính chạy trong một cái chớp mắt. Cách cộng từng đoạn cần tới 1010 phép tính.
Cẩn thận tràn số: dùng long long
Giả sử có n = 105 ngày, mỗi ngày thu hoạch 109 hũ mật. Tổng sẽ là 1014. Kiểu int chỉ chứa được số đến khoảng 2,1 × 109, nên tổng này làm int bị tràn và cho kết quả sai (có khi ra số âm). Kiểu long long chứa được số đến khoảng 9 × 1018, thừa sức.
- Mảng cộng dồn
preluôn khai báo kiểulong long, kể cả khi từng số a[i] vẫn vừa trongint. - Biến chứa kết quả của mỗi câu hỏi cũng phải là
long long. Đừng viếtint ans = pre[r] - pre[l-1];. - Nếu cần tính tích hai số lớn thì ép kiểu trước khi nhân, ví dụ
1LL * x * y.
Quy tắc nhớ nhanh: thấy bài có "tổng" của nhiều số, mà số lượng hoặc giá trị lớn, thì dùng long long.
Cộng dồn để đếm
Mảng cộng dồn không chỉ để cộng các giá trị. Muốn đếm "có bao nhiêu số thỏa điều kiện nào đó trong đoạn [l, r]", ta tạo một mảng phụ b[i] chỉ gồm 0 và 1: b[i] = 1 nếu a[i] thỏa điều kiện, ngược lại b[i] = 0. Số phần tử thỏa điều kiện trong đoạn chính là tổng các số b[i], và ta cộng dồn mảng b như bình thường.
i : 1 2 3 4 5 6
a[i] : 2 7 4 4 9 10
b[i] : 1 0 1 1 0 1 (b[i] = 1 nếu a[i] chia hết cho 2)
pre[i] : 1 1 2 3 3 4 (pre[0] = 0)
Số phần tử chia hết cho 2 trong đoạn [2, 5] = pre[5] - pre[1] = 3 - 1 = 2
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
int b = (x % 2 == 0) ? 1 : 0; // 1 nếu x chẵn, 0 nếu x lẻ
pre[i] = pre[i - 1] + b; // cộng dồn mảng 0/1
}
Một số cách đặt mảng phụ thường gặp:
| Dạng bài | Mảng cần cộng dồn | Ví dụ |
|---|---|---|
| Tổng đoạn | a[i] | Tổng số hũ mật từ ngày l đến ngày r |
| Đếm số thỏa điều kiện | b[i] = 1 nếu a[i] thỏa, ngược lại 0 | Đếm số chẵn; đếm nguyên âm; đếm số nguyên tố (dùng sàng) |
| Đếm từng loại chữ cái | 26 mảng cộng dồn, mỗi chữ cái một mảng | Chữ "a" xuất hiện bao nhiêu lần trong s[l..r] |
| Tổng theo vị trí chẵn/lẻ | a[i] nếu i chẵn, ngược lại 0 | Tổng các phần tử ở vị trí chẵn trong đoạn |
Kết hợp với tìm kiếm nhị phân
Nếu mọi a[i] đều dương thì pre[1] < pre[2] < ... < pre[n], tức là mảng cộng dồn tăng dần. Khi đó ta có thể tìm kiếm nhị phân (tuần 12) trên pre. Ví dụ, tìm ngày nhỏ nhất r mà tổng a[1] + ... + a[r] đạt ít nhất S:
// pre[1..n] tăng dần (vì a[i] > 0)
int r = lower_bound(pre + 1, pre + n + 1, S) - pre;
// r là vị trí đầu tiên có pre[r] >= S; nếu r == n + 1 nghĩa là không có
Khi nào dùng mảng cộng dồn
| Cách làm | Dùng khi nào | Thời gian |
|---|---|---|
| Cộng bằng vòng lặp cho mỗi câu hỏi | Rất ít câu hỏi (q nhỏ), hoặc đoạn rất ngắn | Khoảng n × q phép tính |
| Mảng cộng dồn | Nhiều câu hỏi tổng/đếm trên đoạn, dãy số không bị sửa trong lúc hỏi | Khoảng n + q phép tính |
- Lưu ý: mảng cộng dồn được tính một lần từ dãy ban đầu. Nếu giữa chừng có số a[i] bị thay đổi thì mảng cộng dồn cũ không còn đúng nữa.
Mở rộng: cộng dồn hai chiều (không bắt buộc)
Cho bảng n hàng, m cột. Ta muốn tính nhanh tổng các ô trong một hình chữ nhật bất kỳ. Đặt P[i][j] là tổng của tất cả các ô nằm trong hình chữ nhật từ ô (1, 1) đến ô (i, j). Lấy "hình lớn", trừ đi phần thừa, và nhớ rằng góc trên trái bị trừ hai lần nên phải cộng lại một lần:
P[i][j] = a[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]
- Tổng hình chữ nhật từ ô (x1, y1) đến ô (x2, y2) là
P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]
cột y1-1 cột y1 ... y2
+-----------+--------------+
| A | B | A = P[x1-1][y1-1]
+-----------+--------------+ A + B = P[x1-1][y2]
| C | HÌNH CẦN | A + C = P[x2][y1-1]
| | TÍNH D | hình lớn = P[x2][y2]
+-----------+--------------+ => D = hình lớn - (A+B) - (A+C) + A
long long P[1005][1005]; // P[0][*] và P[*][0] bằng 0
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
int x;
cin >> x;
P[i][j] = x + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];
}
// tổng hình chữ nhật (x1, y1) - (x2, y2)
long long ans = P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1];
Luyện tập
Bài 1. Cột mốc đường mòn
Gấu Po đi dạo trên con đường mòn gồm n đoạn, đoạn thứ i dài a[i] mét. Cứ đi hết một đoạn, Gấu Po lại ghi lên cột mốc tổng quãng đường đã đi từ cổng rừng. Em hãy in ra số ghi trên từng cột mốc.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | n số cách nhau một dấu cách: số ghi trên cột mốc 1, 2, ..., n. | |
| Test | Input | Output |
| 1 | 5 3 1 4 1 5 | 3 4 8 9 14 |
| 2 | 3 1000000000 1000000000 1000000000 | 1000000000 2000000000 3000000000 |
Bài 2. Mật ong của Gấu Po
Gấu Po ghi lại số hũ mật ong thu hoạch được trong n ngày. Thỏ hỏi q câu, mỗi câu có dạng "Từ ngày l đến ngày r, Gấu Po thu được tất cả bao nhiêu hũ mật?". Hãy trả lời nhanh giúp Gấu Po.
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). q dòng tiếp theo: mỗi dòng hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là tổng a[l] + ... + a[r] của một câu hỏi. | |
| Test | Input | Output |
| 1 | 6 3 5 2 8 1 9 4 1 3 2 5 4 4 | 15 20 1 |
| 2 | 3 1 1000000000 1000000000 1000000000 1 3 | 3000000000 |
Bài 3. Cà rốt của Thỏ
Thỏ trồng cà rốt trong n ngày liên tiếp, ngày thứ i thu được a[i] củ. Gấu Po hay hỏi: "Từ ngày l đến ngày r, mỗi ngày Thỏ thu trung bình bao nhiêu củ?". Thỏ chỉ nói phần nguyên của số trung bình (làm tròn xuống).
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 109). q dòng tiếp theo: mỗi dòng hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là phần nguyên của trung bình cộng các số a[l], ..., a[r]. | |
| Test | Input | Output |
| 1 | 5 3 4 7 1 9 3 1 5 2 4 3 3 | 4 5 1 |
| 2 | 3 1 1000000000 1000000000 999999999 1 3 | 999999999 |
Bài 4. Những ngày chẵn
Hổ ghi lại số quả táo rụng xuống mỗi ngày trong n ngày. Hổ thích những ngày có số quả táo là số chẵn. Với mỗi câu hỏi (l, r), hãy cho Hổ biết trong các ngày từ l đến r có bao nhiêu ngày táo rụng số chẵn.
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). q dòng tiếp theo: mỗi dòng hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là số ngày có a[i] chẵn trong đoạn [l, r]. | |
| Test | Input | Output |
| 1 | 6 3 2 7 4 4 9 10 1 6 2 5 5 5 | 4 2 0 |
| 2 | 4 2 6 6 6 1 1 3 3 4 | 3 1 |
Bài 5. Số nguyên tố may mắn
Thỏ tin rằng số nguyên tố mang lại may mắn. Thỏ hỏi q lần, mỗi lần cho một khoảng [l, r] và muốn biết trong khoảng đó có bao nhiêu số nguyên tố. (Gợi ý: dùng sàng nguyên tố của tuần 5, rồi cộng dồn.)
| Đầu vào | Dòng 1: số nguyên q (1 ≤ q ≤ 105). q dòng tiếp theo: mỗi dòng hai số nguyên l, r (1 ≤ l ≤ r ≤ 106). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là số lượng số nguyên tố trong đoạn [l, r]. | |
| Test | Input | Output |
| 1 | 3 1 10 10 20 14 16 | 4 4 0 |
| 2 | 2 2 2 1 1 | 1 0 |
Bài 6. Tiếng gọi của khu rừng
Gấu Po viết lại tiếng hót của chim rừng thành một xâu s gồm các chữ cái thường. Thỏ muốn đếm xem trong đoạn từ vị trí l đến vị trí r của xâu có bao nhiêu nguyên âm (a, e, i, o, u). Thỏ hỏi q lần.
| Đầu vào | Dòng 1: xâu s gồm chữ cái thường, độ dài n (1 ≤ n ≤ 105). Dòng 2: số nguyên q (1 ≤ q ≤ 105). q dòng tiếp theo: mỗi dòng hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là số nguyên âm trong s[l..r] (vị trí tính từ 1). | |
| Test | Input | Output |
| 1 | gaupoandtho 3 1 11 1 3 4 6 | 5 2 2 |
| 2 | xinchaocacban 2 1 13 4 8 | 5 2 |
Bài 7. Điểm cân bằng
Hổ xếp n hòn đá thành một hàng, hòn thứ i nặng a[i] ký. Hổ muốn đặt một cái bập bênh ngay dưới một hòn đá sao cho tổng cân nặng các hòn đá bên trái bằng tổng cân nặng các hòn đá bên phải (hòn đá ở giữa không tính). Hãy tìm vị trí đặt bập bênh.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | In ra vị trí nhỏ nhất i thỏa mãn a[1] + ... + a[i-1] = a[i+1] + ... + a[n]. Nếu không có vị trí nào, in -1. (Phía bên trái hoặc bên phải rỗng thì tổng bằng 0.) | |
| Test | Input | Output |
| 1 | 5 2 3 6 1 4 | 3 |
| 2 | 3 1 2 3 | -1 |
Bài 8. Những ngày bội thu
Vườn của Gấu Po có n ngày thu hoạch, ngày i thu được a[i] quả. Thỏ muốn chọn đúng k ngày liên tiếp để đi hái quả sao cho tổng số quả thu được là lớn nhất. Hãy giúp Thỏ tìm tổng lớn nhất đó.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: tổng lớn nhất của k số liên tiếp. | |
| Test | Input | Output |
| 1 | 7 3 1 5 2 8 3 4 1 | 15 |
| 2 | 3 1 1000000000 1 1000000000 | 1000000000 |
Bài 9. Ăn đủ mật
Mỗi ngày Gấu Po ăn hết a[i] hũ mật ong, bắt đầu từ ngày 1 và ăn liên tục. Thỏ hỏi q lần, mỗi lần cho một số S: "Phải đến ngày thứ mấy thì tổng số hũ Gấu Po đã ăn lần đầu tiên đạt ít nhất S?". (Gợi ý: mảng cộng dồn tăng dần, hãy nhớ tìm kiếm nhị phân ở tuần 12.)
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). Dòng 3: q số nguyên S (1 ≤ S ≤ 1014). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là ngày nhỏ nhất r sao cho a[1] + ... + a[r] ≥ S. Nếu ăn hết n ngày vẫn chưa đủ, in -1. | |
| Test | Input | Output |
| 1 | 5 3 4 2 7 1 6 5 13 21 | 2 3 -1 |
| 2 | 3 2 1000000000 1000000000 1000000000 3000000000 3000000001 | 3 -1 |
Bài tập tự luyện
Bài 1. Bậc thang số chẵn
Cầu thang của Hổ có n bậc, bậc thứ i có a[i] viên đá quý. Hổ chỉ thích nhặt những bậc có số thứ tự chẵn (bậc 2, 4, 6, ...). Với mỗi câu hỏi (l, r), hãy tính tổng số đá quý Hổ nhặt được nếu chỉ đi từ bậc l đến bậc r.
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). q dòng tiếp theo: mỗi dòng hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là tổng các a[i] với i chẵn và l ≤ i ≤ r. | |
| Test | Input | Output |
| 1 | 6 3 5 2 8 1 9 4 1 6 2 3 3 5 | 7 2 1 |
| 2 | 2 2 1000000000 1000000000 1 1 1 2 | 0 1000000000 |
Bài 2. Đếm chữ cái trong đoạn
Gấu Po viết một lá thư dài gồm các chữ cái thường, được ghi thành xâu s. Thỏ hỏi q lần, mỗi lần cho đoạn [l, r] và một chữ cái c: "Trong đoạn này chữ c xuất hiện bao nhiêu lần?". (Gợi ý: mỗi chữ cái dùng một mảng cộng dồn riêng.)
| Đầu vào | Dòng 1: xâu s gồm chữ cái thường, độ dài n (1 ≤ n ≤ 105). Dòng 2: số nguyên q (1 ≤ q ≤ 105). q dòng tiếp theo: mỗi dòng gồm l, r (1 ≤ l ≤ r ≤ n) và chữ cái thường c, cách nhau một dấu cách. | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là số lần chữ c xuất hiện trong s[l..r]. | |
| Test | Input | Output |
| 1 | abracadabra 3 1 11 a 1 4 b 5 7 d | 5 1 1 |
| 2 | zzz 2 1 3 z 2 3 a | 3 0 |
Bài 3. Chuỗi ngày tăng trưởng
Thỏ theo dõi chiều cao của cây cà rốt trong n ngày, ngày thứ i cao a[i] cm. Một ngày i (i ≥ 2) được gọi là "ngày tăng" nếu a[i] > a[i-1]. Với mỗi câu hỏi (l, r), hãy đếm số ngày tăng i thỏa l < i ≤ r (so sánh từng cặp ngày liền nhau trong đoạn [l, r]).
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). q dòng tiếp theo: mỗi dòng hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là số ngày tăng trong đoạn [l, r]. Nếu l = r thì kết quả là 0. | |
| Test | Input | Output |
| 1 | 7 3 3 5 4 6 7 2 8 1 7 2 5 4 4 | 4 2 0 |
| 2 | 3 1 5 5 5 1 3 | 0 |
Bài 4. Chia đôi công bằng
Hổ và Gấu Po chia nhau một hàng gồm n hũ mật, hũ thứ i có a[i] điểm (điểm có thể âm vì có hũ bị hỏng). Hai bạn cắt hàng ở một chỗ: Hổ lấy các hũ bên trái, Gấu Po lấy các hũ bên phải (mỗi bên phải có ít nhất một hũ). Hỏi có bao nhiêu cách cắt để hai bên có tổng điểm bằng nhau?
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (-109 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: số vị trí cắt i (1 ≤ i < n) sao cho a[1] + ... + a[i] = a[i+1] + ... + a[n]. | |
| Test | Input | Output |
| 1 | 6 1 2 3 3 2 1 | 1 |
| 2 | 5 1 -1 0 1 -1 | 2 |
Bài 5. Vòng quanh hồ
Quanh hồ có n cây ăn quả xếp thành vòng tròn, cây i có a[i] quả (cây n nằm cạnh cây 1). Thỏ được chọn đúng k cây liền kề nhau trên vòng tròn để hái. Hỏi Thỏ hái được nhiều nhất bao nhiêu quả? (Gợi ý: viết dãy hai lần liên tiếp để biến vòng tròn thành đường thẳng.)
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: tổng lớn nhất của k cây liền kề trên vòng tròn. | |
| Test | Input | Output |
| 1 | 5 3 4 1 1 2 5 | 11 |
| 2 | 4 4 1000000000 1000000000 1000000000 1000000000 | 4000000000 |
Bài 6. Những ngày vàng
Gấu Po có n ngày bán mật, ngày i bán được a[i] hũ. Một khoảng k ngày liên tiếp được gọi là "tuần vàng" nếu tổng số hũ bán được trong khoảng đó ít nhất S. Hãy đếm xem có bao nhiêu tuần vàng.
| Đầu vào | Dòng 1: ba số nguyên n, k, S (1 ≤ k ≤ n ≤ 105; 1 ≤ S ≤ 1014). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: số khoảng k ngày liên tiếp có tổng không nhỏ hơn S. | |
| Test | Input | Output |
| 1 | 6 3 12 4 1 5 6 2 3 | 2 |
| 2 | 4 2 4000000000 3000000000 1000000000 1000000000 5 | 1 |
Bài 7. Khu vườn hình chữ nhật (không bắt buộc)
Khu vườn của Gấu Po là một bảng gồm n hàng, m cột; ô (i, j) có a[i][j] cây cà rốt. Thỏ hỏi q lần, mỗi lần cho một hình chữ nhật có góc trên trái là ô (x1, y1), góc dưới phải là ô (x2, y2). Hãy tính tổng số cây cà rốt trong hình chữ nhật đó. (Gợi ý: cộng dồn 2 chiều.)
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 1000). n dòng tiếp theo: mỗi dòng m số nguyên a[i][j] (0 ≤ a[i][j] ≤ 106). Dòng tiếp theo: số nguyên q (1 ≤ q ≤ 105). q dòng cuối: mỗi dòng bốn số nguyên x1, y1, x2, y2 (1 ≤ x1 ≤ x2 ≤ n; 1 ≤ y1 ≤ y2 ≤ m). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là tổng các ô trong hình chữ nhật của một câu hỏi. | |
| Test | Input | Output |
| 1 | 3 4 1 2 3 4 5 6 7 8 9 10 11 12 3 1 1 3 4 2 2 3 3 3 4 3 4 | 78 34 12 |
| 2 | 2 2 1000000 1000000 1000000 1000000 1 1 1 2 2 | 4000000 |
Bài 8. Hành trình ngắn nhất
Gấu Po cần thu thập ít nhất S hũ mật. Trên đường có n bụi hoa liên tiếp, bụi i cho a[i] hũ. Gấu Po phải đi qua một đoạn bụi hoa liên tiếp (lấy hết mật của mọi bụi trong đoạn) sao cho tổng đạt ít nhất S, và muốn đoạn đó càng ngắn càng tốt. Hãy cho biết số bụi hoa ít nhất phải đi qua.
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 105; 1 ≤ S ≤ 1014). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: độ dài ngắn nhất của đoạn liên tiếp có tổng ≥ S. Nếu không có đoạn nào, in -1. (Gợi ý: với mỗi vị trí bắt đầu l, tìm vị trí kết thúc nhỏ nhất bằng tìm kiếm nhị phân trên mảng cộng dồn.) | |
| Test | Input | Output |
| 1 | 6 11 2 3 1 2 4 3 | 5 |
| 2 | 3 100 10 20 30 | -1 |
Bài 9. Đoạn vàng lớn nhất (thử thách)
Hổ làm ăn thua lỗ lẫn lãi: ngày thứ i lãi a[i] đồng (số âm nghĩa là lỗ). Hổ muốn chọn một đoạn gồm ít nhất một ngày liên tiếp sao cho tổng lãi lớn nhất. Hãy giúp Hổ. (Gợi ý: tổng đoạn kết thúc ở r bằng pre[r] trừ đi một giá trị pre[j] nào đó với j < r; muốn tổng lớn nhất thì ta chọn pre[j] như thế nào?)
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (-109 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Một số nguyên: tổng lớn nhất của một đoạn con liên tiếp (không rỗng). | |
| Test | Input | Output |
| 1 | 8 -2 1 -3 4 -1 2 1 -5 | 6 |
| 2 | 3 -5 -2 -9 | -2 |
- Gợi ý chung: Có bốn lỗi rất hay gặp với mảng cộng dồn. (1) Viết nhầm pre[r] - pre[l] thay vì pre[r] - pre[l-1], làm mất số a[l]. (2) Quên dùng long long cho pre hoặc biến kết quả, dẫn đến tràn số khi tổng lớn. (3) Đánh số mảng từ 0 rồi dùng pre[l-1] với l = 1, hoặc khai báo mảng thiếu một phần tử (cần n + 1 phần tử vì có pre[0]). (4) Với bài đếm, quên biến dãy thành mảng 0/1 trước khi cộng dồn. Trước khi nộp bài, hãy thử tay với một dãy 3 hoặc 4 số để kiểm tra công thức.