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ổiChủ đềNội dung chínhBài tập gợi ý
13Hàmdef, tham số, return; so sánh "khối tự tạo" ScratchViế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ố)
14Luyện tập hàmChia 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
15Xâu nâng caofind, 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²))
16List nâng caolist comprehension, cắt list, insert, pop, del, list lồng nhauXóa phần tử trùng (giữ thứ tự), xoay dãy k vị trí, trộn hai dãy
17Mả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 ô)
18Sắp xếpsort, sorted, reverse=True, key=, nhiều tiêu chí; tự viết sắp xếp nổi bọt để hiểuXế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ếpSau 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 thiopen, 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ánO(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ớnCù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
22set và dictKiểm tra tồn tại O(1), đếm tần suất bằng dict, CounterCặ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
23Luyện tập dict/setGom 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ⱼ
24Mảng cộng dồn 1 chiềus[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)
25Cộ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ầnTruy 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
26Sàng Eratosthenes & số họcSà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ỗiIn giá trị trung gian, chạy từng bước (Thonny), viết lời giải "trâu" để đối chiếuHS tự tìm lỗi trong 5 chương trình sai do giáo viên chuẩn bị
28Thi thử lần 23–4 bài, 120 phút, đọc/ghi fileRa đề 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)

ScratchPython
Tạo khối la_nguyen_to (x)def la_nguyen_to(x):
Khối trả về giá trịreturn True
Dùng khốiif 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 đaThuật toán chấp nhận đượcVí dụ
≤ 10O(n!)Thử mọi hoán vị
≤ 20O(2ⁿ)Thử mọi tập con
≤ 100O(n³)3 vòng lặp lồng nhau
≤ 2 000 – 3 000O(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.
Zalo