Ứng dụng set, map
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 90 phút
- Học trước
- Set và Map
- Chủ đề
- mapset
- Trạng thái
Kiến thức cơ bản
Nhìn lại set và map
Tuần trước, em đã làm quen với hai người bạn mới: set là chiếc hộp thẻ bài (mỗi loại chỉ giữ một thẻ, các thẻ luôn tự xếp từ nhỏ đến lớn) và map là chiếc tủ ngăn kéo có dán nhãn (nhãn nào thì ngăn đó). Tuần này, ta dùng hai người bạn ấy để giải năm kiểu bài rất hay gặp trong các kỳ thi.
Mỗi lần thêm, xóa hay tìm trong set hoặc map chỉ mất khoảng log n bước. Với n = 105 thì log n chỉ khoảng 17, cả bài mất khoảng 1,7 triệu phép tính, một cái chớp mắt của máy tính. Trong khi tìm bằng cách duyệt cả dãy cho mỗi câu hỏi sẽ mất 1010 phép tính, quá chậm so với quy ước 108.
Những hàm sẽ dùng nhiều trong tuần này
| count(x) | Hỏi “có x không?”, trả về 0 hoặc 1. Dùng để kiểm tra mà không làm thay đổi set hay map. |
|---|---|
| find(x) | Trả về iterator tới x nếu tìm thấy, ngược lại trả về end(). |
| insert(x) | Thêm x vào set. Với map thì dùng mp[k] = v để ghi giá trị v vào khóa k. |
| erase(x) | Xóa x (hoặc xóa khóa x) ra khỏi set hoặc map. Xóa thứ không có thì không sao. |
| size() | Số phần tử của set, hoặc số khóa hiện có của map. |
| lower_bound(x) | Trả về iterator tới phần tử nhỏ nhất lớn hơn hoặc bằng x; nếu không có thì trả về end(). |
| upper_bound(x) | Trả về iterator tới phần tử nhỏ nhất lớn hơn x; nếu không có thì trả về end(). |
| begin(), rbegin() | Iterator tới phần tử nhỏ nhất, lớn nhất. Viết *se.begin(), *se.rbegin() để lấy giá trị. |
| prev(it), --it | Lùi một bước về phần tử đứng ngay trước it. Chỉ lùi được khi it chưa phải là begin(). |
Cái bẫy cần nhớ
- Viết mp[k] khi khóa k chưa có sẽ âm thầm tạo thêm cặp {k, 0}, làm size() tăng lên và kết quả sai. Chỉ muốn hỏi “có khóa k không?” thì dùng mp.count(k) hoặc mp.find(k).
- Trước khi viết *it với it lấy từ find() hoặc lower_bound(), phải kiểm tra it khác end(). Lấy giá trị tại end() là lỗi nguy hiểm.
Mẫu 1: Đếm số loại khác nhau
Bài toán: cho n số, hỏi có bao nhiêu giá trị khác nhau? Hoặc có bao nhiêu giá trị xuất hiện đúng một lần? Ta ném từng số vào hộp set, số trùng sẽ bị bỏ, cuối cùng nhìn xem hộp có bao nhiêu thẻ.
Dãy số: 5 3 5 1 3 9
| | | | | |
v v v v v v (ném từng số vào hộp)
Hộp set: { 1 3 5 9 } -> se.size() = 4 loại
Muốn biết mỗi loại có bao nhiêu thẻ, ta đổi hộp thẻ thành tủ ngăn kéo (map): mỗi nhãn là một giá trị, trong ngăn ghi số lần xuất hiện. Số khóa của map chính là số loại khác nhau.
- Lưu ý: Các đoạn code trong bài này chỉ là phần thân của hàm main. Em nhớ thêm #include <iostream>, <set>, <map> và using namespace std; khi chạy thật.
map<int, int> cnt; // nhãn = giá trị, ngăn = số lần
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++; // ngăn x tăng thêm 1
}
cout << cnt.size() << endl; // số loại khác nhau
int soLe = 0;
for (auto& [val, c] : cnt) // duyệt từng ngăn kéo
if (c == 1) soLe++; // loại chỉ có đúng một thẻ
cout << soLe << endl;
Mẫu 2: Tra cứu nhanh
Bài toán: cho n số, sau đó có q câu hỏi, mỗi câu hỏi “số x xuất hiện bao nhiêu lần?” (hoặc “có số x không?”). Nếu mỗi câu hỏi lại duyệt cả dãy thì mất n × q = 1010 phép tính, quá chậm. Hãy lập sổ tra cứu trước, rồi mỗi câu hỏi chỉ mất log n bước.
map<int, int> cnt;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
while (q--) {
int x;
cin >> x;
if (cnt.count(x) == 0) cout << 0 << "\n"; // KHÔNG viết cnt[x]
else cout << cnt[x] << "\n";
}
Chú ý dòng if: nếu viết thẳng cnt[x] khi chưa có khóa x, map sẽ tự tạo thêm khóa x. Kết quả in ra vẫn là 0, nhưng bài nào có hỏi size() sau đó sẽ bị sai. Khi in nhiều dòng, em dùng "\n" thay cho endl để chương trình chạy nhanh hơn.
Mẫu 3: Tìm cặp có tổng bằng K
Bài toán: cho n số và một số K. Có hai số ở hai vị trí khác nhau cộng lại bằng K hay không? Cách chậm là thử mọi cặp (i, j): n × n = 1010 phép tính khi n = 105.
Cách nhanh: mỗi số a[i] đi tìm “nửa còn lại” của mình, đó là K - a[i]. Hãy tưởng tượng mỗi bạn cầm một nửa tấm vé, chỉ ghép được với bạn cầm nửa vé còn lại. Các bạn lần lượt bước vào lớp. Bạn nào bước vào thì nhìn xem nửa vé của mình đã có ai trong lớp chưa: có thì ghép cặp, chưa có thì ngồi xuống chờ.
K = 9 Dãy: 2 7 11 4 5
Xét 2: cần 9-2 = 7, hộp {} : có 7? KHÔNG -> cất 2 vào hộp
Xét 7: cần 9-7 = 2, hộp {2} : có 2? CÓ! -> được cặp (2, 7)
long long K;
cin >> K;
set<long long> seen; // hộp: các số đã bước vào lớp
bool found = false;
for (int i = 0; i < n; i++) {
long long need = K - a[i]; // nửa còn lại của a[i]
if (seen.count(need)) found = true; // đã có bạn giữ nửa kia
seen.insert(a[i]); // xét xong rồi mới cho vào hộp
}
cout << (found ? "YES" : "NO");
Hai điều em cần nhớ:
- Kiểm tra trước, cất vào hộp sau. Nếu cất a[i] vào hộp trước rồi mới hỏi, số 5 khi K = 10 sẽ tự ghép với chính nó (cùng một vị trí). Làm đúng thứ tự thì 5 chỉ ghép được với một số 5 khác đứng trước.
- Dùng long long. Khi a[i] lên tới 109 và K lên tới 2.109, phép tính K - a[i] hoặc tổng hai số có thể vượt giới hạn của int (em đã học ở tuần 1 và tuần 4).
Muốn đếm số cặp, ta đổi hộp set thành tủ map để biết nửa vé kia đang có bao nhiêu bạn giữ:
map<long long, long long> cnt;
long long dem = 0; // số cặp có thể rất lớn: dùng long long
for (int i = 0; i < n; i++) {
long long need = K - a[i];
if (cnt.count(need)) dem += cnt[need]; // ghép với mọi nửa kia
cnt[a[i]]++;
}
cout << dem;
Em cũng đã biết một cách khác là sắp xếp rồi dùng hai con trỏ (tuần 15). Cả hai cách đều chạy khoảng n log n. Set và map tiện hơn khi đề hỏi vị trí ban đầu của hai số hoặc muốn đếm số cặp.
Mẫu 4: Tìm giá trị gần nhất
Bài toán: có một tập số và nhiều câu hỏi dạng “trong tập, số nhỏ nhất không nhỏ hơn x là số nào?”. Set luôn xếp thẳng hàng từ nhỏ đến lớn nên lower_bound (đã học ở tuần 19) trả lời ngay, chỉ mất log n bước. Muốn tìm số lớn nhất nhỏ hơn x, em lấy lower_bound rồi lùi một bước.
set: 10 20 30 50
^
x = 15 : lower_bound(15) trỏ vào 20 (nhỏ nhất >= 15)
lùi một bước (prev) về 10 (lớn nhất < 15)
x = 51 : lower_bound(51) trỏ vào end() (không có)
auto it = se.lower_bound(x); // nhỏ nhất >= x
if (it == se.end()) cout << -1; // PHẢI kiểm tra trước *it
else cout << *it;
it = se.lower_bound(x); // lớn nhất < x
if (it == se.begin()) cout << -1; // phía trước không còn ai
else cout << *prev(it); // lùi một bước
Mẫu 5: Kết hợp map với cửa sổ trượt
Ở tuần 16, em trượt một cửa sổ gồm k phần tử liên tiếp. Nếu cần biết trong cửa sổ có bao nhiêu giá trị khác nhau, hãy để một map làm tủ đếm cho cửa sổ: phần tử mới bước vào thì ngăn của nó tăng 1, phần tử cũ bước ra thì ngăn của nó giảm 1. Ngăn nào về 0 thì phải dọn bỏ bằng erase, nếu không size() sẽ đếm cả những loại đã đi hết.
map<int, int> cnt; // tủ đếm cho cửa sổ
for (int i = 0; i < n; i++) {
cnt[a[i]]++; // đèn mới bước vào khung
if (i >= k) { // đèn cũ ra khỏi khung
int out = a[i - k];
cnt[out]--;
if (cnt[out] == 0) cnt.erase(out); // hết thì dọn ngăn kéo
}
if (i >= k - 1) cout << cnt.size() << " ";
}
Mở rộng (không bắt buộc): multiset
multiset giống set nhưng cho phép nhiều thẻ giống nhau, vẫn tự xếp theo thứ tự. Nhờ vậy *ms.begin() và *ms.rbegin() luôn là số nhỏ nhất, lớn nhất đang có, kể cả khi có số trùng. Cẩn thận khi xóa: ms.erase(x) xóa tất cả các thẻ bằng x, còn muốn xóa đúng một thẻ thì viết ms.erase(ms.find(x)).
multiset<int> ms;
ms.insert(5); ms.insert(5); ms.insert(2); // {2, 5, 5}
ms.erase(ms.find(5)); // {2, 5}: chỉ xóa MỘT thẻ 5
cout << *ms.begin() << " " << *ms.rbegin(); // 2 5
Nhận dạng đề bài
| Dấu hiệu trong đề | Công cụ | Cách làm |
|---|---|---|
| Đếm số loại khác nhau, bỏ các giá trị trùng | set | se.insert(x) rồi lấy se.size() |
| Mỗi giá trị xuất hiện mấy lần; có q câu hỏi tra cứu | map | cnt[x]++ khi đọc; khi hỏi thì kiểm tra bằng count hoặc find |
| Tìm (hoặc đếm) cặp có tổng bằng K | set hoặc map | Duyệt từng a[i], hỏi “K - a[i] đã gặp chưa?” rồi mới cất a[i] |
| Số nhỏ nhất ≥ x, số lớn nhất < x | set + lower_bound | Luôn kiểm tra end() và begin() trước khi lấy giá trị |
| Mỗi đoạn hay cửa sổ có bao nhiêu loại | map + cửa sổ trượt | Ngăn nào về 0 thì erase |
Luyện tập
Bài 1. Gộp hai kho báu
Gấu Po và Thỏ mỗi bạn có một kho báu gồm các viên ngọc, mỗi viên có một mã số; hai viên cùng mã số là cùng loại ngọc. Hai bạn đổ tất cả ngọc vào một chiếc rương chung. Hỏi trong rương có bao nhiêu loại ngọc khác nhau?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105) là số ngọc của Gấu Po và của Thỏ. Dòng 2: n mã số ngọc của Gấu Po (1 ≤ a[i] ≤ 109). Dòng 3: m mã số ngọc của Thỏ (1 ≤ b[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số loại ngọc khác nhau trong rương. | |
| Test | Input | Output |
| 1 | 4 3 1 2 3 2 3 4 1 | 4 |
| 2 | 2 2 5 5 5 5 | 1 |
Bài 2. Số thứ tự còn trống
Hổ phát cho n bạn, mỗi bạn một tấm thẻ ghi số thứ tự. Hổ muốn tìm số nguyên dương nhỏ nhất mà chưa có bạn nào cầm thẻ ghi số đó, để dành cho bạn đến muộn.
| Đầ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 | Số nguyên dương nhỏ nhất không xuất hiện trong dãy. | |
| Test | Input | Output |
| 1 | 5 1 2 4 5 7 | 3 |
| 2 | 3 2 3 4 | 1 |
Bài 3. Hỏi đáp trên bảng
Gấu Po viết n số lên bảng. Thỏ lần lượt hỏi q câu, mỗi câu có dạng: “Số x được viết bao nhiêu lần trên bảng?”. Hãy giúp Gấu Po trả lời thật nhanh.
| Đầ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 x (1 ≤ x ≤ 109) là các số Thỏ hỏi. | |
|---|---|---|
| Đầu ra | q dòng, dòng thứ i là số lần xuất hiện của số x thứ i trong dãy (bằng 0 nếu số đó không có). | |
| Test | Input | Output |
| 1 | 6 3 4 2 4 9 2 4 4 7 2 | 3 0 2 |
| 2 | 3 2 8 8 8 8 1 | 3 0 |
Bài 4. Chiếc chìa khóa vừa đủ
Hổ có chùm n chiếc chìa khóa, mỗi chiếc khắc một số. Cánh cửa số x chỉ mở được bằng chiếc chìa khóa có số không nhỏ hơn x, và Hổ muốn chọn chiếc có số nhỏ nhất như vậy để không lãng phí. Với mỗi cánh cửa, hãy cho biết số khắc trên chiếc chìa khóa Hổ 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) là các số khắc trên chìa khóa (có thể trùng nhau). Dòng 3: q số nguyên x (1 ≤ x ≤ 109) là số của các cánh cửa. | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng in số khắc trên chiếc chìa khóa được chọn, hoặc in -1 nếu không có chìa nào mở được. | |
| Test | Input | Output |
| 1 | 5 4 10 30 20 30 50 5 20 31 51 | 10 20 50 -1 |
| 2 | 3 2 7 7 7 7 8 | 7 -1 |
Bài 5. Hai chiếc bánh ngọt
Thỏ có n chiếc bánh xếp thành một hàng, chiếc thứ i có độ ngọt a[i]. Thỏ muốn chọn hai chiếc bánh ở hai vị trí i < j sao cho tổng độ ngọt đúng bằng K. Nếu có nhiều cách chọn, Thỏ chọn cách có j nhỏ nhất; nếu vẫn còn nhiều cách thì chọn cách có i nhỏ nhất.
| Đầ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 | Hai số i và j cách nhau một dấu cách (vị trí đánh số từ 1), hoặc in -1 nếu không chọn được. | |
| Test | Input | Output |
| 1 | 6 10 3 8 5 4 5 7 | 3 5 |
| 2 | 3 100 1 2 3 | -1 |
Bài 6. Đếm cặp đồng xu
Gấu Po có n đồng xu, đồng xu thứ i có giá trị a[i]. Hỏi có bao nhiêu cách chọn hai đồng xu (hai vị trí i < j) sao cho tổng giá trị đúng bằng K?
| Đầ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ặp (i, j) với i < j thỏa mãn a[i] + a[j] = K. | |
| Test | Input | Output |
| 1 | 6 6 1 5 3 3 3 5 | 5 |
| 2 | 4 4 2 2 2 2 | 6 |
Bài 7. Bảng điểm giải đấu
Giải đấu của rừng xanh có n lượt ghi điểm. Mỗi lượt được ghi trên một dòng gồm tên bạn ghi điểm và số điểm bạn đó ghi được. Hãy lập bảng tổng điểm của từng bạn, xếp 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ỉ gồm chữ cái thường, dài không quá 20 ký tự) và số điểm d (0 ≤ d ≤ 1000), cách nhau một dấu cách. | |
|---|---|---|
| Đầu ra | Mỗi dòng gồm một tên và tổng điểm của bạn đó, cách nhau một dấu cách, theo thứ tự từ điển của tên. | |
| Test | Input | Output |
| 1 | 5 po 10 tho 7 ho 5 po 3 tho 1 | ho 5 po 13 tho 8 |
| 2 | 1 ho 0 | ho 0 |
Bài 8. Nhóm từ anh em
Thỏ có n tấm thẻ, mỗi thẻ ghi một từ. Hai từ được gọi là “anh em” nếu xáo trộn các chữ cái của từ này thì được từ kia (ví dụ listen và silent). Thỏ xếp các từ anh em vào cùng một nhóm. Hỏi Thỏ có tất cả bao nhiêu nhóm?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n từ, mỗi từ chỉ gồm chữ cái thường và dài không quá 20 ký tự. | |
|---|---|---|
| Đầu ra | Số nhóm từ anh em. | |
| Test | Input | Output |
| 1 | 6 listen silent enlist google gogole cat | 3 |
| 2 | 3 ab ba ab | 1 |
Bài 9. Khung kính trượt
Hổ treo n chiếc đèn lồng thành một hàng, chiếc thứ i có màu a[i]. Hổ dùng một khung kính che vừa k đèn liên tiếp và trượt từ trái sang phải. Với mỗi vị trí của khung, hãy cho biết Hổ nhìn thấy bao nhiêu màu khác nhau trong khung.
| Đầ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 | n - k + 1 số cách nhau một dấu cách, số thứ t là số màu khác nhau trong khung khi khung bắt đầu ở đèn thứ t. | |
| Test | Input | Output |
| 1 | 7 3 1 2 1 3 3 3 2 | 2 3 2 1 2 |
| 2 | 4 4 5 5 5 5 | 1 |
Bài tập tự luyện
Bài 1. Chỉ có ở đội Thỏ
Đội của Thỏ có n bạn, đội của Hổ có m bạn, mỗi bạn có một mã số. Hãy liệt kê các mã số có ở đội Thỏ nhưng không có ở đội Hổ (mỗi mã chỉ in một lần).
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105). Dòng 2: n mã số của đội Thỏ. Dòng 3: m mã số của đội Hổ (các mã đều từ 1 đến 109). | |
|---|---|---|
| Đầu ra | Dòng 1: số lượng mã số thỏa mãn. Nếu số lượng này lớn hơn 0, dòng 2 in các mã đó theo thứ tự tăng dần. | |
| Test | Input | Output |
| 1 | 5 3 1 3 5 7 3 3 4 5 | 2 1 7 |
| 2 | 2 2 1 2 2 1 | 0 |
Bài 2. Từ bị lặp đầu tiên
Gấu Po đọc lần lượt n từ. Hãy cho biết từ nào là từ lặp đầu tiên, tức là tìm vị trí j nhỏ nhất sao cho từ thứ j đã xuất hiện ở một vị trí trước đó. Nếu không có từ nào lặp lại thì in -1.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n từ, mỗi từ chỉ gồm chữ cái thường và dài không quá 20 ký tự. | |
|---|---|---|
| Đầu ra | Từ lặp đầu tiên, hoặc -1 nếu không có. | |
| Test | Input | Output |
| 1 | 6 bua keo bao keo bua tay | keo |
| 2 | 3 an binh cuc | -1 |
Bài 3. Huy chương bạc
Cuộc thi chạy có n bạn tham gia, mỗi bạn có một số điểm. Các bạn có điểm cao nhất cùng nhận huy chương vàng. Huy chương bạc thuộc về các bạn có điểm cao nhì, tức là cao nhất trong số những điểm thấp hơn điểm vàng. Hãy cho biết điểm của huy chương bạc.
| Đầ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 | Điểm của huy chương bạc, hoặc -1 nếu mọi bạn đều cùng điểm. | |
| Test | Input | Output |
| 1 | 6 90 85 90 70 85 60 | 85 |
| 2 | 3 5 5 5 | -1 |
Bài 4. Câu lạc bộ ra vào
Câu lạc bộ rừng xanh có một chiếc cửa. Gấu Po ghi lại q sự kiện: có bạn đi vào, có bạn đi ra, hoặc Gấu Po đếm xem trong phòng đang có bao nhiêu bạn. Lưu ý một bạn đã ở trong phòng mà vào thêm lần nữa thì vẫn chỉ tính là một bạn, và bạn không có trong phòng mà đi ra thì bỏ qua.
| Đầu vào | Dòng 1: số nguyên q (1 ≤ q ≤ 105). q dòng sau, mỗi dòng là một trong ba dạng: 1 ten: bạn ten đi vào phòng. 2 ten: bạn ten đi ra khỏi phòng. 3: Gấu Po đếm số bạn đang có trong phòng. Tên chỉ gồm chữ cái thường, dài không quá 20 ký tự. | |
|---|---|---|
| Đầu ra | Với mỗi sự kiện loại 3, in ra số bạn đang có trong phòng. | |
| Test | Input | Output |
| 1 | 7 1 po 1 tho 3 1 po 2 ho 2 po 3 | 2 1 |
| 2 | 3 3 1 an 3 | 0 1 |
Bài 5. Cột mốc gần nhất
Trên con đường rừng có n cột mốc, cột mốc thứ i đặt tại vị trí a[i] (có thể có nhiều cột mốc cùng vị trí). Hổ lần lượt đứng ở q vị trí x. Với mỗi vị trí, hãy cho biết cột mốc nào gần Hổ nhất. Nếu có hai cột mốc cách đều Hổ thì chọn cột mốc có vị trí nhỏ hơ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). Dòng 3: q số nguyên x (1 ≤ x ≤ 109). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng in vị trí của cột mốc gần Hổ nhất. | |
| Test | Input | Output |
| 1 | 4 4 10 20 30 40 25 5 100 30 | 20 10 40 30 |
| 2 | 1 2 7 1 9 | 7 7 |
Bài 6. Ba chiếc vé may mắn
Trong hộp có n chiếc vé, mỗi vé ghi một số. Thỏ được chọn đúng ba chiếc vé ở ba vị trí khác nhau, và sẽ trúng thưởng nếu tổng ba số bằng K. Hỏi Thỏ có thể trúng thưởng không?
| Đầu vào | Dòng 1: hai số nguyên n, K (3 ≤ n ≤ 2000; 3 ≤ K ≤ 3.109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | In YES nếu có ba vị trí i < j < k mà a[i] + a[j] + a[k] = K, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 5 6 2 2 2 9 1 | YES |
| 2 | 4 20 10 10 7 5 | NO |
Bài 7. Đoạn đường có tổng K
Thỏ đi qua n trạm liên tiếp. Ở trạm thứ i, Thỏ nhận được a[i] đồng (nếu a[i] âm thì Thỏ phải trả |a[i]| đồng). Hỏi có bao nhiêu đoạn gồm các trạm liên tiếp mà tổng số tiền Thỏ nhận được đúng bằng K?
| Đầu vào | Dòng 1: hai số nguyên n, K (1 ≤ n ≤ 105; |K| ≤ 1014). Dòng 2: n số nguyên a[i] (|a[i]| ≤ 109). | |
|---|---|---|
| Đầu ra | Số đoạn liên tiếp có tổng bằng K. | |
| Test | Input | Output |
| 1 | 5 3 1 2 1 2 1 | 4 |
| 2 | 4 0 1 -1 1 -1 | 4 |
Bài 8. Dãy áo dài nhất
Một hàng n bạn đứng cạnh nhau, bạn thứ i mặc áo số a[i]. Gấu Po muốn chọn một đoạn các bạn đứng liên tiếp sao cho trong đoạn đó có tối đa k số áo khác nhau. Hỏi đoạn như vậy dài nhất là bao nhiêu bạn?
| Đầ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 | Độ dài lớn nhất của đoạn liên tiếp có tối đa k giá trị khác nhau. | |
| Test | Input | Output |
| 1 | 7 2 1 2 1 3 3 3 2 | 4 |
| 2 | 5 1 7 7 8 8 8 | 3 |
Bài 9. Thử thách (không bắt buộc): Độ chênh trong khung kính
Hổ có n cây cột với chiều cao a[i] xếp thành hàng. Hổ cầm một khung kính che k cây liên tiếp và trượt từ trái sang phải. Với mỗi vị trí của khung, hãy cho biết hiệu giữa chiều cao lớn nhất và nhỏ nhất của các cây trong khung. (Gợi ý: dùng multiset, nhớ xóa đúng một thẻ khi cây ra khỏi khung.)
| Đầ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 | n - k + 1 số cách nhau một dấu cách, số thứ t là hiệu lớn nhất - nhỏ nhất trong khung khi khung bắt đầu ở cây thứ t. | |
| Test | Input | Output |
| 1 | 6 3 4 1 7 3 9 2 | 6 6 6 7 |
| 2 | 3 1 5 5 5 | 0 0 0 |
-
Gợi ý chung: Khi chỉ muốn kiểm tra khóa k có trong map hay không, hãy dùng mp.count(k) hoặc mp.find(k), đừng dùng mp[k]. Nếu khóa k chưa có, mp[k] sẽ âm thầm tạo thêm một cặp {k, 0} và làm size() tăng lên, dẫn đến kết quả sai.
-
Lưu ý thêm: Khi cộng hoặc trừ các số lớn (cặp có tổng K, tổng tiền tố, đếm số cặp) hãy dùng long long. Khi tìm cặp, kiểm tra “nửa còn lại” trước rồi mới cất số hiện tại vào set hay map. Trước khi viết *it với it lấy từ find() hoặc lower_bound(), hãy kiểm tra it khác end().