Ôn Thi HSG Tin Học (Lập Trình C++)
Ôn Thi HSG Tin Học (Lập Trình C++)
Mục tiêu của khóa học
- Nắm vững tư duy thuật toán và lập trình C++ theo định hướng thi Học sinh giỏi Tin học.
- Thành thạo các cấu trúc dữ liệu và thuật toán cốt lõi thường xuất hiện trong đề thi HSG:
- Binary Search, Deque, Hashing, BIT, Segment Tree, Sparse Table,…
- Hiểu và vận dụng tốt các dạng Quy hoạch động quan trọng:
- Quy hoạch động cơ bản, Digit DP, DP Bitmask, tối ưu DP bằng Segment Tree, nhân ma trận.
- Làm chủ các thuật toán đồ thị và cây nâng cao:
- Dijkstra, MST, LCA, SCC.
- Rèn luyện kỹ năng phân tích đề, tối ưu thuật toán và cài đặt chính xác, đáp ứng yêu cầu đề thi HSG các cấp.
- Tự tin tham gia kỳ thi HSG cấp trường, huyện, tỉnh và các kỳ thi chọn đội tuyển.
Đối tượng học viên
- Học sinh ôn thi học sinh giỏi tin học, Olympic tin học
- Học sinh thích thú với lập trình (8-12)
Sự khác biệt khoá học
- 9 Lý Do nên lựa chọn Fullhouse Dev mà không phải trung tâm khác:
- 1. 100% Giáo viên đạt giải lập trình thi đấu quốc gia hoặc làm việc doanh nghiệp lớn.
- 2. Lộ trình, Slide bài giảng được biên soạn cẩn thận và chuyên sâu.
- 3. Giáo viên giảng dạy vô cùng dễ hiểu được kiểm duyệt kỹ trước khi vào lớp.
- 4. Hệ thống Website chấm tự động với 600-800 bài tập chuyên sâu có lời hướng dẫn giải.
- 5. Kèm 1:1 bất kỳ khi nào học viên cần.
- 6. Đo lường đánh giá được số bài tập làm được, số bài đúng, số bài sai, thời gian tham gia học từng bạn.
- 7. Phương pháp học châu âu Flipped Classroom, Mind Map, Mentor System.
- 8. cuộc thi định kỳ, quà tặng, nhắc nhở thúc đẩy học tập.
- 9. Chứng nhận sau khoá học.
Phương pháp giảng dạy
- Dạy học online trực tiếp với giáo viên
- Có mentor kèm 1:1
- Giải đáp mọi kiến thức, bài tập 24/24
- Có video xem lại sau mỗi buổi học
Nội dung chương trình học
CHƯƠNG 1: KÝ THUẬT CƠ BẢN & TƯ DUY THUẬT TOÁN
Ôn tư duy chia để trị
Bài toán mở đầu tìm kiếm nhị phân
Binary search trên mảng tăng/giảm
Lỗi thường gặp (mid, điều kiện dừng)
Khái niệm “chặt nhị phân trên đáp án”
Điều kiện đơn điệu
Các dạng bài: tối ưu min/max
So sánh với tìm kiếm nhị phân thường
Định nghĩa deque
Bài toán tìm min/max trên đoạn tịnh tiến
Kỹ thuật cửa sổ trượt
Phân tích độ phức tạp O(n)
Mục đích của hashing
Hash chuỗi, hash số
Collision và cách hạn chế
Ứng dụng so sánh nhanh
Ý tưởng cây chỉ số nhị phân
Update điểm – Query prefix
Update đoạn (giới thiệu)
So sánh BIT và Segment Tree
CHƯƠNG 2:QUY HOẠCH ĐỘNG
Khái niệm DP
Trạng thái, công thức chuyển
Top-down & Bottom-up
Các lỗi thường gặp
DP dãy con
DP trên bảng
Tối ưu bộ nhớ
Ý tưởng DP theo chữ số
Trạng thái: pos, tight, sum…
Các bài đếm số thỏa điều kiện
Khái niệm bitmask
Biểu diễn tập hợp
DP bitmask cơ bản
Giới hạn N ≤ 20
Loại bỏ trạng thái dư
Tiền xử lý
Kỹ thuật tối ưu phổ biến
Ôn Segment Tree
Lazy propagation
Ứng dụng tối ưu DP
CHƯƠNG 3: CẤU TRÚC DỮ LIỆU NÂNG CAO
RMQ – Range Minimum Query
RSQ – Range Sum Query
Tiền xử lý O(n log n)
Query O(1)
Xây dựng tổng quát
Update đoạn
Query đoạn
So sánh BIT – Sparse – Segtree
Ý tưởng chia căn
Phân đoạn mảng
Độ phức tạp
Áp dụng chia căn
Xử lý offline query
Sắp xếp truy vấn
So sánh các kỹ thuật
Chọn giải pháp phù hợp bài toán
Bài luyện tập tổng hợp
CHƯƠNG 4: ĐỒ THỊ & CÂY
Bài toán đường đi ngắn nhất
Dijkstra với priority_queue
Ứng dụng thực tế
Khái niệm cây khung
Tính chất MST
Kruskal / Prim
Binary Lifting
Tiền xử lý cây
Query LCA O(log n)
Liên thông
Liên thông mạnh (SCC)
Kosaraju / Tarjan
Ứng dụng SCC
Nén đồ thị
Bài toán thực tế HSG
Kết hợp nhiều thuật toán
Phân tích đề HSG
Bài luyện đề
CHƯƠNG 5: THUẬT TOÁN NÂNG CAO & LUYỆN ĐỀ
Phép nhân ma trận
Lũy thừa ma trận
Độ phức tạp
DP tuyến tính
Chuyển sang ma trận
Bài toán Fibonacci mở rộng
Bài tập vận dụng
Tổng hợp toàn bộ kiến thức
Chiến lược làm bài
Thi thử HSG Tin học
Chữa chi tiết & nhận xét
