Bỏ qua để đến nội dung

Lập trình thi đấu

Đề thi học sinh giỏi Tin học hay tuyển sinh chuyên Tin thường có giới hạn kiểu n ≤ 105 hoặc n ≤ 106. Với giới hạn đó, cách thử hết mọi khả năng thường cần tới 1010 phép tính trở lên, chỉ lấy được điểm các test nhỏ. Lập trình thi đấu là các kỹ thuật giúp đưa số phép tính xuống còn khoảng 106 đến 108, đủ để chương trình chạy kịp giới hạn của đề.

Mỗi bài trong mục này gồm:

  • Lý thuyết giải thích vì sao kỹ thuật đúng và vì sao nó nhanh, kèm bảng chạy tay.
  • Chương trình Python và C++ cho từng ý quan trọng.
  • Bài luyện tập có đáp số để tự kiểm tra (miễn phí). Lời giải chi tiết các bài luyện tập có trong bộ tài liệu có phí.
  • Học sinh THCS, THPT ôn thi học sinh giỏi Tin học và tuyển sinh chuyên Tin lớp 10.
  • Học sinh thi Tin học trẻ Bảng B, C (lập trình Python, C++).
  • Thầy cô dạy đội tuyển cần một lộ trình có bài luyện tập theo từng kỹ thuật.

Các bạn cần viết được chương trình có vòng lặp, mảng, hàm trước khi bắt đầu.

Lộ trình chia thành ba giai đoạn theo mức độ, mỗi giai đoạn gồm các chặng đánh số. Các bạn học lần lượt từ chặng 1 trở đi: chặng sau dùng kiến thức của chặng trước. Một số bài nền tảng nằm ở mục CTDL & Giải thuật và phần toán nằm ở mục Toán tin, lộ trình ghi rõ tên mục ở các bài đó. Icon trước mỗi giai đoạn cũng là icon mức độ ở đầu từng bài và trong mục lục bên trái.

0 / 82 bài đã học

Bấm vào ô tròn trước tên bài để đánh dấu đã học. Tiến độ lưu trên trình duyệt này. 11 bài ghi "Chưa có bài" đang được soạn.

Bắt đầuĐộ phức tạp thuật toánChặng 1 · Làm quen với thi đấu

Giai đoạn Cơ bản

Thi học sinh giỏi cấp huyện, cấp tỉnh THCS, Tin học trẻ Bảng B, C. Các bạn nên bắt đầu từ đây.

  1. 1Làm quen với thi đấuƯớc lượng số bước chạy và vét cạn có tổ chức.0/6
  2. 2Số học cơ bảnChia hết, ước, số nguyên tố và phép lấy dư, gặp nhiều trong đề thi.0/6
  3. 3Biểu diễn số và phép toán bitSố nhị phân và các phép toán trên từng bit.0/2
  4. 4Sắp xếp, tìm kiếm và tham lamSắp xếp dữ liệu để tìm nhanh và chọn đúng.0/3
  5. 5Kỹ thuật trên mảngBốn kỹ thuật đưa n² bước xuống còn khoảng n bước.0/4
  6. 6Cấu trúc dữ liệu cơ bảnCác cấu trúc có sẵn trong Python và C++ mà bài nào cũng dùng tới.0/4
  7. 7Quy hoạch động nhập mônLưu lại kết quả bài toán con để không tính lại.0/2
    • Dãy truy hồiLập công thức bằng cách xét bước cuối, tính từ dưới lên.Toán tin
    • Quy hoạch độngĐổi tiền, cái túi, khoảng cách chỉnh sửa.CTDL & Giải thuật
  8. 8Đồ thị nhập mônBiểu diễn đồ thị và hai cách duyệt.0/2
  9. 9Tổ hợp và trò chơi cơ bảnĐếm số cách và tìm người thắng.0/5

Giai đoạn Nâng cao

