Lớp C / Lập trình thi đấu nâng cao

Phân tích bài toán sâu hơn.
Xây lời giải có lập luận.

90 phút / buổi5–8 học sinh

Một lời giải thuật toán cần trả lời được ba câu hỏi: vì sao đúng, sử dụng dữ liệu như thế nào và tốn bao nhiêu thao tác. Lớp C phát triển cách phân tích đó qua kỹ thuật mảng, cấu trúc dữ liệu, đệ quy, chia để trị, quay lui, tham lam, chặt nhị phân trên đáp án và băm xâu. Quy hoạch động tiếp nối bằng việc xác định trạng thái, liên hệ các bài toán con và truy vết lời giải. Toàn bộ chương trình lớp C gồm 19 chủ đề, hướng đến nền tảng chuyên Tin và HSG cấp Tỉnh theo đối tượng đã công bố.

Đăng ký học lớp C

*Lịch học sắp xếp thuận tiện nhất cho học viên theo từng đợt tuyển sinh; trao đổi cụ thể cùng CSAT ngay bây giờ!

Poster lớp C của CSAT

Ảnh giới thiệu lớp C

ĐỐI TƯỢNG

Học sinh lớp 7, 8, 9 có định hướng thi HSG cấp Tỉnh, chuyên Tin các tỉnh mạnh, cạnh tranh.

CÙNG CHỌN ĐIỂM BẮT ĐẦU

Lớp C tiếp nối nền tảng C++ và các phương pháp giải bài cơ bản. Bạn hãy chia sẻ những bài đã tự phân tích, cài đặt và kiểm tra, cùng các thuật toán mình từng sử dụng. Từ đó, CSAT sẽ cùng bạn xác định kiến thức cần củng cố và điểm học tiếp phù hợp trong chương trình nâng cao.

THÔNG TIN LỚP

109.000đ / buổi

90 phút / buổi · 5–8 học sinh.

Định hướng phát triển / C

Mở rộng phương pháp. Đào sâu lập luận.

  1. 01 / ĐIỂM BẮT ĐẦU

    Từ nền tảng đến mô hình

    Kết nối kiến thức cơ bản với cách biểu diễn dữ liệu và phân tích giới hạn của bài toán.

  2. 02 / QUÁ TRÌNH HỌC

    Kỹ thuật → chiến lược → trạng thái

    Sáu chặng đi từ xử lý mảng và cấu trúc dữ liệu đến các chiến lược tìm kiếm, rồi quy hoạch động.

  3. 03 / HƯỚNG VẬN DỤNG

    Lập luận và tối ưu lời giải

    Đối chiếu cách giải với tính đúng đắn, độ phức tạp và trường hợp biên khi luyện bài chuyên Tin, HSG Tỉnh.

NỘI DUNG HỌC TẬP / C19 CHỦ ĐỀ / 6 CHẶNG

Kiến thức có trình tự.
Tư duy có chiều sâu.

Tham khảo lộ trình Tự học
01 / CTiền xử lý và kỹ thuật trên mảng3 chủ đề · C01–C03
  • Tiền xử lý
  • Truy vấn đoạn
  • Bất biến hai con trỏ
  • Cập nhật cửa sổ
  • Điều kiện áp dụng
  1. C01

    Kỹ thuật mảng: Mảng cộng dồn

    • 1D & 2D

    Chuẩn bị thông tin để tính tổng trên đoạn hoặc vùng dữ liệu.

    Xây mảng cộng dồn một chiều và hai chiều; liên hệ tổng cần tìm với những giá trị đã tính trước.

  2. C02

    Kỹ thuật mảng: Mảng hiệu

    • Difference array

    Biểu diễn thay đổi trên đoạn thông qua thông tin chênh lệch.

    Tìm hiểu mảng hiệu và quan hệ với phép cộng dồn; theo dõi cách cập nhật được ghi nhận rồi khôi phục thành dữ liệu.

  3. C03

    Kỹ thuật mảng: Hai con trỏ, cửa sổ trượt

    Khai thác quan hệ giữa các vị trí hoặc đoạn liên tiếp trong dãy.

    Dùng hai con trỏ và cửa sổ trượt; xác định khi nào dịch chuyển biên và thông tin nào cần giữ khi phạm vi thay đổi.

