Giai đoạn 2 – Kỹ năng thi
Mục tiêu giai đoạn: HS viết code gọn bằng hàm, dùng thành thạo sắp xếp, dict/set, mảng cộng dồn, sàng nguyên tố; biết ước lượng thời gian chạy và đọc/ghi file đúng thể lệ.
Cuối giai đoạn: giải chắc bài 1–2 của đề thi, lấy điểm từng phần bài 3.
Mỗi buổi giữ cấu trúc 90 phút như Giai đoạn 1 (khởi động – kiến thức – luyện tập – tổng kết).
Bảng tiến độ
| Buổi | Chủ đề | Nội dung chính | Bài tập gợi ý |
|---|---|---|---|
| 13 | Hàm | def, tham số, return; so sánh "khối tự tạo" Scratch | Viết hàm la_nt(x), tong_cs(x), dao(x); đếm số "siêu nguyên tố" (nguyên tố và tổng chữ số cũng nguyên tố) |
| 14 | Luyện tập hàm | Chia bài toán lớn thành hàm nhỏ | Số đẹp (đối xứng + chia hết cho 3), số thân thiện, liệt kê số Armstrong ≤ n |
| 15 | Xâu nâng cao | find, in, replace, split, join, ord/chr, đếm tần suất ký tự | Đếm xâu con xuất hiện, nén xâu aaabcc → a3b1c2, giải nén, xâu đối xứng dài nhất (★★★ O(n²)) |
| 16 | List nâng cao | list comprehension, cắt list, insert, pop, del, list lồng nhau | Xóa phần tử trùng (giữ thứ tự), xoay dãy k vị trí, trộn hai dãy |
| 17 | Mảng 2 chiều | Đọc ma trận m×n, tổng hàng/cột, đường chéo, duyệt 8 ô kề | Ma trận đối xứng, hàng có tổng lớn nhất, dò mìn (đếm mìn quanh mỗi ô) |
| 18 | Sắp xếp | sort, sorted, reverse=True, key=, nhiều tiêu chí; tự viết sắp xếp nổi bọt để hiểu | Xếp HS theo điểm giảm, cùng điểm theo tên tăng; sắp chẵn trước lẻ sau |
| 19 | Ứng dụng sắp xếp | Sau khi sort: phần tử trùng đứng cạnh nhau, khoảng cách nhỏ nhất ở hai phần tử kề | Trung vị, đếm giá trị khác nhau, hiệu nhỏ nhất của hai phần tử, ghép cặp tổng lớn nhất |
| 20 | Đọc/ghi file & khung chương trình đi thi | open, sys.stdin, sys.stdout; đọc nhanh; khung chương trình chuẩn (xem dưới) | Làm lại 5 bài cũ theo kiểu đọc/ghi file TENBAI.INP/OUT, chấm bằng cham_bai.py --file |
| 21 | Độ phức tạp thuật toán | O(1), O(log n), O(n), O(n log n), O(n²); bảng giới hạn (xem dưới); đo thời gian, tự sinh test lớn | Cùng 1 bài (tổng 1..n, đếm ước, cặp tổng k) giải bằng 2 cách, đo thời gian với n lớn |
| 22 | set và dict | Kiểm tra tồn tại O(1), đếm tần suất bằng dict, Counter | Cặp tổng k với n = 10⁵ (dùng set), phần tử xuất hiện nhiều nhất, phần tử chung của 2 dãy |
| 23 | Luyện tập dict/set | Gom nhóm, đếm từ | Đếm số lần mỗi từ xuất hiện, nhóm các từ là đảo chữ của nhau, số cặp (i<j) có aᵢ = aⱼ |
| 24 | Mảng cộng dồn 1 chiều | s[i] = s[i-1] + a[i]; tổng đoạn [l, r] = s[r] - s[l-1] | q truy vấn tổng đoạn (n, q ≤ 10⁵); đoạn dài k có tổng lớn nhất; ★★★ đếm đoạn có tổng bằng k (cộng dồn + dict) |
| 25 | Cộng dồn 2 chiều & mảng hiệu | ★★ tổng hình chữ nhật con; mảng hiệu: cộng v vào đoạn [l, r] nhiều lần | Truy vấn tổng hình chữ nhật; q lần tăng lương cho đoạn nhân viên – in lương cuối |
| 26 | Sàng Eratosthenes & số học | Sàng đến 10⁶–10⁷; % với số lớn, pow(a, b, m) | Làm lại DEMNT (Đề 01) được 10/10; đếm nguyên tố trong q đoạn [a, b] (sàng + cộng dồn) |
| 27 | Ôn tập & kỹ năng gỡ lỗi | In giá trị trung gian, chạy từng bước (Thonny), viết lời giải "trâu" để đối chiếu | HS tự tìm lỗi trong 5 chương trình sai do giáo viên chuẩn bị |
| 28 | Thi thử lần 2 | 3–4 bài, 120 phút, đọc/ghi file | Ra đề theo mẫu de_thi_thu/De01 |
Kiến thức cốt lõi cần chốt
Buổi 13 – Hàm (so sánh với Scratch)
| Scratch | Python |
|---|---|
Tạo khối la_nguyen_to (x) | def la_nguyen_to(x): |
| Khối trả về giá trị | return True |
| Dùng khối | if la_nguyen_to(a[i]): |
def tong_cs(x): s = 0 while x > 0: s += x % 10 x //= 10 return s print(tong_cs(2026)) # 10
Buổi 18 – Sắp xếp nhiều tiêu chí
hs = [("An", 8), ("Binh", 9), ("Chi", 8)] hs.sort(key=lambda x: (-x[1], x[0])) # điểm giảm dần, cùng điểm thì tên tăng dần # [('Binh', 9), ('An', 8), ('Chi', 8)]
Buổi 20 – Khung chương trình chuẩn đi thi
import sys # Nếu đề yêu cầu đọc/ghi file: bỏ dấu # ở 2 dòng dưới, sửa TENBAI # sys.stdin = open("TENBAI.INP", "r") # sys.stdout = open("TENBAI.OUT", "w") input = sys.stdin.readline # đọc nhanh (nhớ .strip() khi đọc xâu) def main(): n = int(input()) a = list(map(int, input().split())) print(sum(a)) main()
Đọc toàn bộ dữ liệu một lần (nhanh nhất, khi dữ liệu rất lớn):
data = sys.stdin.read().split() n = int(data[0]) a = list(map(int, data[1:n + 1]))
Buổi 21 – Bảng ước lượng cho Python (giới hạn ~1 giây)
| n tối đa | Thuật toán chấp nhận được | Ví dụ |
|---|---|---|
| ≤ 10 | O(n!) | Thử mọi hoán vị |
| ≤ 20 | O(2ⁿ) | Thử mọi tập con |
| ≤ 100 | O(n³) | 3 vòng lặp lồng nhau |
| ≤ 2 000 – 3 000 | O(n²) | Duyệt mọi cặp |
| ≤ 10⁵ – 10⁶ | O(n log n) hoặc O(n) | Sắp xếp, cộng dồn, set/dict |
| ≤ 10¹² | O(√n) | Đếm ước, kiểm tra nguyên tố |
| ≤ 10¹⁸ | O(log n) hoặc O(1) | Công thức, tìm kiếm nhị phân, Euclid |
Thói quen bắt buộc từ buổi này: đọc giới hạn n → chọn thuật toán → mới bắt đầu code.
Buổi 22 – set/dict
# Có tồn tại cặp i < j mà a[i] + a[j] = k? O(n) thay vì O(n²) da_gap = set() co = False for x in a: if k - x in da_gap: co = True break da_gap.add(x) # Đếm tần suất dem = {} for x in a: dem[x] = dem.get(x, 0) + 1
Buổi 24 – Mảng cộng dồn
n, q = map(int, input().split()) a = list(map(int, input().split())) s = [0] * (n + 1) for i in range(n): s[i + 1] = s[i] + a[i] for _ in range(q): l, r = map(int, input().split()) # đánh số từ 1 print(s[r] - s[l - 1])
Buổi 26 – Sàng Eratosthenes
M = 10**6 nt = [True] * (M + 1) nt[0] = nt[1] = False i = 2 while i * i <= M: if nt[i]: nt[i * i::i] = [False] * len(range(i * i, M + 1, i)) # gạch bội của i (cách nhanh trong Python) i += 1
Giải thích bằng hình: viết bảng số 1–100 lên giấy, cho HS lần lượt gạch bội của 2, 3, 5, 7.
Phân hóa cho 2 học sinh
- Lớp 7: tập trung buổi 13, 15, 18, 20, 21, 22, 24 – làm chắc bài ★, ★★.
- Lớp 8: thêm buổi 25 (cộng dồn 2 chiều, mảng hiệu) và bài ★★★ (đếm đoạn có tổng k, xâu đối xứng dài nhất).
- Mỗi tuần: mỗi em tự giải thêm 5–10 bài online đúng chủ đề tuần trên LQDOJ/VNOJ.