III. XÂU KÝ TỰ (STRING) - "XỬ LÝ VĂN BẢN"

Phần 3: Kỹ thuật xử lý chuỗi và chuẩn hóa dữ liệu - Đội tuyển HSG Phan Chu Trinh

Xâu ký tự thực chất là một "mảng của các ký tự". Tuy nhiên, trong Python, xâu ký tự có những phương thức xử lý cực mạnh giúp việc biến đổi văn bản trở nên đơn giản.

Ví dụ 3: Chuẩn hóa họ tên
Yêu cầu: Nhập vào một họ tên có thể chứa khoảng trắng thừa ở đầu, cuối hoặc giữa các từ. Hãy chuyển đổi về dạng chuẩn (Viết hoa chữ cái đầu mỗi từ, các từ cách nhau đúng 1 dấu cách).

1. Mã nguồn Python Full (Tham khảo)

def chuan_hoa_ho_ten(s): # Bước 1: Tách xâu thành danh sách các từ (loại bỏ khoảng trắng thừa)
words = s.split()
# Bước 2: Viết hoa chữ cái đầu mỗi từ (capitalize)
cap_words = [w.capitalize() for w in words]
# Bước 3: Nối lại thành xâu hoàn chỉnh bằng dấu cách
result = ' '.join(cap_words)
return result
# Sử dụng name = " nguYễn vĂn aN " print(f"Kết quả: '{chuan_hoa_ho_ten(name)}'") # Output: "Nguyễn Văn An"

Lưu ý quan trọng:

• Hàm split() không tham số sẽ tự động gom các khoảng trắng liên tiếp thành 1 dấu phân cách.
• Xâu ký tự trong Python là Immutable (không thể thay đổi trực tiếp từng ký tự), nên ta thường chuyển sang List rồi mới Join lại.

✨ CÔNG CỤ CHUẨN HÓA TÊN TRỰC TUYẾN

Nhập họ tên cần chuẩn hóa:

Kết quả:

Trạng thái:

4. Tư duy lập trình

Trong các kỳ thi HSG, xâu ký tự thường xuất hiện trong các bài toán về Tần suất (kết hợp với Dictionary) hoặc Xử lý số lớn (BigNum). Việc nắm vững split() và join() giúp bạn tiết kiệm 50% thời gian viết code so với các ngôn ngữ cũ như Pascal hay C++.

II. MẢNG (LIST) - "DÃY NGĂN KÉO CHỨA ĐỒ"

Phần 2: Quản lý và xử lý dữ liệu tập trung - Đội tuyển HSG Phan Chu Trinh

Mảng là cấu trúc dữ liệu quan trọng nhất giúp chúng ta lưu trữ hàng triệu giá trị chỉ với một tên biến duy nhất.

Ví dụ 2: Quản lý điểm số
Đề bài: Cho danh sách điểm của n học sinh. Tìm điểm cao nhất và đếm xem có bao nhiêu bạn đạt số điểm đó.

1. Mã nguồn Python tối ưu

# Cách 1: Sử dụng các hàm xây dựng sẵn (Built-in)
def thong_ke_diem(ds_diem):
    diem_max = max(ds_diem)
    so_luong = ds_diem.count(diem_max)
    return diem_max, so_luong

# Cách 2: Duyệt một vòng lặp (Tối ưu nhất cho dữ liệu lớn)
def tim_max_va_dem(ds_diem):
    m = -1
    c = 0
    for x in ds_diem:
        if x > m:
            m = x; c = 1
        elif x == m:
            c += 1
    return m, c

Phân tích thuật toán:

• Kiến thức: Truy xuất A[i], hàm max(), count().
• Tư duy: Gom nhóm dữ liệu. Thay vì xử lý rời rạc, ta xử lý trên một tập hợp thống nhất.
• Độ phức tạp: $O(n)$. Với 1 triệu học sinh ($n=10^6$), Python chỉ mất khoảng 0.1s.

📊 MÔ PHỎNG QUẢN LÝ ĐIỂM HỌC SINH