Thi học sinh giỏi cấp tỉnh, tuyển sinh chuyên Tin lớp 10.

  1. 10Kỹ thuật tìm kiếm và tham lamTìm đáp án bằng cách đoán rồi kiểm tra, chia đôi tập để vét cạn nhanh hơn.0/4
  2. 11Kỹ năng thiTự kiểm tra lời giải trước khi nộp.0/1
  3. 12Cấu trúc dữ liệu nâng caoGiữ dữ liệu luôn có thứ tự, gộp nhóm nhanh.0/3
  4. 13Truy vấn trên đoạnTrả lời nhiều câu hỏi trên đoạn mà không duyệt lại cả đoạn.0/2
  5. 14Quy hoạch độngCác dạng quy hoạch động kinh điển.0/5
  6. 15Đồ thịDuyệt, đường đi ngắn nhất, cây khung.0/5
  7. 16Số học và trò chơi nâng caoLũy thừa lớn, phương trình đồng dư, trò chơi nhiều đống.0/4
  8. 17Hình học tọa độTính toán trên điểm, đoạn thẳng, đa giác.0/3
  9. 18Xử lý xâu cơ bảnSo sánh xâu con nhanh, xâu đối xứng.0/2

Giai đoạn Chuyên sâu

Thi học sinh giỏi quốc gia, lập trình thi đấu (ICPC).

  1. 19Cây phân đoạn và chia cănTruy vấn và cập nhật trên đoạn khi dữ liệu thay đổi.0/2
    • Cây phân đoạn (Segment Tree)Hỏi và sửa trên đoạn trong log n bước, cập nhật lười.
    • Chia căn và thuật toán MoChia mảng thành khối √n, trả lời truy vấn đoạn theo thứ tự có lợi.
    • Cây phân đoạn bền vữngGiữ lại mọi phiên bản của cây sau mỗi lần sửa.Chưa có bài
  2. 20Kỹ thuật trên câyĐưa bài toán trên cây về bài toán trên mảng.0/4
  3. 21Quy hoạch động nâng caoTrạng thái là tập con, công thức truy hồi với n rất lớn, tối ưu chuyển trạng thái.0/2
    • Quy hoạch động trạng thái bitTrạng thái là một tập con, bài người du lịch.
    • Lũy thừa ma trậnTính số hạng thứ n của dãy truy hồi với n đến 10¹⁸.Toán tin
    • Tối ưu chia để trịGiảm quy hoạch động n² khi vị trí tối ưu tăng dần.Chưa có bài
    • Bao lồi trong quy hoạch độngConvex hull trick khi công thức chuyển là các đường thẳng.Chưa có bài
    • Quy hoạch động tổng trên tập con (SOS)Tính tổng trên mọi tập con trong n × 2ⁿ bước.Chưa có bài
  4. 22Đồ thị nâng caoCấu trúc liên thông, ghép cặp và luồng.0/2
  5. 23Xử lý xâu nâng caoTìm mẫu trong xâu và cấu trúc trên tập xâu.0/2
    • KMP và Z-functionTìm mọi vị trí xuất hiện của mẫu trong n + m bước.
    • Cây tiền tố (Trie)Lưu tập xâu theo tiền tố chung, XOR lớn nhất.
    • Aho-CorasickTìm nhiều mẫu cùng lúc.Chưa có bài
    • Mảng hậu tốSắp xếp mọi hậu tố, mảng LCP.Chưa có bài
  6. 24Toán chuyên sâuHàm số học, tổ hợp modulo, xác suất, hình học nâng cao.0/7

Các bài trong mục này so sánh hai cách làm bằng số phép tính, không bằng thời gian: thời gian chạy thật phụ thuộc rất nhiều vào máy, ngôn ngữ, trình biên dịch và cách viết code.

Để biết cách làm nào hợp với giới hạn của đề, các bạn thay n lớn nhất vào số bước. Ví dụ n = 105: thử mọi cặp mất khoảng 5 × 109 bước, còn kỹ thuật hai con trỏ chỉ mất khoảng 2 × 105 bước, ít hơn khoảng 25 000 lần.

Th.S Trần Huy Phúc

Th.S Trần Huy Phúc

Principal Software Engineer @Adnovum & Bumbii Academy