Ôn tổng hợp GĐ3
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 90 phút
- Học trước
- Set và Map, Ứng dụng set, map, Stack, Queue, Deque, Priority_queue, Sinh kế tiếp, Quay lui (1), Quay lui (2)
- Chủ đề
- ôn tập
- Trạng thái
Kiến thức cơ bản
Bản đồ kiến thức giai đoạn 3
Trong bảy tuần qua, em đã học thêm bảy công cụ mới. Tuần này em không học thêm gì mới, mà tập chọn đúng công cụ cho từng bài và dùng chúng phối hợp với nhau. Bảng dưới đây gom tất cả lại.
| Công cụ | Hình ảnh dễ nhớ | Dùng khi | Chi phí mỗi thao tác |
|---|---|---|---|
| set | Hộp thẻ bài, mỗi loại một thẻ, tự xếp tăng dần | Bỏ trùng, hỏi “có không”, tìm số nhỏ nhất ≥ x | log n |
| map | Tủ ngăn kéo có dán nhãn | Đếm tần suất, gắn giá trị cho từng khóa (số lớn hoặc chuỗi) | log n |
| stack | Chồng đĩa | Việc đến sau làm trước: ngoặc, hoàn tác, phần tử lớn hơn gần nhất | 1 |
| queue | Hàng mua vé | Đến trước phục vụ trước, mô phỏng vòng tròn | 1 |
| priority_queue | Hộp kẹo luôn đưa gói to nhất lên trên | Lấy lớn nhất (nhỏ nhất) nhiều lần, ghép hai số nhỏ nhất, k số lớn nhất | log n |
| Sinh kế tiếp | Công tơ mét | Liệt kê mọi cấu hình theo thứ tự, tìm cấu hình đứng ngay sau | Khoảng n bước cho mỗi cấu hình |
| Quay lui | Đi hết các ngã rẽ trong rừng, xóa dấu chân khi quay về | Cấu hình có điều kiện, đường đi, quân hậu, chỉ cần một nghiệm hoặc nghiệm tốt nhất | Số cấu hình (2^n, n!, ...) sau khi cắt tỉa |
Khuôn viết nhanh
set<int> se; se.insert(x); se.count(x); se.erase(x); *se.begin();
se.lower_bound(x); se.size();
map<string, int> mp; mp[k]++; mp.count(k); mp.erase(k);
for (auto& [key, val] : mp) { ... }
stack<int> st; st.push(x); st.top(); st.pop(); st.empty();
queue<int> q; q.push(x); q.front(); q.pop(); q.empty();
priority_queue<int> pq; // top() là số LỚN nhất
priority_queue<int, vector<int>, greater<int>> pq; // top() là số NHỎ nhất
next_permutation(a.begin(), a.end()); // hoán vị kế tiếp (trả về false nếu hết)
void Try(int pos) { điều kiện dừng; for (lựa chọn) { ghi; Try(pos + 1); hủy; } }
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 nhìn giới hạn của n để biết cách giải nào đủ nhanh.
| Giới hạn n | Cách làm có thể | Ví dụ |
|---|---|---|
| n ≤ 10 | Thử mọi hoán vị (n!) hoặc quay lui | Xếp chỗ ngồi, chọn công việc |
| n ≤ 20 | Thử mọi tập con (2^n) | Chia đôi quà, tập con có tổng S |
| n ≤ 1000 | Hai vòng for lồng nhau (n²) | Đếm cặp, đoạn dài nhất bằng cách thử tất cả |
| n ≤ 105 | n log n: sort, set, map, priority_queue; hoặc n bước: stack, hai con trỏ | Cặp có tổng K, k số lớn nhất, người cao hơn gần nhất |
Tám lỗi hay gặp
- mp[k] khi khóa k chưa có sẽ tự tạo khóa mới và làm size() sai. Chỉ kiểm tra thì dùng count hoặc find.
- Gọi top(), front(), pop() khi stack, queue, priority_queue rỗng sẽ lỗi. Luôn kiểm tra empty() trước.
- Lấy *it khi it == end() là lỗi nguy hiểm. Luôn kiểm tra sau find() và lower_bound().
- priority_queue mặc định lấy số LỚN nhất. Cần số nhỏ nhất thì dùng greater<int>.
- Khi tổng, tích hoặc số cặp có thể vượt 2 tỷ, dùng long long.
- Quay lui: quên hủy lựa chọn (pop_back, bỏ đánh dấu vis hoặc used) làm các nhánh sau sai.
- Cặp có tổng K: 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 hoặc map.
- Loang đếm vùng thì không xóa dấu vis, còn đếm đường đi thì phải xóa dấu khi quay lui.
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 trên? (2) n 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 kiểm tra rỗng hay end()? Sau đó mới gõ code. Một số bài dưới đây cần dùng hai công cụ cùng lúc.
Luyện tập
Bài 1. Bảng xếp hạng từ khóa
Thỏ đọc n từ khóa trên mạng và muốn lập bảng xếp hạng. Từ nào xuất hiện nhiều lần hơn thì xếp trước; nếu bằng nhau thì xếp theo thứ tự bảng chữ cái. Hãy in k từ đứng đầu bảng.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ 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 | Mỗi dòng gồm một từ và số lần xuất hiện, cách nhau một dấu cách. In nhiều nhất k dòng (nếu có ít hơn k từ khác nhau thì in tất cả). | |
| Test | Input | Output |
| 1 | 7 2 meo cho meo ga cho meo ga | meo 3 cho 2 |
| 2 | 4 3 b a b a | a 2 b 2 |
Bài 2. Ngoặc đúng dài nhất
Gấu Po viết một dãy gồm các dấu ( và ). Hãy tìm độ dài lớn nhất của đoạn liên tiếp trong dãy mà đoạn đó là dãy ngoặc đúng (mỗi dấu đóng ghép được với một dấu mở đứng trước, không còn dấu mở nào thừa).
| Đầu vào | Một dòng duy nhất là xâu s gồm các dấu ( và ), dài từ 1 đến 105 ký tự. | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của đoạn là dãy ngoặc đúng (in 0 nếu không có). | |
| Test | Input | Output |
| 1 | (()())( | 6 |
| 2 | )()()) | 4 |
| 3 | ))(( | 0 |
Bài 3. Quầy phục vụ
Ngân hàng của rừng xanh có k quầy phục vụ, ban đầu đều rảnh. Có n khách xếp hàng theo thứ tự, khách thứ i cần t[i] phút. Khi đến lượt, khách đến quầy rảnh sớm nhất (nếu nhiều quầy cùng rảnh sớm nhất thì chọn quầy bất kỳ, kết quả không đổi). Hỏi sau bao nhiêu phút thì khách cuối cùng được phục vụ xong, tức là sau bao nhiêu phút mọi khách đều được phục vụ xong?
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 105; 1 ≤ k ≤ 105). Dòng 2: n số nguyên t[i] (1 ≤ t[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Thời điểm mọi khách đều được phục vụ xong. | |
| Test | Input | Output |
| 1 | 4 2 5 3 4 2 | 7 |
| 2 | 3 5 7 1 4 | 7 |
Bài 4. Người trùng tên gần nhất
Có n bạn xếp thành hàng, bạn thứ i có số áo a[i]. Với mỗi bạn, hãy cho biết khoảng cách (hiệu số thứ tự) đến bạn gần nhất đứng phía trước có cùng số áo.
| Đầ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ố thứ i là khoảng cách đến bạn trùng số áo gần nhất phía trước, hoặc -1 nếu không có. | |
| Test | Input | Output |
| 1 | 6 5 3 5 5 3 9 | -1 -1 2 1 3 -1 |
| 2 | 3 1 2 3 | -1 -1 -1 |
Bài 5. Mật khẩu lớn hơn
Hổ viết một mật khẩu gồm n chữ số. Hổ muốn biết có bao nhiêu mật khẩu khác nhau có thể tạo bằng cách sắp xếp lại các chữ số của mật khẩu đó (chữ số 0 được phép đứng đầu), mà lớn hơn mật khẩu của Hổ theo thứ tự từ điển.
| Đầu vào | Một dòng duy nhất là xâu s gồm các chữ số, dài từ 1 đến 8 ký tự. | |
|---|---|---|
| Đầu ra | Số mật khẩu khác nhau lớn hơn s. | |
| Test | Input | Output |
| 1 | 123 | 5 |
| 2 | 3221 | 0 |
| 3 | 9 | 0 |
Bài 6. Túi đồ của Gấu Po
Gấu Po có n món đồ, món thứ i nặng w[i] và có giá trị v[i]. Túi của Gấu Po chứa được tổng khối lượng không quá W. Hỏi tổng giá trị lớn nhất của các món có thể mang đi?
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 20; 1 ≤ W ≤ 109). n dòng tiếp theo, mỗi dòng gồm hai số nguyên w[i], v[i] (1 ≤ w[i] ≤ 108; 1 ≤ v[i] ≤ 106). | |
|---|---|---|
| Đầu ra | Tổng giá trị lớn nhất. | |
| Test | Input | Output |
| 1 | 3 50 10 60 20 100 30 120 | 220 |
| 2 | 2 5 6 10 7 20 | 0 |
Bài 7. Thống kê hòn đảo
Bản đồ của Thỏ là lưới n × m gồm ô '#' (đất) và ô '.' (biển). Các ô đất kề cạnh nhau tạo thành một hòn đảo. Hãy thống kê: với mỗi cỡ đảo (số ô) có bao nhiêu hòn đảo?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 100). n dòng tiếp theo, mỗi dòng gồm m ký tự '.' hoặc '#'. | |
|---|---|---|
| Đầu ra | Mỗi dòng gồm hai số: cỡ đảo và số hòn đảo có cỡ đó, theo thứ tự tăng dần của cỡ đảo. Nếu không có đảo thì không in gì. | |
| Test | Input | Output |
| 1 | 4 5 ##..# #...# ..#.. #.### | 1 1 2 1 3 1 4 1 |
| 2 | 2 3 #.# ...# | 1 2 |
Bài 8. Tổng k điểm cao nhất
Giải chạy của rừng xanh nhận điểm của các vận động viên theo thứ tự thời gian. Sau khi nhận mỗi điểm mới, ban tổ chức muốn biết tổng của k điểm cao nhất trong số các điểm đã nhận (nếu chưa đủ k điểm thì lấy tổng của tất cả điểm đã có).
| Đầ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 số cách nhau một dấu cách, số thứ t là tổng k điểm cao nhất trong t điểm đầu tiên. | |
| Test | Input | Output |
| 1 | 5 2 4 9 1 7 8 | 4 13 13 16 17 |
| 2 | 3 5 2 2 2 | 2 4 6 |
Bài 9. Xóa nhóm giống nhau
Hổ có một xâu chữ cái thường. Mỗi lượt, nếu trong xâu có k chữ cái giống nhau đứng liên tiếp thì Hổ xóa cả k chữ cái đó, phần còn lại được nối liền. Hổ làm đến khi không xóa được nữa. Hãy cho biết xâu cuối cùng.
| Đầu vào | Dòng 1: số nguyên k (2 ≤ k ≤ 105). Dòng 2: xâu s gồm chữ cái thường, dài từ 1 đến 105 ký tự. | |
|---|---|---|
| Đầu ra | Xâu sau khi xóa, hoặc in EMPTY nếu xâu rỗng. | |
| Test | Input | Output |
| 1 | 3 abbbaac | c |
| 2 | 2 abbaca | ca |
| 3 | 3 aabbbaa | a |
Bài tập tự luyện
Bài 1. Phiếu bầu quá bán
Lớp có n phiếu bầu, mỗi phiếu ghi tên một bạn. Một bạn thắng cử nếu nhận được nhiều hơn một nửa số phiếu (tức là hơn n / 2 phiếu). Hãy cho biết bạn thắng cử.
| Đầ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 và dài không quá 20 ký tự. | |
|---|---|---|
| Đầu ra | Tên bạn thắng cử, hoặc in NONE nếu không có ai. | |
| Test | Input | Output |
| 1 | 5 an binh an cuc an | an |
| 2 | 4 an binh an binh | NONE |
Bài 2. Đoạn dài nhất chia hết
Cho n số nguyên và số m. Hãy tìm đoạn liên tiếp dài nhất có tổng chia hết cho m.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n ≤ 105; 1 ≤ m ≤ 109). Dòng 2: n số nguyên a[i] (|a[i]| ≤ 109). | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của đoạn có tổng chia hết cho m, hoặc 0 nếu không có đoạn nào. | |
| Test | Input | Output |
| 1 | 5 3 1 2 3 4 5 | 5 |
| 2 | 3 5 1 1 1 | 0 |
Bài 3. Người thấp hơn bên trái
Gấu Po cho n bạn đứng thành một hàng ngang, bạn thứ i cao a[i]. Mỗi bạn nhìn sang bên trái và muốn biết bạn gần nhất đứng bên trái và thấp hơn mình là bạn cao bao nhiêu.
| Đầ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ố thứ i là chiều cao của bạn gần nhất bên trái và thấp hơn bạn i, hoặc -1 nếu không có. | |
| Test | Input | Output |
| 1 | 6 4 5 2 25 7 8 | -1 4 -1 2 2 7 |
| 2 | 3 3 2 1 | -1 -1 -1 |
Bài 4. Số lớn hơn kế tiếp
Thỏ viết một số rất dài bằng các chữ số. Hãy tìm số nhỏ nhất lớn hơn số của Thỏ mà được tạo bằng cách sắp xếp lại đúng các chữ số đó. Nếu không có thì in -1.
| Đầu vào | Một dòng duy nhất là xâu s gồm các chữ số, không bắt đầu bằng 0, dài từ 1 đến 105 ký tự. | |
|---|---|---|
| Đầu ra | Số tìm được, hoặc -1. | |
| Test | Input | Output |
| 1 | 123 | 132 |
| 2 | 321 | -1 |
| 3 | 115 | 151 |
Bài 5. Chia kẹo theo gói
Thỏ có n viên kẹo. Thỏ chia kẹo thành các gói theo thứ tự, mỗi gói có số viên thuộc một tập cho trước gồm m số. Hai cách chia khác nhau nếu thứ tự các gói khác nhau (chia 1 rồi 2 khác chia 2 rồi 1). Hỏi có bao nhiêu cách chia hết n viên kẹo?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n ≤ 20; 1 ≤ m ≤ 5). Dòng 2: m số nguyên khác nhau, mỗi số từ 1 đến 20 là số viên kẹo trong một gói. | |
|---|---|---|
| Đầu ra | Số cách chia. | |
| Test | Input | Output |
| 1 | 4 2 1 2 | 5 |
| 2 | 10 3 1 2 5 | 128 |
Bài 6. Ghép que diêm thành hình vuông
Gấu Po có n que diêm, que thứ i dài a[i]. Gấu Po muốn ghép tất cả các que (không bẻ gãy, mỗi que dùng đúng một lần) thành một hình vuông. Có làm được không?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 14). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 100). | |
|---|---|---|
| Đầu ra | In YES nếu ghép được, ngược lại in NO. | |
| Test | Input | Output |
| 1 | 5 1 1 2 2 2 | YES |
| 2 | 5 3 3 3 3 4 | NO |
Bài 7. Số lớn hơn hoặc bằng gần nhất trước đó
Hổ nhận lần lượt n số. Với mỗi số, hãy cho biết trong các số đã nhận trước đó, số nhỏ nhất mà không nhỏ hơn số hiện tại là số nào.
| Đầ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ố thứ i là số nhỏ nhất trong các số trước đó mà ≥ a[i], hoặc -1 nếu không có. | |
| Test | Input | Output |
| 1 | 6 5 3 8 5 9 1 | -1 5 -1 5 -1 3 |
| 2 | 3 4 3 2 | -1 4 3 |
Bài 8. Dãy ngoặc có độ sâu giới hạn
Hãy đếm số dãy ngoặc đúng gồm n dấu mở và n dấu đóng mà độ sâu lớn nhất (số dấu mở đang chưa đóng nhiều nhất tại một thời điểm) không vượt quá d.
| Đầu vào | Một dòng gồm hai số nguyên n, d (1 ≤ n ≤ 10; 1 ≤ d ≤ 10). | |
|---|---|---|
| Đầu ra | Số dãy ngoặc đúng thỏa mãn. | |
| Test | Input | Output |
| 1 | 3 2 | 4 |
| 2 | 4 1 | 1 |
Bài 9. Thử thách (không bắt buộc): Số nhỏ thứ k trong khung trượt
Hổ có n số và một khung kính che w số liên tiếp trượt từ trái sang phải. Với mỗi vị trí của khung, hãy cho biết số nhỏ thứ k trong khung (các số trùng vẫn tính là các vị trí khác nhau). (Gợi ý: dùng multiset, nhớ xóa đúng một thẻ khi số rời khung; dùng next(ms.begin(), k - 1) để tìm số nhỏ thứ k.)
| Đầu vào | Dòng 1: ba số nguyên n, w, k (1 ≤ k ≤ w ≤ n ≤ 3000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | n - w + 1 số cách nhau một dấu cách, số thứ t là số nhỏ thứ k trong khung bắt đầu ở vị trí t. | |
| Test | Input | Output |
| 1 | 6 3 2 4 1 7 3 9 2 | 4 3 7 3 |
| 2 | 3 3 3 5 1 5 | 5 |
-
Gợi ý chung: Trước khi viết code, hãy ghi ra ba điều: dạng bài (set, map, stack, queue, priority_queue, sinh kế tiếp hay quay lui), giới hạn n lớn nhất, 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 rỗng và lỗi end() nhanh nhất.