02 / CLựa chọn cấu trúc dữ liệu3 chủ đề · C04–C06
  • Chọn thao tác chủ đạo
  • Chi phí thêm / xóa / tìm
  • Thứ tự LIFO / FIFO
  • Duy trì thứ tự dữ liệu
  • Kiểm soát bộ nhớ
  1. C04

    Cấu trúc dữ liệu: Tuyến tính

    • vector
    • pair
    • unique

    Tổ chức và xử lý dữ liệu tuyến tính theo thao tác cần thực hiện.

    Kết nối vector, pair và unique với biểu diễn dãy, nhóm thuộc tính và xử lý phần tử trùng theo yêu cầu.

  2. C05

    Cấu trúc dữ liệu: Cây & Băm

    • set
    • map
    • mảng đếm

    Lựa chọn cách lưu, tìm và thống kê dữ liệu theo đặc trưng của bài toán.

    Đối chiếu set, map và mảng đếm về vai trò lưu trữ, truy cập; phân biệt yêu cầu của từng cấu trúc trong lời giải.

  3. C06

    Cấu trúc dữ liệu: Hàng đợi & Ngăn xếp

    • queue
    • deque
    • stack

    Biểu diễn những quy tắc khác nhau về thứ tự đưa vào và lấy dữ liệu.

    Tìm hiểu queue, deque và stack; theo dõi thứ tự xử lý để liên hệ cấu trúc với mô hình của bài toán.

03 / CĐệ quy, chia để trị và quay lui3 chủ đề · C07–C09
  • Phân rã bài toán
  • Điều kiện dừng đệ quy
  • Sinh đủ phương án
  • Khôi phục trạng thái
  • Cắt nhánh có căn cứ
  1. C07

    Đệ quy & Chia để trị

    • đệ quy có nhớ
    • merge sort

    Giải bài toán thông qua những bài toán nhỏ hơn và cách tổng hợp kết quả.

    Phân tích đệ quy, đệ quy có nhớ và merge sort; làm rõ điều kiện dừng, lời gọi con và bước kết hợp.

  2. C08

    Quay lui: Sinh tổ hợp

    • nhị phân
    • hoán vị
    • xâu

    Sinh các phương án theo một quá trình xây dựng có thứ tự.

    Vận dụng quay lui để sinh dãy nhị phân, hoán vị và xâu; theo dõi lựa chọn, trạng thái và thao tác khôi phục.

  3. C09

    Quay lui: Mô hình

    • N quân hậu
    • mã đi tuần
    • cắt nhánh

    Xây mô hình tìm kiếm cho những bài toán có ràng buộc giữa các lựa chọn.

    Phân tích N quân hậu, mã đi tuần và cắt nhánh; xác định điều kiện hợp lệ và những hướng có thể loại bỏ.

04 / CTham lam, tìm kiếm trên đáp án và băm3 chủ đề · C10–C12
  • Lập luận lựa chọn tham lam
  • Tính đơn điệu
  • Hàm kiểm tra khả thi
  • Phản ví dụ
  • Va chạm hashing
  1. C10

    Tham lam

    • chọn hoạt động
    • đổi tiền
    • xếp lịch

    Xem xét khi nào một chuỗi lựa chọn theo tiêu chí có thể tạo lời giải phù hợp.

    Đối chiếu chọn hoạt động, đổi tiền và xếp lịch để phân tích tiêu chí tham lam; kiểm tra điều kiện áp dụng bằng lập luận và phản ví dụ.

  2. C11

    Chặt nhị phân: Vòng 2

    • chặt trên đáp án
    • hàm check

    Chuyển việc tìm đáp án thành quá trình kiểm tra các giá trị ứng viên.

    Xây hàm check và phân tích tính đơn điệu trước khi chặt nhị phân trên đáp án; theo dõi miền đáp án sau từng lần kiểm tra.

  3. C12

    Xử lý xâu: Thuật toán Hashing

    Tìm hiểu cách biểu diễn xâu bằng giá trị băm để hỗ trợ so sánh.

    Liên hệ dữ liệu xâu với biểu diễn hashing; xem xét cách so sánh và giới hạn của việc dùng giá trị băm.