Nhập số lượng học sinh bạn muốn giả lập (N):

Điểm cao nhất

--

Số bạn đạt được

--

Thời gian xử lý

--

3. Bài học về kỹ năng

Khi làm việc với mảng trong thi HSG Tin học, hãy luôn ưu tiên các hàm có sẵn của Python như sum(), max(), min(), sort() vì chúng được viết bằng ngôn ngữ C, giúp chương trình chạy nhanh hơn nhiều so với việc tự viết vòng lặp thủ công.

BÀI 1: ĐỘ PHỨC TẠP THUẬT TOÁN

Dành cho đội tuyển HSG Tin học - THPT Phan Chu Trinh

1. Khái niệm về "Thước đo sức mạnh" $O$

Trong lập trình thi đấu, không phải cứ ra kết quả đúng là có điểm. Bạn phải ra kết quả đúng trong thời gian cho phép (thường là 1 giây).

Quy tắc vàng: Máy tính xử lý được khoảng 10⁷ - 10⁸ phép tính mỗi giây. Nếu thuật toán của bạn vượt quá con số này, bạn sẽ nhận lỗi TLE (Time Limit Exceeded).

2. Ví dụ: Tính tổng từ 1 đến $N$

Đề bài: Tính tổng $S = 1 + 2 + 3 + \dots + n$ với $n$ là số nguyên dương nhập từ bàn phím.
CÁCH 1: Duyệt tuần tự (Vòng lặp for - Duyệt vòng lặp $O(N)$) Mô tả: Giống như việc em đi bộ từ cổng trường vào lớp, bước đủ $n$ bước, mỗi bước cộng thêm 1 giá trị vào tổng.Mã nguồn Python:

def sum_linear(n):
    s = 0
     for i in range(1, n + 1):
         s += i
     return s

=> Càng nhiều bước ($N$ lớn), máy càng tốn thời gian.

Phân tích:
    - Kiến thức: Sử dụng biến tích lũy và vòng lặp cơ bản.
    -Tư duy: Tuyến tính (Linear). $n$ tăng gấp đôi thì máy phải làm việc gấp đôi.
    - Độ phức tạp: $O(n)$.).

CÁCH 2: Dùng công thức toán học (Gauss)

Mô tả: Thay vì đi bộ, em dùng "siêu năng lực" dịch chuyển tức thời. Chỉ cần một phép tính duy nhất là ra kết quả.:

def sum_constant(n):
    return n * (n + 1) // 2

=> Dù $N$ lớn bao nhiêu, chỉ cần 1 bước tính là xong!

Phân tích:
    - Kiến thức: Áp dụng công thức tổng cấp số cộng: $$S = \frac{n(n+1)}{2}$$
    -Tư duy: TTối ưu (Constant). Không phụ thuộc vào độ lớn của $n$.
    - Độ phức tạp: $O(1)$

🔬 PHÒNG THÍ NGHIỆM THUẬT TOÁN

import time
def demo_complexity(n):
    print(f"\n--- Thử nghiệm với n = {n:,} ---")
    # Đo Cách 1: O(n)
    start = time.time()
    res1 = sum_linear(n)
    end = time.time()
     print(f"Cách 1 (Vòng lặp): Kết quả = {res1}, Thời gian = {end - start:.5f} giây")
    # Đo Cách 2: O(1)
    start = time.time()
    res2 = sum_constant(n)
    end = time.time()
     print(f"Cách 2 (Toán học): Kết quả = {res2}, Thời gian = {end - start:.5f} giây")
# Chạy thử nghiệm
demo_complexity(10**7) # 10 triệu
demo_complexity(10**8) # 100 triệu

Nhập số $N$ để so sánh tốc độ (Thử với $N = 10,000,000$):

Cách 2 - $O(1)$: ---

Cách 1 - $O(N)$: ---

3. Bài học rút ra

• Tư duy tuần tự: Dễ nhưng chậm.
• Tư duy tối ưu: Cần kiến thức nhưng cực nhanh.