Set và Map
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 120 phút
- Học trước
- Tìm kiếm nhị phân
- Chủ đề
- mapset
- Trạng thái
Kiến thức cơ bản
Vì sao cần set và map
Ở các tuần trước, khi cần đếm số lần xuất hiện của mỗi giá trị, ta dùng mảng đếm cnt[x]++. Cách này rất nhanh nhưng chỉ dùng được khi x nhỏ (do giới hạn của mảng). Cách khác là đưa các giá trị vào vector rồi mỗi lần hỏi "có số x không?" thì duyệt từ đầu đến cuối. Với n = 105 số và 105 câu hỏi, ta mất khoảng 1010 phép tính, chậm hơn quy ước 108 khi lập trình thi đấu rất nhiều.
C++ có sẵn hai "cấu trúc dữ liệu" giải quyết vấn đề này: set và map.
Cấu trúc dữ liệu Set
Set là một cấu trúc dữ liệu đã được xây dựng sẵn, lưu trữ một tập hợp các phần tử duy nhất (không cho phép trùng lặp) và tự động sắp xếp các phần tử theo thứ tự tăng dần (mặc định). Để sử dụng set, ta cần thêm thư viện set: #include <set>.
Khai báo set
set <data_type> set_name; (ví dụ: set <int> se;)
Duyệt set
Tương tự như vector, sử dụng range-based for loop hoặc thông qua iterator.
#include <iostream>
#include <set>
using namespace std;
int main() {
set<int> se = {1, 2, 3}; // khai báo set, gán se = {1, 2, 3}
se.insert(3); // {1, 2, 3}, set vẫn giữ nguyên vì 3 đã tồn tại
se.insert(2); // {1, 2, 3}
se.insert(4); // {1, 2, 3, 4}, 4 được thêm vào set
// Duyệt set bằng range-based for loop
for(int x : se) cout << x <<" ";
cout <<endl;
// Duyệt set bằng iterator
for(auto it = se.begin(); it != se.end(); ++it) {
cout << *it <<" "; // *it: giá trị của it
}
return 0;
}
Các tính chất của set
- Set không có chỉ số: không viết được se[0], se[1].
- Nếu set chứa chuỗi (set<string>) thì các chuỗi được xếp theo thứ tự từ điển.
- *se.begin(), *se.rbegin() là hai số nhỏ nhất, lớn nhất của set.
- multiset cho phép lưu trữ nhiều phần tử có giá trị giống nhau; unordered_set (hash set) lưu trữ các phần tử duy nhất nhưng không theo bất kỳ thứ tự nào.
Một số hàm của set
| size() | Số lượng phần tử trong set |
|---|---|
| insert() | Thêm phần tử vào trong set |
| empty() | Kiểm tra set rỗng, nếu đúng trả về true, ngược lại trả về false |
| clear() | Xóa toàn bộ phần tử trong set |
| find() | Trả về iterator tới phần tử nếu tìm thấy, ngược lại sẽ trả về iterator end() của set |
| count() | Trả về số lần xuất hiện của phần tử trong set, do đó hàm này sẽ có giá trị trả về là 0 hoặc 1. Rất hay dùng: duyệt từng số x, nếu se.count(x) bằng 0 thì đây là lần đầu gặp. |
| erase() | Xóa một giá trị ra khỏi set, ngoài ra bạn cũng có thể xóa thông qua iterator trỏ tới giá trị đó trong set. |
| lower_bound() | Trả về iterator tới phần tử có giá trị nhỏ nhất lớn hơn hoặc bằng giá trị cần tìm kiếm. |
| upper_bound() | Trả về iterator tới phần tử có giá trị nhỏ nhất lớn hơn giá trị cần tìm kiếm. |
Cấu trúc dữ liệu Map
Trong thực tế, dữ liệu theo cặp đem lại nhiều sự tiện lợi, như khi đếm số phiếu bầu ({Hoa, 1}, {Lan, 3}, {Mai, 1},...), cặp toạ độ {x, y}, thời gian {bắt đầu, kết thúc} công việc,... Mỗi cặp bao một khoá (key) và giá trị (value): {key, value}.
Map là một cấu trúc dữ liệu được xây dựng sẵn trong C++, nó lưu trữ dữ liệu theo cặp khóa (key) và giá trị (value).
Để sử dụng được map, ta cần thêm thư viện map: #include <map>;
Khai báo map
map<key_data_type, value_data_type> map_name; (VD: map<int, int> mp;)
Để truy xuất value của key của map mp, người ta dùng mp[key].
Lệnh mp[k] = v: Ghi giá trị v vào khoá k (chưa có thì tự tạo, có rồi thì ghi đè).
Lệnh m[k]++: Tăng giá trị trong khoá k thêm 1 (khoá mới bắt đầu từ 0).
Duyệt map
// Duyệt tuần tự (range-based for loop) qua từng cặp key-value
for (auto& p : mp) {
// p.first, p.second tương ứng key, value
}
// Duyệt tách trực tiếp key, value
for (auto& [key, value] : mp) {
// xử lý ở đây
}
// Duyệt Iterator: xuôi, sử dụng .begin() và .end()
for(auto it = mp.begin(); it != mp.end(); ++it) {
// xử lý ở đây
}
// Duyệt Iterator: ngược, sử dụng .rbegin() và .rend()
for(auto it = mp.rbegin(); it != mp.rend(); ++it) {
// xử lý ở đây
}
Các tính chất của map
- Mỗi phần tử trong map chính là 1 pair ({key, value}).
- Map không hỗ trợ truy cập thông qua chỉ số như mảng hay vector, string.
- Các key trong map là riêng biệt, không có 2 key trùng nhau. Map duy trì thứ tự các phần tử theo giá trị key tăng dần.
- Map tìm kiếm giá trị key với độ phức tạp O(logN)
- Tương tự như map, multimap cho phép nhiều giá trị khác nhau ứng với cùng một key, trong khi unordered_map (hash map) lưu trữ key riêng biệt nhưng không theo bất kỳ thứ tự nào
Một số hàm của map
| size() | Số lượng phần tử trong map |
|---|---|
| empty() | Kiểm tra map rỗng, nếu đúng trả về true, ngược lại trả về false |
| clear() | Xóa toàn bộ phần tử trong map |
| insert() | Thêm phần tử vào trong map (mp.insert({1, 2});) Ngoài ra, còn có thể sử dụng cú pháp mp[key] = value để thêm cặp {key, value} vào trong map. |
| find() | Trả về iterator tới phần tử nếu tìm thấy, ngược lại sẽ trả về iterator end() của map |
| count() | Trả về số lần xuất hiện của phần tử trong map, do đó hàm này sẽ có giá trị trả về là 0 hoặc 1 |
| erase() | Xóa 1 cặp phần tử trong map thông qua key, có 2 cách sử dụng hàm này là xóa thông qua giá trị hoặc xóa thông qua iterator. |
| lower_bound() | Trả về iterator tới giá trị nhỏ nhất trong map có key lớn hơn hoặc bằng giá trị tìm kiếm |
| upper_bound() | Trả về iterator tới phần tử có giá trị nhỏ nhất lớn hơn giá trị cần tìm kiếm. |
Khi nào dùng mảng đếm, set, map
| Công cụ | Dùng khi nào | Ví dụ |
|---|---|---|
| Mảng đếm cnt[x] | Giá trị nhỏ (không quá 107), cần tốc độ cao nhất | Đếm điểm thi từ 0 đến 10; đếm chữ cái a..z |
| set | Chỉ cần biết "có hay không", bỏ trùng, cần dãy sắp xếp tăng dần | Số loại bút màu khác nhau; mã thẻ đã đăng ký |
| map | Cần đếm hoặc gắn một giá trị cho từng khóa; khóa lớn hoặc là chuỗi | Đếm phiếu bầu theo tên; sổ điểm theo tên bạn |
Luyện tập
Bài 1. Đếm loại bút màu
Hộp bút của Mai có n cái, mỗi cái ghi mã màu (một số nguyên). Hai cây có cùng mã là cùng loại màu. Mai muốn biết hộp bút có bao nhiêu loại màu khác nhau.
| Đầ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ố loại màu khác nhau | |
| Test | Input | Output |
| 1 | 6 5 3 5 1 3 9 | 4 |
| 2 | 5 7 7 7 7 7 | 1 |
Bài 2. Danh sách đăng ký
Thủ thư có danh sách n mã thẻ của các bạn đã đăng ký. Sau đó có q bạn đến hỏi: "Mã thẻ của mình có trong danh sách không?". Hãy giúp thủ thư trả lời.
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n mã thẻ (1 ≤ a[i] ≤ 109). Dòng 3: q mã cần hỏi, mỗi mã là một số x (1 ≤ x ≤ 109). | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng in YES nếu x có trong danh sách, ngược lại in NO | |
| Test | Input | Output |
| 1 | 5 3 10 20 30 40 50 20 25 50 | YES NO YES |
| 2 | 4 2 1000000000 5 5 7 7 8 | YES NO |
Bài 3. Danh sách khách mời
Câu lạc bộ nhận phiếu đăng ký tham dự tiệc theo thứ tự thời gian, nhưng có bạn nộp phiếu hai ba lần. Hãy in danh sách khách mời: mỗi bạn chỉ ghi một lần, tại lần đầu tiên bạn ấy nộp phiếu, giữ nguyên thứ tự nộp.
| Đầ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) là mã số các phiếu. | |
|---|---|---|
| Đầu ra | Các mã số sau khi bỏ lần lặp, theo thứ tự xuất hiện lần đầu, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 7 4 2 4 9 2 7 9 | 4 2 9 7 |
| 2 | 3 5 5 5 | 5 |
Bài 4. Xếp hàng
Bạn Bo sưu tầm n thẻ bài, mỗi thẻ có một số. Bo muốn mỗi số chỉ giữ lại một thẻ và xếp các thẻ từ số nhỏ đến số lớn. Em hãy làm sao cho set tự xếp hộ nhé.
| Đầ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 | Các số khác nhau theo thứ tự tăng dần, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 6 30 10 20 10 30 40 | 10 20 30 40 |
| 2 | 4 1000000000 1 1000000000 500 | 1 500 1000000000 |
Bài 5. Nhường cơ hội
Cô giáo gọi tên n lượt học sinh lên bảng. Cô muốn biết với mỗi lượt gọi, bạn đó đã được gọi trước đó hay chưa để nhường cơ hội cho các bạn khác. Tên chỉ gồm chữ cái thường, không có dấu cách.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n tên, mỗi tên dài không quá 20 ký tự. | |
|---|---|---|
| Đầu ra | n dòng, dòng thứ i in YES nếu tên thứ i đã xuất hiện ở các lượt trước, ngược lại in NO. | |
| Test | Input | Output |
| 5 lan mai lan hoa mai | NO NO YES NO YES | |
Bài 6. Số xuất hiện nhiều nhất
Trong buổi xổ số của lớp, n bạn mỗi bạn bốc một số. Số nào được bốc nhiều lần nhất sẽ là "số may mắn". Nếu có nhiều số cùng được bốc nhiều nhất thì chọn số nhỏ nhất.
| Đầ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 | Hai số cách nhau một dấu cách: số may mắn và số lần nó xuất hiện. | |
| Test | Input | Output |
| 1 | 7 4 2 4 9 2 7 4 | 4 3 |
| 2 | 6 5 3 5 3 8 1 | 3 2 |
Bài 7. Bầu lớp trưởng
Lớp có n phiếu bầu, mỗi phiếu ghi tên một bạn. Hãy lập bảng kết quả: mỗi bạn được bao nhiêu phiếu, các bạn xếp theo thứ tự bảng chữ cái (từ điển).
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n tên, mỗi tên chỉ gồm chữ cái thường, dài không quá 20 ký tự. | |
|---|---|---|
| Đầu ra | Mỗi dòng gồm một tên và số phiếu của tên đó, cách nhau một dấu cách, theo thứ tự từ điển của tên. | |
| Test | Input | Output |
| 6 lan mai lan hoa mai lan | hoa 1 lan 3 mai 2 | |
Bài 8. Điểm của thầy giáo
Thầy giáo dùng một cuốn sổ điểm có ba loại thao tác: ghi (hoặc sửa) điểm của một bạn, tra điểm của một bạn, và xóa một bạn khỏi sổ. Em hãy lập trình cuốn sổ này nhé.
| Đầ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 v: ghi điểm v cho bạn ten (nếu đã có thì ghi đè), 0 ≤ v ≤ 10. 2 ten: tra điểm của bạn ten. 3 ten: xóa bạn ten khỏi sổ (nếu không có thì bỏ qua). Tên chỉ gồm chữ cái thường, dài không quá 20 ký tự. | |
|---|---|---|
| Đầu ra | Với mỗi thao tác loại 2, in ra điểm của bạn đó, hoặc in -1 nếu bạn đó không có trong sổ. | |
| Test | Input | Output |
| 1 | 7 1 lan 8 1 mai 9 2 lan 1 lan 10 2 lan 3 mai 2 mai | 8 10 -1 |
| 2 | 4 2 hoa 1 hoa 5 3 hoa 2 hoa | -1 -1 |
Bài 9. Hai chiếc vé may mắn
Trong hộp có n chiếc vé, mỗi vé ghi một số. Em được chọn đúng hai chiếc vé ở hai vị trí khác nhau sao cho tổng hai số bằng K thì trúng thưởng. Hỏi em có thể trúng thưởng không?
| Đầ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 | In YES nếu có hai vị trí khác nhau i ≠ j mà a[i] + a[j] = K, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 5 9 2 7 11 4 5 | YES |
| 2 | 4 8 4 1 2 3 | NO |
Bài tập tự luyện
Bài 1. Giao của hai đội
Đội A có n bạn, đội B có m bạn, mỗi bạn có một mã số. Có những bạn tham gia cả hai đội. Hãy liệt kê các mã số xuất hiện ở cả hai đội (mỗi mã 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 A. Dòng 3: m mã số của đội B (các mã đều từ 1 đến 109). | |
|---|---|---|
| Đầu ra | Dòng 1: số lượng mã xuất hiện ở cả hai đội. 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 4 1 3 5 7 3 3 4 5 3 | 2 3 5 |
| 2 | 2 2 1 2 3 4 | 0 |
Bài 2. Chiếc tất lẻ
Bạn Bo có n chiếc tất, mỗi chiếc ghi một mã hoa văn. Hoa văn nào chỉ có đúng một chiếc thì gọi là tất "lẻ đôi". Hãy đếm xem có bao nhiêu hoa văn lẻ đôi.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n mã hoa văn a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số hoa văn xuất hiện đúng một lần. | |
| Test | Input | Output |
| 1 | 6 1 2 2 3 3 4 | 2 |
| 2 | 4 5 5 5 5 | 0 |
Bài 3. Điểm danh
Lớp có n bạn (tên không trùng nhau) được ghi theo danh sách lớp. Sáng nay có m bạn có mặt (nói tên theo thứ tự tùy ý). Hãy in tên các bạn vắng mặt theo đúng thứ tự trong danh sách lớp.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n tên trong danh sách. Dòng 3: số nguyên m (0 ≤ m ≤ n). Dòng 4: m tên các bạn có mặt (nếu m = 0 thì không có dòng này). Tên gồm chữ cái thường, dài không quá 20 ký tự. | |
|---|---|---|
| Đầu ra | Mỗi dòng một tên bạn vắng, theo thứ tự trong danh sách lớp. Nếu không ai vắng thì in NO. | |
| Test | Input | Output |
| 1 | 5 lan mai hoa cuc dao 3 hoa lan dao | mai cuc |
| 2 | 2 an binh 2 binh an | NO |
Bài 4. Ghép chữ cái
Bạn Tí có một bịch chữ cái bằng nhựa, ghi bởi xâu s (mỗi ký tự là một chữ cái nhựa). Tí muốn ghép từ t, mỗi chữ cái nhựa chỉ được dùng tối đa một lần. Hỏi Tí có ghép được không?
| Đầu vào | Dòng 1: xâu s. Dòng 2: xâu t. Hai xâu gồm chữ cái thường, độ dài từ 1 đến 105. | |
|---|---|---|
| Đầu ra | In YES nếu ghép được t, ngược lại in NO. | |
| Test | Input | Output |
| 1 | xemhoathan hoa | YES |
| 2 | abc aab | NO |
Bài 5. Số xuất hiện đúng k lần
Cho dãy n số nguyên và một số k. Hãy liệt kê các giá trị xuất hiện trong dãy đúng k lần.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 105; 1 ≤ k ≤ n). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Các giá trị xuất hiện đúng k lần, theo thứ tự tăng dần, cách nhau một dấu cách. Nếu không có giá trị nào thì in -1. | |
| Test | Input | Output |
| 1 | 8 2 5 1 5 1 9 9 9 2 | 1 5 |
| 2 | 5 3 1 2 3 4 5 | -1 |
Bài 6. Cặp quân cờ giống nhau
Gấu Po xếp một hàng gồm n quân cờ, mỗi quân ghi một số. Hãy đếm xem có bao nhiêu cặp chỉ số (i, j) với i < j mà hai quân cờ ở hai vị trí đó ghi cùng một số.
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 2 × 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cặp quân cờ giống nhau. | |
| Test | Input | Output |
| 1 | 6 1 2 1 2 1 3 | 4 |
| 2 | 4 5 5 5 5 | 6 |
Bài 7. Hai bạn hơn kém nhau K tuổi
Cho n số nguyên (tuổi các bạn trong câu lạc bộ) và một số K. Hãy đếm số cặp chỉ số (i, j) với i < j sao cho hai tuổi hơn kém nhau đúng K, tức là |a[i] - a[j]| = K.
| Đầu vào | Dòng 1: hai số nguyên n, K (2 ≤ n ≤ 105; 1 ≤ K ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cặp thỏa mãn. | |
| Test | Input | Output |
| 1 | 5 2 1 3 5 3 1 | 6 |
| 2 | 4 5 7 7 7 7 | 0 |
Bài 8. Đoạn dài nhất không trùng
Một hàng n bạn đứng cạnh nhau, mỗi bạn đeo một số áo. Cô giáo muốn chọn một đoạn các bạn đứng liên tiếp sao cho không có hai bạn nào cùng số áo. Hỏi đoạn như vậy dài nhất là bao nhiêu bạn?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 3000). 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 mà các số đều khác nhau. | |
| Test | Input | Output |
| 1 | 8 1 2 3 1 4 5 2 6 | 6 |
| 2 | 5 7 7 7 7 7 | 1 |
Bài 9. Thử thách: Dãy số liên tiếp dài nhất
Cho n số nguyên (không cần đứng cạnh nhau, có thể trùng). Hãy tìm dãy dài nhất gồm các giá trị liên tiếp nhau như x, x+1, x+2, ..., x+L-1 mà tất cả đều có mặt trong n số đó. Ví dụ với các số 100, 4, 200, 1, 3, 2 thì dãy 1, 2, 3, 4 có độ dài 4.
| Đầ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 | Độ dài L lớn nhất. | |
| Test | Input | Output |
| 1 | 7 100 4 200 1 3 2 101 | 4 |
- 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.