05 / CXây dựng trạng thái quy hoạch động4 chủ đề · D01–D04
  • Định nghĩa trạng thái
  • Khởi tạo cơ sở
  • Quan hệ chuyển
  • Thứ tự tính
  • Tối ưu bộ nhớ
  1. D01

    QHĐ: Nhập môn

    • leo bậc thang
    • tam giác số
    • Kadane

    Làm quen việc giải bài toán bằng kết quả của những bài toán con.

    Phân tích leo bậc thang, tam giác số và Kadane qua trạng thái, điều kiện ban đầu, quan hệ chuyển và thứ tự tính.

  2. D02

    QHĐ: Trên lưới

    • đường đi lớn nhất
    • đếm cách đi

    Biểu diễn quá trình tính toán theo vị trí trong một bảng hoặc lưới.

    Xây trạng thái cho đường đi lớn nhất và đếm cách đi; liên hệ một ô với những vị trí có thể dẫn đến nó.

  3. D03

    QHĐ: Cái túi

    • Knapsack 0/1
    • không giới hạn số lượng

    Mô tả lựa chọn dưới một giới hạn bằng trạng thái quy hoạch động.

    Đối chiếu Knapsack 0/1 với trường hợp không giới hạn số lượng; phân tích vai trò của giới hạn và thứ tự cập nhật.

  4. D04

    QHĐ: Chia tập

    • đổi tiền
    • chia kẹo

    Tổ chức các lựa chọn thành mô hình tính toán trên tổng hoặc phần được phân chia.

    Phân tích bài toán đổi tiền, chia kẹo; làm rõ ý nghĩa trạng thái, lựa chọn bổ sung và kết quả cần tính.

06 / CQuy hoạch động trên dãy, xâu và mở rộng3 chủ đề · D05–D07
  • Mô hình hóa dãy / xâu
  • Thông tin đủ trong trạng thái
  • Truy vết phương án
  • Tránh tính lặp
  • So sánh độ phức tạp
  1. D05

    QHĐ: LIS

    • dãy con tăng dài nhất
    • truy vết

    Mô hình hóa quan hệ giữa các phần tử khi tìm dãy con tăng dài nhất.

    Phân tích LIS qua trạng thái thể hiện dãy con và cách truy vết để đi từ giá trị tối ưu tới một lời giải cụ thể.

  2. D06

    QHĐ: LCS & Xâu

    • xâu con chung dài nhất
    • Edit Distance

    Biểu diễn quan hệ giữa hai xâu bằng những bài toán con.

    Đối chiếu LCS và Edit Distance để xác định trạng thái theo vị trí, điều kiện ký tự và quan hệ chuyển.

  3. D07

    QHĐ: Mở rộng

    • trạng thái 2 chiều
    • chia đoạn

    Mở rộng cách mô tả trạng thái khi một chiều thông tin chưa đủ.

    Phân tích trạng thái hai chiều và chia đoạn; xác định các chiều cần lưu, quan hệ phụ thuộc và cách tổng hợp kết quả.

Điểm đến của hành trình / C

Mục tiêu cuối khoá

Quá trình học hướng đến sự tiến bộ trong cách suy nghĩ, lựa chọn phương pháp và tự kiểm tra lời giải — để mỗi kiến thức trở thành một công cụ có thể vận dụng.

  1. 01

    Tư duy bài toán

    Mô hình hóa bài toán, lý giải tính đúng đắn và độ phức tạp; kết nối nhiều kỹ thuật, kiểm tra trường hợp biên và truy vết lời giải.

  2. 02

    Dạng bài vận dụng

    Luyện bài xử lý dãy và xâu, tìm kiếm phương án, tối ưu lựa chọn và các dạng quy hoạch động như knapsack, dãy con, xâu con và khoảng cách chỉnh sửa.

  3. 03

    Thuật toán & mức độ

    Phân tích và vận dụng cộng dồn, mảng hiệu, hai con trỏ, cửa sổ trượt, cấu trúc dữ liệu, đệ quy, chia để trị, quay lui, tham lam, chặt trên đáp án, hashing và quy hoạch động trong phạm vi 19 chủ đề.

  4. 04

    Nền tảng để đi tiếp

    Củng cố nền tảng chuyên Tin và HSG cấp Tỉnh. Học sinh có thể trao đổi hướng học sâu ở lớp E và tìm hiểu thi tuyển riêng từ C.

Tìm hiểu lớp E và thi tuyển

Cùng CSAT chọn bước tiếp theo

Chia sẻ việc học.
Cùng chọn hướng đi.

Bạn đang quan tâm lập trình thi đấu nâng cao? Hãy bắt đầu từ những điều đã học và mục tiêu muốn hướng tới.

NỘI DUNG QUAN TÂM

C — Lập trình thi đấu nâng cao

Chia sẻ nhu cầu học tập hoặc tài liệu bạn đang tìm cùng đội ngũ CSAT.