Ôn tổng hợp GĐ2
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 90 phút
- Học trước
- Sắp xếp cơ bản, Sort, pair và comparator, Tìm kiếm nhị phân, Mảng cộng dồn 1 chiều, Mảng hiệu, Hai con trỏ, Cửa sổ trượt
- Chủ đề
- ôn tập
- Trạng thái
Kiến thức cơ bản
Bản đồ kiến thức giai đoạn 2
Trong bảy tuần qua (tuần 10 đến tuần 16), em đã học thêm bảy công cụ để chương trình chạy nhanh hơn. Tuần này em không học thêm gì mới, mà tập nhận ra mỗi bài thuộc dạng nào và chọn đúng công cụ. Bảng dưới đây gom tất cả lại.
| Công cụ | Hình ảnh dễ nhớ | Dùng khi | Chi phí |
|---|---|---|---|
| sort (tuần 10) | Xếp hàng theo chiều cao | Cần dãy có thứ tự, hoặc muốn các số giống nhau đứng cạnh nhau | n log n |
| pair và comparator (tuần 11) | Thẻ học sinh ghi nhiều thông tin, luật xếp hạng do em đặt | Sắp xếp theo nhiều tiêu chí, nhớ vị trí ban đầu | n log n |
| Tìm kiếm nhị phân, lower_bound, upper_bound (tuần 12) | Mở sách ở giữa rồi bỏ nửa không cần | Hỏi “có không”, đếm số lần xuất hiện, đếm số phần tử ≤ x trong dãy đã sắp | log n mỗi câu hỏi |
| Cộng dồn (tuần 13) | Cột mốc ki-lô-mét trên đường | Tổng của nhiều đoạn, nhiều câu hỏi | n lúc chuẩn bị, 1 mỗi câu hỏi |
| Mảng hiệu (tuần 14) | Cọ sơn: đặt cọ ở đầu đoạn, nhấc cọ ở cuối đoạn | Nhiều lần cộng hoặc tô cả một đoạn | 1 mỗi lần tô, n lúc khôi phục |
| Hai con trỏ (tuần 15) | Hai bạn đi vào từ hai đầu cầu, hoặc hai bạn đi cùng chiều | Cặp số trên dãy đã sắp; đoạn liên tiếp với số dương | n |
| Cửa sổ trượt (tuần 16) | Khung kính trượt trên dãy số | Đoạn dài đúng k, hoặc đoạn co giãn theo điều kiện | n |
Khuôn viết nhanh
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Luật xếp hạng: điểm giảm dần, bằng điểm thì số hiệu tăng dần
bool cmp(pair<int, int> x, pair<int, int> y) {
if (x.first != y.first) return x.first > y.first;
return x.second < y.second;
}
int main() {
vector<int> a = {5, 2, 5, 7};
sort(a.begin(), a.end()); // sắp tăng dần
int x = 5;
// Số lần xuất hiện của x trong dãy đã sắp
int dem = upper_bound(a.begin(), a.end(), x)
- lower_bound(a.begin(), a.end(), x);
// Cộng dồn: p[0] = 0, tổng đoạn [l, r] là p[r] - p[l - 1]
p[i] = p[i - 1] + a[i];
long long tong = p[r] - p[l - 1];
// Mảng hiệu: tô đoạn [l, r], cuối cùng cộng dồn lại
d[l]++;
d[r + 1]--;
cur += d[i];
// Hai con trỏ l, r đi từ hai đầu (dãy đã sắp)
while (l < r) {
if (a[l] + a[r] <= K) { dem += r - l; l++; } // r - l cặp thỏa
else r--;
}
// Cửa sổ trượt độ dài k: thêm số mới, bớt số cũ
cur += a[i] - a[i - k];
// Cửa sổ co giãn (số dương): l là đầu trái, r là đầu phải
for (int r = 0; r < n; r++) {
sum += a[r];
while (sum > S) { sum -= a[l]; l++; }
}
return 0;
}
Nhận dạng dạng bài
Đọc đề xong, em đừng vội viết code. Hãy tìm “từ khóa” trong đề rồi đối chiếu với bảng sau.
| Dấu hiệu trong đề | Hãy nghĩ đến |
|---|---|
| “xếp hạng”, “theo thứ tự”, “bằng nhau thì xét tiếp…” | sort cùng pair và comparator |
| Nhiều câu hỏi “có bao nhiêu số bằng x”, “bao nhiêu số ≤ x” | sort một lần, rồi lower_bound hoặc upper_bound cho từng câu hỏi |
| Nhiều câu hỏi “tổng các số từ vị trí l đến r” | Cộng dồn |
| Nhiều lần “tăng, tô, bật cả đoạn [l, r]”, cuối cùng mới hỏi kết quả | Mảng hiệu |
| “Cặp số có tổng (hoặc hiệu) …” trên dãy sắp được | Hai con trỏ từ hai đầu, hoặc nhị phân |
| “Đoạn liên tiếp dài nhất (hoặc đếm đoạn)” với số dương và điều kiện về tổng | Hai con trỏ cùng chiều (cửa sổ co giãn) |
| “k ngày liên tiếp”, độ dài đoạn cho trước | Cửa sổ trượt cố định |
| “Gộp các đoạn chồng nhau”, “độ dài phần phủ” | Sắp theo đầu đoạn rồi quét một lượt |
| “Lớn nhất sao cho vẫn đủ…” (không bắt buộc) | Nhị phân theo đáp án |
Nhìn giới hạn để chọn cách giải
Máy tính làm được khoảng 108 phép tính trong một giây. Em đếm số phép tính của cách mình định làm rồi so với con số đó.
| Giới hạn | Cách làm có thể | Ví dụ |
|---|---|---|
| n ≤ 1000 | Hai vòng for lồng nhau (n²) vẫn kịp | Đếm cặp, thử mọi đoạn |
| n, q ≤ 105 | Cách “n × q” mất 1010 phép tính, quá chậm. Phải chuẩn bị một lần (sort, cộng dồn, mảng hiệu) rồi trả lời mỗi câu hỏi trong 1 hoặc log n bước | Tổng đoạn, đếm số lần xuất hiện |
| n ≤ 105, một câu hỏi | n log n (sort) hoặc n (hai con trỏ, cửa sổ trượt) | Đoạn dài nhất, đếm cặp |
| n lên tới 106 | Chỉ nên dùng cách n, hoặc n log n gọn nhẹ | Cửa sổ trượt, cộng dồn |
Tám lỗi hay gặp
- Cộng dồn: quên p[0] = 0 hoặc khai báo mảng thiếu chỗ. Tổng đoạn từ l đến r là p[r] - p[l-1], không phải p[r] - p[l].
- Mảng hiệu: có d[r+1]-- nên mảng d phải dài ít nhất n + 2.
- lower_bound và upper_bound chỉ đúng khi dãy đã được sắp xếp. Số lần xuất hiện là hiệu của hai vị trí, và nhớ trừ cho begin() nếu cần vị trí.
- Tổng, tích hoặc số cặp có thể vượt 2 tỷ (ví dụ n = 105 thì số cặp gần 5 tỷ). Dùng long long.
- Comparator phải dùng dấu < hoặc >, không dùng ≤ hoặc ≥ (có thể làm chương trình sập).
- Cửa sổ co giãn (dịch con trỏ trái khi tổng quá lớn) chỉ đúng khi mọi số đều dương. Nếu có số âm thì không dùng được.
- Cửa sổ trượt: tính cửa sổ đầu tiên một lần, sau đó mỗi bước chỉ thêm số mới và bớt số cũ. Tính lại từ đầu mỗi lần sẽ mất n × k phép tính.
- sort làm mất vị trí ban đầu. Nếu đề hỏi “bạn thứ mấy” thì phải lưu cặp (giá trị, vị trí) trước khi sắp.
Cách luyện tập tuần này
Với mỗi bài, em đừng viết code ngay. Hãy tự hỏi: (1) Bài thuộc dạng nào trong bảng nhận dạng? (2) n, q lớn nhất là bao nhiêu thì cách mình định làm có kịp không? (3) Có chỗ nào cần long long, có chỗ nào cần sắp xếp trước? Trả lời được ba câu này rồi mới mở máy.
Luyện tập
Bài 1. Trò chơi nhận dạng dạng bài
Chưa cần viết code. Với mỗi đề bên dưới, em điền dạng bài (công cụ) và số phép tính ước lượng. Đáp án ở cuối tài liệu, em chỉ xem sau khi đã tự điền xong.
| Đề | Dạng bài | Độ phức tạp |
|---|---|---|
| 1. Thỏ có 105 ngày thu hoạch cà rốt và 105 câu hỏi “từ ngày l đến ngày r thu được bao nhiêu củ?”. | ||
| 2. Hổ sơn hàng rào m lần, mỗi lần sơn thêm một lớp từ cọc l đến cọc r. Cuối cùng hỏi mỗi cọc có mấy lớp sơn. | ||
| 3. Gấu Po xếp hạng n bạn theo điểm giảm dần, bằng điểm thì xếp theo tên. | ||
| 4. Bảng giá đã xếp tăng dần. Có 105 khách, mỗi khách hỏi có bao nhiêu món giá không quá x. | ||
| 5. Cho n số dương, tìm đoạn liên tiếp dài nhất có tổng không quá S. | ||
| 6. Cho doanh thu của n ngày, tìm tổng lớn nhất của 7 ngày liên tiếp. | ||
| 7. Đếm số cặp (i, j) với i < j mà a[i] + a[j] ≤ K, n = 105. | ||
| 8. Thỏ sơn n đoạn hàng rào chồng lên nhau. Hỏi tổng chiều dài đã được sơn. |
Bài 2. Cuộc đua của rừng xanh
Thỏ ghi lại điểm của n vận động viên trong cuộc đua, vận động viên thứ i có số hiệu i. Điểm cao hơn thì xếp trên; nếu bằng điểm thì số hiệu nhỏ hơn xếp trên. Hãy in số hiệu của các vận động viên theo thứ tự xếp hạng.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên, số thứ i là điểm của vận động viên i (0 ≤ điểm ≤ 109). | |
|---|---|---|
| Đầu ra | n số hiệu theo thứ tự xếp hạng, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 70 90 70 85 90 | 2 5 4 1 3 |
| 2 | 3 10 10 10 | 1 2 3 |
Bài 3. Đếm thẻ cùng mã
Hổ có n thẻ bài, mỗi thẻ ghi một số nguyên. Hổ hỏi q câu, mỗi câu cho một số x và hỏi có bao nhiêu thẻ ghi đúng số x.
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên (giá trị tuyệt đối không quá 109). q dòng tiếp theo, mỗi dòng một số nguyên x. | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là câu trả lời cho một câu hỏi. | |
| Test | Input | Output |
| 1 | 6 3 5 2 5 7 5 2 5 2 9 | 3 2 0 |
| 2 | 4 2 1 1 1 1 1 3 | 4 0 |
Bài 4. Quãng đường chạy bộ
Gấu Po chạy bộ n ngày, ngày thứ i chạy được a[i] mét. Thỏ hỏi q câu, mỗi câu cho hai ngày l và r, hỏi tổng quãng đường Gấu Po chạy từ ngày l đến ngày 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] (0 ≤ a[i] ≤ 109). q dòng tiếp theo, mỗi dòng hai số l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là tổng quãng đường (mét) của một câu hỏi. | |
| Test | Input | Output |
| 1 | 5 3 4 2 7 1 6 1 5 2 3 5 5 | 20 9 6 |
| 2 | 3 2 1000000000 1000000000 1000000000 1 3 2 3 | 3000000000 2000000000 |
Bài 5. Sơn hàng rào
Hàng rào của Hổ có n cọc, đánh số từ 1 đến n, ban đầu chưa sơn. Hổ sơn m lần, mỗi lần sơn thêm một lớp cho các cọc từ l đến r. Hãy cho biết mỗi cọc có bao nhiêu lớp sơn.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105). m dòng tiếp theo, mỗi dòng hai số l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | n số cách nhau một dấu cách, số thứ i là số lớp sơn của cọc i. | |
| Test | Input | Output |
| 1 | 6 3 1 3 2 5 3 3 | 1 2 3 1 1 0 |
| 2 | 4 1 1 4 | 1 1 1 1 |
Bài 6. Hai củ cà rốt vừa giỏ
Thỏ có n củ cà rốt, củ thứ i nặng a[i]. Mỗi giỏ của Thỏ đựng đúng hai củ và chịu được tổng khối lượng không quá K. Hỏi Thỏ có bao nhiêu cách chọn hai củ (không tính thứ tự) bỏ vào một giỏ?
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 105; 1 ≤ K ≤ 2 × 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cách chọn (có thể rất lớn, hãy cẩn thận với kiểu dữ liệu). | |
| Test | Input | Output |
| 1 | 5 7 1 5 3 4 2 | 8 |
| 2 | 4 3 5 6 7 8 | 0 |
Bài 7. Chuỗi ngày hái quả dài nhất
Gấu Po hái quả liên tục trong những ngày liên tiếp. Ngày thứ i hái được a[i] quả (a[i] > 0). Gấu Po muốn hái nhiều ngày nhất có thể nhưng tổng số quả không được vượt quá S. Hãy tìm số ngày liên tiếp nhiều nhất.
| Đầ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 | Số ngày liên tiếp nhiều nhất (in 0 nếu không có đoạn nào thỏa mãn). | |
| Test | Input | Output |
| 1 | 7 10 2 3 1 4 2 5 1 | 4 |
| 2 | 3 1 5 6 7 | 0 |
Bài 8. Ngày đạt chỉ tiêu
Hổ tiết kiệm mỗi ngày a[i] đồng (a[i] > 0). Với mỗi mục tiêu X, Hổ muốn biết đến cuối ngày nào thì tổng tiền tiết kiệm lần đầu tiên đạt ít nhất X đồ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] (1 ≤ a[i] ≤ 109). q dòng tiếp theo, mỗi dòng một số nguyên X (1 ≤ X ≤ 1014). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là ngày sớm nhất đạt mục tiêu, hoặc -1 nếu sau n ngày vẫn chưa đạt. | |
| Test | Input | Output |
| 1 | 5 4 3 2 5 1 4 3 6 15 16 | 1 3 5 -1 |
| 2 | 3 2 10 10 10 1 30 | 1 3 |
Bài 9. Hàng rào chồng nhau
Thỏ sơn n đoạn hàng rào, đoạn thứ i bắt đầu ở vị trí l và kết thúc ở vị trí r (độ dài r - l). Các đoạn có thể chồng lên nhau. Hãy tính tổng chiều dài phần hàng rào đã được sơn, mỗi chỗ chỉ tính một lần.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo, mỗi dòng hai số l, r (0 ≤ l < r ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng chiều dài phần được sơn. | |
| Test | Input | Output |
| 1 | 3 1 5 4 9 12 14 | 10 |
| 2 | 3 1 10 2 3 5 6 | 9 |
Bài 10. Dải ruy băng may mắn
Gấu Po có một dải ruy băng gồm n ô, ô thứ i ghi số dương a[i]. Gấu Po muốn cắt ra một đoạn gồm các ô liên tiếp có tổng đúng bằng S. Hỏi có bao nhiêu đoạn như vậy?
| Đầ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 | Số đoạn có tổng đúng bằng S. | |
| Test | Input | Output |
| 1 | 6 5 2 3 2 1 4 1 | 4 |
| 2 | 4 3 1 1 1 1 | 2 |
Bài tập tự luyện
Bài 1. Bảng giá siêu thị
Siêu thị của rừng xanh có n món hàng, giá đã được xếp tăng dần. Có q khách, mỗi khách có x đồng và hỏi mình mua được bao nhiêu món (giá món đó không quá x).
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên giá tăng dần (0 ≤ giá ≤ 109). q dòng tiếp theo, mỗi dòng một số nguyên x (0 ≤ x ≤ 109). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là số món mà khách mua được. | |
| Test | Input | Output |
| 1 | 5 3 10 20 20 35 50 20 5 100 | 3 0 5 |
| 2 | 3 1 7 8 9 8 | 2 |
Bài 2. Bảng vàng thành tích
Thỏ có danh sách n bạn, mỗi bạn có một tên và một điểm. Hãy in tên các bạn theo thứ tự: điểm cao hơn xếp trước; nếu bằng điểm thì tên xếp trước theo thứ tự bảng chữ cái.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo, mỗi dòng gồm tên (chữ cái thường, dài không quá 10 ký tự) và điểm (số nguyên từ 0 đến 1000). | |
|---|---|---|
| Đầu ra | n dòng, mỗi dòng một tên theo thứ tự xếp hạng. | |
| Test | Input | Output |
| 1 | 4 thor 80 gau 95 ho 80 binh 95 | binh gau ho thor |
| 2 | 3 an 5 an 5 be 7 | be an an |
Bài 3. Hàng cây xen kẽ
Hổ trồng n cây thành một hàng, cây thứ i cao a[i]. Với mỗi câu hỏi l, r, Hổ muốn biết trong các cây từ l đến r, tổng chiều cao các cây ở vị trí lẻ và tổng chiều cao các cây ở vị trí chẵn (vị trí tính theo cả hàng, bắt đầu từ 1).
| Đầ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ố l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng hai số: tổng ở vị trí lẻ và tổng ở vị trí chẵn, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 2 3 1 4 1 5 1 5 2 4 | 12 2 4 2 |
| 2 | 1 1 9 1 1 | 9 0 |
Bài 4. Tuần buôn bán tốt nhất
Cửa hàng của Gấu Po có lãi hoặc lỗ mỗi ngày (số âm là lỗ). Gấu Po muốn chọn k ngày liên tiếp có tổng lãi lớn nhất. Hãy tìm tổng lãi đó.
| Đầ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] (|a[i]| ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng lớn nhất của k ngày liên tiếp. | |
| Test | Input | Output |
| 1 | 6 3 2 -1 3 -5 4 1 | 4 |
| 2 | 4 2 -3 -1 -4 -2 | -4 |
Bài 5. Dãy đèn lễ hội
Rừng xanh có n bóng đèn xếp thành hàng, ban đầu đều tắt. Hổ bấm công tắc m lần, mỗi lần đổi trạng thái (tắt thành sáng, sáng thành tắt) của các bóng từ l đến r. Hỏi cuối cùng có bao nhiêu bóng đang sáng?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105). m dòng tiếp theo, mỗi dòng hai số l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | Số bóng đèn đang sáng. | |
| Test | Input | Output |
| 1 | 5 3 1 3 2 4 3 5 | 3 |
| 2 | 4 2 1 4 1 4 | 0 |
Bài 6. Cặp số hơn kém nhau K
Thỏ có n tấm thẻ, thẻ thứ i ghi số a[i]. Hãy đếm số cặp thẻ (x, y) mà số trên thẻ y lớn hơn số trên thẻ x đúng K đơn vị. Hai thẻ ghi cùng số vẫn là hai thẻ khác nhau.
| Đầu vào | Dòng 1: hai số nguyên n, K (1 ≤ n ≤ 105; 1 ≤ K ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cặp tìm được. | |
| Test | Input | Output |
| 1 | 5 2 1 3 5 3 5 | 6 |
| 2 | 4 1 2 2 3 3 | 4 |
Bài 7. Đoạn không quá S
Gấu Po có n số dương. Hãy đếm số đoạn liên tiếp (gồm ít nhất một số) có tổng không vượt quá S.
| Đầ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 | Số đoạn thỏa mãn. | |
| Test | Input | Output |
| 1 | 5 6 2 1 3 1 2 | 12 |
| 2 | 3 1 2 3 4 | 0 |
Bài 8. Dải cờ hai màu
Hổ treo một dải cờ, mỗi lá cờ ứng với một chữ cái thường. Hổ muốn cắt một đoạn liên tiếp dài nhất mà chỉ có nhiều nhất hai loại chữ cái khác nhau. Hãy cho biết độ dài lớn nhất.
| Đầu vào | Một dòng duy nhất là xâu s gồm chữ cái thường, dài từ 1 đến 105 ký tự. | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của đoạn thỏa mãn. | |
| Test | Input | Output |
| 1 | abcbbbcaa | 6 |
| 2 | aaaa | 4 |
Bài 9. Thử thách (không bắt buộc): Cắt dây thừng
Gấu Po có n sợi dây thừng, sợi thứ i dài a[i]. Gấu Po cần cắt được ít nhất k đoạn dây có độ dài bằng nhau và là số nguyên dương (mỗi sợi có thể cắt thành nhiều đoạn, phần dư bỏ đi). Hãy tìm độ dài lớn nhất của mỗi đoạn. (Gợi ý: nếu cắt được với độ dài L thì cũng cắt được với mọi độ dài nhỏ hơn L. Hãy nghĩ đến tìm kiếm nhị phân trên chính đáp án.)
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 105; 1 ≤ k ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của mỗi đoạn, hoặc 0 nếu không thể cắt được k đoạn. | |
| Test | Input | Output |
| 1 | 3 5 9 7 11 | 4 |
| 2 | 2 100 10 20 | 0 |
-
Gợi ý chung: Trước khi viết code, hãy ghi ra ba điều: dạng bài (sort, nhị phân, cộng dồn, mảng hiệu, hai con trỏ hay cửa sổ trượt), giới hạn lớn nhất của n và q, và kiểu dữ liệu cần dùng (int hay long long). Nếu một bài có thể giải bằng hai công cụ, hãy chọn công cụ đơn giản hơn và đủ nhanh.
-
Lưu ý thêm: Khi một bài có nhiều test mẫu, hãy chạy thử hết các test mẫu và tự nghĩ thêm các test nhỏ nhất (n = 1), test toàn số bằng nhau, và test giá trị lớn nhất. Đây là cách phát hiện lỗi long long, lỗi chỉ số l - 1 và lỗi mảng thiếu chỗ nhanh nhất.
Đáp án trò chơi nhận dạng
| Đề | Dạng bài | Độ phức tạp |
|---|---|---|
| 1 | Cộng dồn | n + q |
| 2 | Mảng hiệu | n + m |
| 3 | sort với pair và comparator | n log n |
| 4 | upper_bound trên dãy đã sắp | log n mỗi khách |
| 5 | Hai con trỏ cùng chiều (cửa sổ co giãn) | n |
| 6 | Cửa sổ trượt cố định (k = 7) | n |
| 7 | sort rồi hai con trỏ từ hai đầu | n log n |
| 8 | Sắp theo đầu đoạn rồi quét một lượt | n log n |