Chữa đề và nhận dạng dạng bài
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 90 phút
- Học trước
- Mini contest 4: Đề 1
- Chủ đề
- nhận dạng bàiquy hoạch độngtham lam
- Trạng thái
Kiến thức cơ bản
Thám tử chữa đề: năm bước cho mọi bài toán
Tuần này em không học thêm công cụ mới. Em đóng vai thám tử: nhìn một đề bài lạ, tìm manh mối trong đề rồi đoán xem phải dùng công cụ nào trong chiếc hộp dụng cụ 34 tuần của mình. Thám tử giỏi không lao vào viết code ngay, mà đi qua năm bước, mỗi bước chỉ mất vài phút.
| Bước | Thám tử làm gì | Câu hỏi tự hỏi |
|---|---|---|
| 1. Đọc kỹ | Đọc đề hai lần, gạch chân dữ liệu vào, dữ liệu ra và yêu cầu. | Đề bắt mình đếm, tìm lớn nhất, liệt kê hay chỉ trả lời có hoặc không? |
| 2. Soi giới hạn | Tìm n, q và giá trị lớn nhất của dữ liệu. | n lớn nhất là bao nhiêu? Cách định làm cần khoảng bao nhiêu phép tính? |
| 3. Đoán công cụ | Đối chiếu với bảng dấu hiệu ở dưới. | Đề này giống bài nào mình từng làm? |
| 4. Chạy tay | Chạy thử cách làm trên test mẫu bằng giấy bút. | Ra đúng kết quả mẫu chưa? Nếu định dùng tham lam, có phản ví dụ nhỏ nào không? |
| 5. Viết và thử | Viết code, rồi tự nghĩ thêm test nhỏ nhất và test lớn nhất. | Có tràn int không? Có lệch chỉ số một đơn vị không? n = 1 thì sao? |
Bảng dấu hiệu: đọc đề, đoán công cụ
Mỗi cụm từ trong đề là một manh mối. Em tìm cụm từ giống nhất ở cột trái, rồi nhìn sang cột giữa để biết nên nghĩ tới công cụ nào.
| Dấu hiệu trong đề | Công cụ nên nghĩ tới | Tuần |
|---|---|---|
| Rất nhiều câu hỏi “tổng các số từ vị trí l đến r” | Mảng cộng dồn | 13 |
| Rất nhiều lần “cộng thêm cho đoạn từ l đến r”, cuối cùng mới hỏi | Mảng hiệu | 14 |
| Dãy đã sắp xếp, tìm cặp có tổng K, hoặc gộp hai dãy | Hai con trỏ | 15 |
| Đoạn liên tiếp dài nhất hoặc ngắn nhất thỏa điều kiện; tổng k số liên tiếp | Cửa sổ trượt | 16 |
| “Có hay không”, đếm số phần tử ≤ x trên dãy đã sắp; tìm giá trị nhỏ nhất đủ để điều kiện đúng | Tìm kiếm nhị phân, lower_bound, upper_bound, nhị phân theo đáp án | 12 |
| Xếp hạng theo nhiều tiêu chí, nhớ vị trí ban đầu | sort với pair và comparator | 10–11 |
| Bỏ trùng, hỏi “đã có chưa”, tìm số gần nhất | set | 19–20 |
| Đếm số lần xuất hiện, gắn nhãn (tên, chuỗi) cho dữ liệu | map | 19–20 |
| Dấu ngoặc, hoàn tác, phần tử lớn hơn gần nhất | stack | 21 |
| Xếp hàng, mô phỏng vòng tròn | queue | 21 |
| Liên tục lấy số lớn nhất hoặc nhỏ nhất sau mỗi lần thêm số | priority_queue | 22 |
| Liệt kê mọi hoán vị hoặc xâu theo thứ tự, tìm cấu hình đứng ngay sau | Sinh kế tiếp | 23 |
| n rất nhỏ (n ≤ 20), thử mọi cách chọn có điều kiện, đếm số nghiệm | Quay lui | 24–25 |
| Ước, bội, ƯCLN, số nguyên tố, đếm trong khoảng lớn | Số học, sàng | 4–5 |
| Lưới ô vuông, đếm các vùng liền nhau | Mảng 2 chiều, đệ quy (loang) | 6–7 |
| “Ít nhất”, “nhiều nhất”, sắp xếp rồi chọn dần, mỗi lần chọn cái tốt nhất lúc này | Tham lam | 28–29 |
| “Có bao nhiêu cách”, “nhỏ nhất”, “lớn nhất” mà kết quả bài to được xây từ kết quả các bài nhỏ hơn | Quy hoạch động | 30–33 |
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 để biết cách giải nào đủ nhanh. Đây là manh mối mạnh nhất, vì có khi đề không nói gì về thuật toán nhưng giới hạn đã nói thay.
| Giới hạn | Cách làm có thể | Ví dụ |
|---|---|---|
| n ≤ 10 | Thử mọi hoán vị (n! khoảng 3,6 triệu) | Xếp chỗ ngồi |
| n ≤ 20 | Thử mọi tập con (2n khoảng một triệu), quay lui | Tập con có tổng S |
| n ≤ 1000 | Hai vòng for lồng nhau (n2), hoặc DP bảng hai chiều | Dãy tăng dài nhất, xâu chung dài nhất |
| n ≤ 100 và sức chứa ≤ 104 | DP bảng n × sức chứa (khoảng 106 phép) | Túi quà, đổi tiền |
| n ≤ 105 | n log n: sort, set, map, priority_queue, nhị phân; hoặc n phép: cộng dồn, hai con trỏ, stack, DP một chiều | Cặp có tổng K, đoạn tổng lớn nhất |
| n ≤ 106 | Chỉ còn cách làm khoảng n phép; sàng Eratosthenes | Liệt kê số nguyên tố |
| Giá trị tới 1018 | Không duyệt từng số; dùng công thức, ƯCLN hoặc nhị phân theo đáp án | Tìm đáp án nhỏ nhất thỏa điều kiện |
Tham lam hay quy hoạch động?
Hai dạng này hay bị nhầm vì cùng hỏi “ít nhất” hoặc “nhiều nhất”. Em dùng ba câu hỏi sau để phân biệt.
- Tham lam: mỗi lần chọn cái tốt nhất lúc này, có chắc sau này không phải hối hận không? Em hãy thử với ba bốn số nhỏ bằng tay. Chỉ cần một phản ví dụ là bỏ ý tưởng tham lam.
- Quy hoạch động: bài to có xây được từ các bài nhỏ giống hệt, và số bài nhỏ không quá nhiều (n2 hoặc n × sức chứa) không? Nếu có, hãy lập bảng dp.
- Quay lui: n chỉ cỡ 10 đến 20 và đề cần liệt kê hoặc đếm mọi cách? Khi đó thử hết là đủ nhanh và đơn giản nhất.
Ví dụ: tờ tiền 1, 2, 5, 10 thì lấy tờ to nhất còn vừa luôn đúng (tham lam). Nhưng xu 1, 3, 4 và cần trả 6: tham lam lấy 4 + 1 + 1 hết 3 xu, còn cách đúng là 3 + 3 chỉ hết 2 xu. Gặp đổi tiền kiểu này phải dùng quy hoạch động.
Khuôn viết nhanh
// Cộng dồn: tổng đoạn [l, r] = pre[r] - pre[l - 1]
for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
// Mảng hiệu: tăng đoạn [l, r] thêm 1, cuối cùng cộng dồn d
d[l]++; d[r + 1]--;
// Hai con trỏ / cửa sổ trượt: r đi tới, l bị đẩy lên khi vi phạm
int l = 0;
for (int r = 0; r < n; r++) {
// thêm a[r] vào cửa sổ
while (/* cửa sổ vi phạm */) { /* bỏ a[l] ra */ l++; }
best = max(best, r - l + 1);
}
// Nhị phân theo đáp án: tìm giá trị nhỏ nhất mà ok(mid) đúng
long long l = 0, r = maxVal;
while (l < r) {
long long mid = (l + r) / 2;
if (ok(mid)) r = mid; else l = mid + 1;
}
// Tham lam: sắp xếp theo tiêu chí rồi chọn lần lượt
sort(v.begin(), v.end());
for (auto& x : v) if (x còn hợp lệ) { chọn x; }
// DP một chiều: dp[i] = kết quả tốt nhất của bài nhỏ thứ i
dp[0] = ...; // trường hợp cơ sở
for (int i = 1; i <= n; i++) dp[i] = ... dp[i - 1] ...;
// Túi quà (mỗi món dùng một lần): duyệt sức chứa từ lớn xuống nhỏ
for (int c = W; c >= w; c--) dp[c] = max(dp[c], dp[c - w] + v);
Chữa đề: ba kiểu lỗi và thủ phạm quen thuộc
Chữa đề nghĩa là tìm ra vì sao bài làm chưa đủ điểm, rồi ghi lại để lần sau không vấp nữa. Em nhìn triệu chứng để đoán thủ phạm.
| Triệu chứng | Thủ phạm hay gặp | Cách kiểm tra |
|---|---|---|
| Sai ngay ở test mẫu | Hiểu sai đề; ý tưởng sai (tham lam sai); công thức hoặc trường hợp cơ sở của DP sai | Chạy tay test mẫu từng bước; thử tìm phản ví dụ nhỏ |
| Đúng test nhỏ, sai test lớn | Tràn int; lệch chỉ số một đơn vị; quên đặt lại biến; mp[k] vô tình tạo khóa mới | Đổi int sang long long; thử n = 1 và n = 2; in kết quả trung gian |
| Quá thời gian | Hai vòng for với n = 105; đệ quy tính lại việc cũ (Fibonacci không nhớ); xóa giữa vector | Đếm số phép tính; tìm vòng lặp lồng; nghĩ tới cộng dồn, hai con trỏ, dp |
| Chương trình dừng đột ngột | a[-1] hoặc a[n]; top() khi stack rỗng; *it khi it == end(); đệ quy không có điểm dừng | Kiểm tra chỉ số đầu và cuối; kiểm tra empty() trước; xem lại điều kiện dừng |
Sổ thám tử: ghi lại lỗi của contest 4
Sau contest 4, em chép bảng này vào vở và điền cho mỗi bài chưa được trọn điểm. Hai dòng đầu là ví dụ. Mục “Lần sau” quan trọng nhất, vì nó là lời dặn của em cho chính em.
| Bài | Em đã nghĩ là | Dạng đúng là | Lỗi thuộc loại | Lần sau em sẽ |
|---|---|---|---|---|
| Đổi xu 1, 3, 4 | Tham lam | Quy hoạch động | Ý tưởng sai | Thử phản ví dụ nhỏ trước khi chọn tham lam |
| Đoạn tổng lớn nhất | Hai vòng for | DP một chiều | Quá thời gian | Nhìn n = 105 rồi mới chọn cách làm |
Cách luyện tập tuần này
Tuần này là tuần “nói trước, code sau”. Với mỗi đề, em hãy nói to ba điều: bài thuộc dạng nào, vì sao em nghĩ vậy, và cách làm cần khoảng bao nhiêu phép tính. Nói được rồi mới viết code. Hai trò chơi nhận dạng chưa cần viết code, đáp án ở cuối tài liệu, em chỉ xem sau khi đã tự điền xong.
Luyện tập
Bài 1. Thám tử nhận dạng: tham lam, quy hoạch động hay quay lui?
Với mỗi đề ngắn dưới đây, em ghi thuật toán sẽ dùng và một câu giải thích vì sao. Chưa cần viết code.
| Đề | Thuật toán | Vì sao |
|---|---|---|
| 1. Gấu Po trả tiền bằng các tờ 1000, 2000, 5000, 10000, 20000, 50000 đồng, cần trả đúng V đồng bằng ít tờ nhất. | ||
| 2. Thỏ có các đồng xu 1, 3, 4 và cần trả đúng 6 đồng bằng ít xu nhất. | ||
| 3. Hổ có n cuộc họp, mỗi cuộc có giờ bắt đầu và giờ kết thúc. Chọn nhiều cuộc nhất sao cho không cuộc nào chồng nhau. | ||
| 4. Thang có n ≤ 106 bậc, mỗi bước lên 1 hoặc 2 bậc. Đếm số cách lên hết thang. | ||
| 5. Có 18 viên đá nặng khác nhau, cần chia thành hai đống sao cho hiệu cân nặng hai đống nhỏ nhất. | ||
| 6. Có 100 món quà (cân nặng, giá trị), túi chịu được tối đa 104 kg, mỗi món lấy hoặc không. Tìm tổng giá trị lớn nhất. | ||
| 7. Hai xâu, mỗi xâu dài 1000 ký tự. Tìm độ dài lớn nhất của xâu con chung (không cần liền nhau). | ||
| 8. Có 8 bạn xếp vào 8 ghế, một số cặp bạn không được ngồi cạnh nhau. Đếm số cách xếp. | ||
| 9. Có n ≤ 105 bài tập, bài i mất t[i] phút, Thỏ có T phút. Làm được nhiều bài nhất là bao nhiêu? | ||
| 10. Cho n ≤ 105 số (có số âm). Tìm đoạn liên tiếp có tổng lớn nhất. |
Bài 2. Rừng số nguyên tố
Thỏ trồng một khu rừng có 106 cây, cây thứ i mang số hiệu i. Cây có số hiệu là số nguyên tố được gọi là “cây thần”. Gấu Po hỏi Thỏ q câu: từ cây l đến cây r có bao nhiêu cây thầ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 | Với mỗi câu hỏi, in ra một dòng là số cây thần tìm được. | |
| Test | Input | Output |
| 1 | 3 1 10 11 20 90 100 | 4 4 1 |
| 2 | 2 1 1 2 2 | 0 1 |
Bài 3. Tưới vườn hoa
Vườn của Hổ có n luống hoa đánh số từ 1 đến n. Hổ tưới m lần, mỗi lần tưới các luống từ l đến r, mỗi luống thêm đúng 1 lít nước. Cuối ngày, Hổ muốn biết mỗi luống nhận được bao nhiêu lít nước.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n ≤ 105; 0 ≤ m ≤ 105). m dòng tiếp theo: mỗi dòng hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | n số nguyên cách nhau một dấu cách, số thứ i là số lít nước của luống i. | |
| Test | Input | Output |
| 1 | 5 3 1 3 2 5 2 3 | 1 3 3 1 1 |
| 2 | 4 0 | 0 0 0 0 |
Bài 4. Cân thuyền qua sông
Có n bạn nhỏ đứng chờ qua sông, bạn thứ i nặng a[i] ki-lô-gam. Mỗi chiếc thuyền chở tối đa hai bạn và tổng cân nặng không vượt quá W. Mỗi bạn đều nhẹ hơn hoặc bằng W. Gấu Po cần ít thuyền nhất để chở hết các bạn.
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 105; 1 ≤ W ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ W). | |
|---|---|---|
| Đầu ra | Số thuyền ít nhất. | |
| Test | Input | Output |
| 1 | 4 10 3 8 5 6 | 3 |
| 2 | 5 100 50 50 50 50 50 | 3 |
Bài 5. Đoạn đường ít màu
Thỏ lát một con đường bằng n viên gạch, viên thứ i có màu a[i]. Thỏ muốn tìm đoạn gạch liên tiếp dài nhất mà chỉ dùng tối đa hai 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 | Độ dài lớn nhất của đoạn gạch tìm được. | |
| Test | Input | Output |
| 1 | 8 1 2 1 3 3 3 2 3 | 5 |
| 2 | 5 7 7 7 7 7 | 5 |
Bài 6. Ngày ấm hơn
Gấu Po ghi lại nhiệt độ của n ngày liên tiếp. Với mỗi ngày i, Gấu Po muốn biết phải chờ thêm bao nhiêu ngày nữa thì gặp một ngày ấm hơn hẳn ngày i. Nếu sau đó không có ngày nào ấm hơn thì ghi 0.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên t[i] (1 ≤ t[i] ≤ 104). | |
|---|---|---|
| Đầu ra | n số nguyên cách nhau một dấu cách, số thứ i là số ngày phải chờ. | |
| Test | Input | Output |
| 1 | 8 73 74 75 71 69 72 76 73 | 1 1 4 2 1 1 0 0 |
| 2 | 3 30 20 10 | 0 0 0 |
Bài 7. Ghép dây thừng
Hổ có n sợi dây, sợi thứ i dài d[i]. Mỗi lần Hổ nối hai sợi bất kỳ thành một sợi dài bằng tổng hai sợi, và công sức bỏ ra đúng bằng chiều dài sợi mới. Hổ nối cho đến khi còn đúng một sợi. Tổng công sức ít nhất là bao nhiêu?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên d[i] (1 ≤ d[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng công sức ít nhất (có thể rất lớn, nhớ dùng long long). | |
| Test | Input | Output |
| 1 | 4 4 3 2 6 | 29 |
| 2 | 1 7 | 0 |
Bài 8. Chia quà theo ý Thỏ
Thỏ có n món quà, món thứ i có giá trị a[i]. Thỏ muốn chọn một số món sao cho tổng giá trị đúng bằng S. Hai cách chọn khác nhau khi có ít nhất một món được chọn ở cách này mà không được chọn ở cách kia (hai món cùng giá trị vẫn là hai món khác nhau). Hãy đếm số cách chọn.
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 20; 1 ≤ S ≤ 1010). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cách chọn. | |
| Test | Input | Output |
| 1 | 5 10 2 3 5 7 8 | 3 |
| 2 | 3 100 1 2 3 | 0 |
Bài 9. Cầu thang gãy
Cầu thang nhà Gấu Po có n bậc, Gấu Po đứng dưới đất (bậc 0). Mỗi bước, Gấu Po leo lên 1 hoặc 2 bậc. Có m bậc bị hỏng, Gấu Po không được đặt chân lên bậc hỏng nhưng được phép nhảy qua. Hãy đếm số cách leo lên đến bậc n. Vì số cách có thể rất lớn, chỉ in phần dư khi chia cho 109 + 7.
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n ≤ 106; 0 ≤ m ≤ n). Dòng 2 (chỉ có khi m > 0): m số nguyên đôi một khác nhau là các bậc hỏng (từ 1 đến n). | |
|---|---|---|
| Đầu ra | Số cách leo, lấy phần dư khi chia cho 109 + 7. | |
| Test | Input | Output |
| 1 | 5 1 3 | 2 |
| 2 | 4 0 | 5 |
Bài 10. Kho báu trên lưới
Bản đồ của Thỏ là lưới n × m, ô ở hàng i cột j chứa a[i][j] đồng vàng. Thỏ xuất phát ở ô góc trên bên trái, mỗi bước chỉ được đi sang phải hoặc đi xuống dưới, và dừng ở ô góc dưới bên phải. Thỏ nhặt hết vàng ở mọi ô đi qua, kể cả ô đầu và ô cuối. Hãy tìm số đồng vàng nhiều nhất Thỏ có thể nhặt.
| Đầ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] ≤ 1000). | |
|---|---|---|
| Đầu ra | Số đồng vàng nhiều nhất. | |
| Test | Input | Output |
| 1 | 3 3 1 3 1 1 5 1 4 2 1 | 12 |
| 2 | 1 4 2 0 5 1 | 8 |
Bài tập tự luyện
Bài 1. Thám tử nhận dạng toàn lộ trình
Trò chơi này đi qua gần hết các tuần đã học. Với mỗi đề, em điền công cụ phù hợp và số phép tính ước lượng. Chưa cần viết code.
| Đề | 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. Cho dãy đã sắp xếp tăng dần gồm n = 105 số. Tìm hai số có tổng đúng bằng K. | ||
| 4. Cho doanh thu của n ngày. Tìm tổng lớn nhất của k ngày liên tiếp. | ||
| 5. Đếm xem trong n = 105 từ có bao nhiêu từ khác nhau. | ||
| 6. Tìm từ xuất hiện nhiều lần nhất trong n = 105 từ. | ||
| 7. Kiểm tra một dãy gồm các dấu ( và ) dài 105 có phải dãy ngoặc đúng hay không. | ||
| 8. Có n = 105 thanh gỗ. Mỗi bước nối hai thanh ngắn nhất thành một thanh mới, cho đến khi còn một thanh. | ||
| 9. Liệt kê mọi xâu nhị phân độ dài n ≤ 12 không có hai số 1 đứng cạnh nhau. | ||
| 10. Bản đồ lưới 50 × 50 gồm ô đất và ô biển. Đếm số hòn đảo (vùng đất liền nhau). | ||
| 11. Tìm tốc độ ăn chuối nhỏ nhất (tối đa 109 chuối mỗi giờ) để ăn hết n = 105 nải chuối trong h giờ. | ||
| 12. Liệt kê mọi số nguyên tố không vượt quá 106. | ||
| 13. Xếp hạng n = 105 bạn theo điểm giảm dần, bằng điểm thì xếp theo tên. |
Bài 2. Cặp bạn thân
Lớp của Gấu Po có n bạn, bạn thứ i đeo số áo a[i]. Hai bạn i và j (i < j) là “cặp bạn thân” nếu a[i] + a[j] đúng bằng K. Hãy đếm số cặp bạn thân.
| Đầu vào | Dòng 1: hai số nguyên n, K (1 ≤ n ≤ 105; 1 ≤ K ≤ 2·109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số cặp bạn thân (có thể rất lớn, nhớ dùng long long). | |
| Test | Input | Output |
| 1 | 6 10 3 7 5 5 5 7 | 5 |
| 2 | 3 4 1 1 1 | 0 |
Bài 3. Xếp lịch họp
Rừng xanh có một phòng họp duy nhất. Có n cuộc họp, cuộc thứ i bắt đầu lúc s và kết thúc lúc e. Hai cuộc họp xếp được chung phòng nếu cuộc này kết thúc không muộn hơn lúc cuộc kia bắt đầu (kết thúc đúng lúc thì vẫn được). Hổ muốn xếp được nhiều cuộc họp nhất.
| Đầ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ố nguyên s, e (0 ≤ s < e ≤ 109). | |
|---|---|---|
| Đầu ra | Số cuộc họp nhiều nhất xếp được. | |
| Test | Input | Output |
| 1 | 5 1 4 3 5 0 6 5 7 8 9 | 3 |
| 2 | 3 1 2 2 3 3 4 | 3 |
Bài 4. Đổi tiền khó tính
Thỏ có k loại đồng xu, mỗi loại dùng bao nhiêu lần cũng được. Thỏ cần trả đúng V đồng bằng số xu ít nhất. Em hãy thử xem: với xu 1, 3, 4 và V = 6, cách “lấy xu to nhất còn vừa” cho kết quả sai. Nếu không thể trả đúng V thì in -1.
| Đầu vào | Dòng 1: hai số nguyên k, V (1 ≤ k ≤ 100; 1 ≤ V ≤ 104). Dòng 2: k mệnh giá khác nhau (1 ≤ mệnh giá ≤ 104). | |
|---|---|---|
| Đầu ra | Số xu ít nhất, hoặc -1 nếu không trả được. | |
| Test | Input | Output |
| 1 | 3 6 1 3 4 | 2 |
| 2 | 2 7 2 4 | -1 |
Bài 5. Sơn tường
Hàng rào có n bức tường liên tiếp, bức thứ i cần a[i] giờ để sơn. Gấu Po thuê k thợ, mỗi thợ sơn một đoạn các bức tường liền nhau, và mọi bức tường đều phải được sơn. Các thợ làm cùng lúc nên thời gian hoàn thành bằng thời gian của thợ làm lâu nhất. Hãy chia việc để thời gian hoàn thành là ít 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] ≤ 104). | |
|---|---|---|
| Đầu ra | Thời gian hoàn thành ít nhất. | |
| Test | Input | Output |
| 1 | 5 2 1 2 3 4 5 | 9 |
| 2 | 3 3 5 5 5 | 5 |
Bài 6. Dãy tăng dài nhất
Thỏ viết một dãy gồm n số. Thỏ muốn xóa bớt vài số (có thể không xóa) để các số còn lại, giữ nguyên thứ tự, tăng chặt dần từ trái sang phải. Hỏi Thỏ giữ lại được nhiều nhất bao nhiêu số?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 1000). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của dãy con tăng chặt. | |
| Test | Input | Output |
| 1 | 8 10 9 2 5 3 7 101 18 | 4 |
| 2 | 4 5 5 5 5 | 1 |
Bài 7. Túi quà
Hổ có n món quà, món thứ i nặng w[i] ki-lô-gam và có giá trị v[i]. Túi chịu được tối đa W ki-lô-gam, mỗi món chỉ được lấy một lần. Hãy chọn các món để tổng giá trị lớn nhất.
| Đầu vào | Dòng 1: hai số nguyên n, W (1 ≤ n ≤ 100; 1 ≤ W ≤ 104). n dòng tiếp theo: mỗi dòng hai số nguyên w[i], v[i] (1 ≤ w[i] ≤ 104; 1 ≤ v[i] ≤ 106). | |
|---|---|---|
| Đầu ra | Tổng giá trị lớn nhất. | |
| Test | Input | Output |
| 1 | 4 10 5 10 4 40 6 30 3 50 | 90 |
| 2 | 2 5 6 100 7 200 | 0 |
Bài 8. Chuỗi ngày lãi nhất
Cửa hàng của Gấu Po có lãi hoặc lỗ mỗi ngày, ngày thứ i là a[i] (số âm nghĩa là lỗ). Gấu Po muốn chọn một đoạn gồm các ngày liên tiếp (ít nhất một ngày) để tổng lãi lớn nhất.
| Đầ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 | Tổng lớn nhất của một đoạn liên tiếp (nhớ dùng long long). | |
| Test | Input | Output |
| 1 | 9 -2 1 -3 4 -1 2 1 -5 4 | 6 |
| 2 | 3 -5 -2 -9 | -2 |
Bài 9. Xâu chung dài nhất
Thỏ và Hổ mỗi bạn có một xâu chỉ gồm chữ cái thường. Hai bạn muốn tìm xâu con chung dài nhất. Xâu con có được bằng cách xóa một số ký tự (có thể không xóa), giữ nguyên thứ tự các ký tự còn lại.
| Đầu vào | Dòng 1: xâu s (độ dài từ 1 đến 1000). Dòng 2: xâu t (độ dài từ 1 đến 1000). | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của xâu con chung. | |
| Test | Input | Output |
| 1 | abcde ace | 3 |
| 2 | abc def | 0 |
Bài 10. Thử thách (không bắt buộc): Đoạn chia hết
Gấu Po viết n số nguyên dương trên một hàng. Em hãy đếm xem có bao nhiêu đoạn liên tiếp mà tổng các số trong đoạn chia hết cho m. (Gợi ý: nhìn số dư của các tổng cộng dồn khi chia cho m, hai vị trí có cùng số dư thì đoạn nằm giữa chúng có tổng chia hết cho m. Dùng map để đế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] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số đoạn có tổng chia hết cho m (nhớ dùng long long). | |
| Test | Input | Output |
| 1 | 5 3 1 2 3 4 5 | 7 |
| 2 | 3 5 1 1 1 | 0 |
-
Gợi ý chung: Trước khi viết code, hãy ghi ra ba điều: dạng bài (cộng dồn, hai con trỏ, set, map, stack, priority_queue, quay lui, tham lam hay quy hoạch động), 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 giải được bằng hai cách, hãy chọn cách đơn giản hơn mà vẫn đủ 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 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 lệch chỉ số nhanh nhất.
Đáp án trò chơi nhận dạng
Thám tử nhận dạng: tham lam, quy hoạch động hay quay lui?
| Đề | Thuật toán | Vì sao |
|---|---|---|
| 1 | Tham lam | Với các tờ tiền này, lấy tờ to nhất còn vừa luôn cho kết quả ít tờ nhất. |
| 2 | Quy hoạch động | Tham lam lấy 4 + 1 + 1 (3 xu), còn cách đúng là 3 + 3 (2 xu): đã có phản ví dụ. |
| 3 | Tham lam | Sắp xếp theo giờ kết thúc, luôn chọn cuộc họp kết thúc sớm nhất còn xếp được. |
| 4 | Quy hoạch động | dp[i] = dp[i - 1] + dp[i - 2], chỉ cần khoảng n phép tính. |
| 5 | Quay lui (thử mọi tập con) | n = 18 nhỏ, 218 khoảng 262 nghìn cách chia, thử hết vẫn rất nhanh. |
| 6 | Quy hoạch động (túi quà) | Cần lập bảng n × sức chứa khoảng 106; chọn theo giá trị trên cân nặng có thể sai. |
| 7 | Quy hoạch động (xâu chung dài nhất) | Bảng hai chiều 1000 × 1000 khoảng 106 phép. |
| 8 | Quay lui (hoặc thử mọi hoán vị) | 8! = 40320 cách xếp, kiểm tra điều kiện từng cách. |
| 9 | Tham lam | Sắp xếp t[i] tăng dần rồi làm bài ngắn trước, n log n. |
| 10 | Quy hoạch động (một chiều) | best[i] = max(a[i], best[i - 1] + a[i]), khoảng n phép; hai vòng for sẽ quá thời gian. |
Thám tử nhận dạng toàn lộ trình
| Đề | Dạng bài | Độ phức tạp |
|---|---|---|
| 1 | Cộng dồn | n + q |
| 2 | Mảng hiệu | n + m |
| 3 | Hai con trỏ từ hai đầu | n |
| 4 | Cửa sổ trượt cố định (độ dài k) | n |
| 5 | set | n log n |
| 6 | map | n log n |
| 7 | stack | n |
| 8 | priority_queue (lấy hai số nhỏ nhất) | n log n |
| 9 | Quay lui (hoặc sinh kế tiếp) | Không quá 212 xâu |
| 10 | Loang bằng đệ quy trên mảng 2 chiều | n × m |
| 11 | Nhị phân theo đáp án | n log(109) |
| 12 | Sàng Eratosthenes | n log log n |
| 13 | sort với pair và comparator | n log n |