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í.
Dành cho ai?
Phần tiêu đề “Dành cho ai?”- 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
Phần tiêu đề “Lộ trình”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.
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.
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
- Độ phức tạp thuật toánĐếm số phép tính theo n, ký hiệu O lớn.CTDL & Giải thuật
- Ví dụ phân tích độ phức tạpĐọc độ phức tạp từ vòng lặp lồng nhau, tìm kiếm nhị phân.CTDL & Giải thuật
- Đọc giới hạn của đề để chọn thuật toánTừ n lớn nhất suy ra cách làm nào chạy kịp, lấy điểm từng subtask.
- Đệ quyHàm gọi lại chính nó với bài toán nhỏ hơn.CTDL & Giải thuật
- Quay lui, nhánh cậnThử từng lựa chọn, gặp ngõ cụt thì lùi lại, cắt bỏ nhánh không thể tốt hơn.CTDL & Giải thuật
- Chia để trịChia bài toán làm đôi, giải từng nửa rồi ghép lại.CTDL & Giải thuật
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
- Phép chia có dư và chia hếtThương, số dư, dấu hiệu chia hết.Toán tin
- Ước và bộiLiệt kê ước đến √n, đếm ước, tổng ước.Toán tin
- ƯCLN, BCNN - thuật toán EuclidTìm ước chung lớn nhất trong khoảng log n bước.Toán tin
- Số nguyên tốKiểm tra số nguyên tố đến √n, phân tích thừa số nguyên tố.Toán tin
- Sàng EratosthenesLiệt kê mọi số nguyên tố đến n cùng một lúc.Toán tin
- Đồng dư và phép toán moduloCộng, trừ, nhân theo modulo khi kết quả quá lớn.Toán tin
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
- Hệ nhị phân và hệ cơ sốĐổi số giữa hệ thập phân, nhị phân và hệ cơ số bất kỳ.Toán tin
- Phép toán bitAND, OR, XOR, dịch bit, duyệt mọi tập con bằng bit.Toán tin
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
- Thuật toán sắp xếpSắp xếp n² và n log n, sắp xếp đếm phân phối.CTDL & Giải thuật
- Tìm kiếm tuần tự và nhị phânTìm trong dãy đã sắp xếp với log n bước, tìm biên trái, biên phải.CTDL & Giải thuật
- Thuật toán tham lamMỗi bước chọn cái tốt nhất trước mắt, và khi nào cách đó sai.CTDL & Giải thuật
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
- Tổng tiền tố và mảng hiệuTổng một đoạn trong một phép tính, cộng cả đoạn trong hai phép tính.Toán tin
- Mảng đánh dấu và đếm tần suấtĐếm số lần xuất hiện bằng chỉ số mảng thay vì so từng cặp.
- Hai con trỏ và cửa sổ trượtHai đầu đoạn chỉ tiến về phía trước, mỗi đầu đi tối đa n bước.
- Rời rạc hóa (nén số)Đổi giá trị đến 10⁹ về 1, 2, 3... giữ nguyên thứ tự.
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
- Ngăn xếp (stack)Vào sau ra trước, kiểm tra dãy ngoặc.CTDL & Giải thuật
- Hàng đợi (queue), dequeVào trước ra trước, hàng đợi hai đầu.CTDL & Giải thuật
- Heap, hàng đợi ưu tiênLấy phần tử nhỏ nhất hoặc lớn nhất trong log n bước.CTDL & Giải thuật
- Bảng bămTra cứu theo khóa gần như tức thì: dict, set, unordered_map.CTDL & Giải thuật
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Đồ thị nhập mônBiểu diễn đồ thị và hai cách duyệt.0/2
- Đồ thị và cách biểu diễnĐỉnh, cạnh, ma trận kề, danh sách kề.CTDL & Giải thuật
- Duyệt đồ thị BFS, DFSLan theo từng lớp và đi sâu trước.CTDL & Giải thuật
9Tổ hợp và trò chơi cơ bảnĐếm số cách và tìm người thắng.0/5
- Quy tắc cộng, quy tắc nhânĐếm bằng cách chia trường hợp và chia bước.Toán tin
- Hoán vị, chỉnh hợp, tổ hợpĐếm số cách sắp xếp và số cách chọn.Toán tin
- Nguyên lý bù trừĐếm phần hợp của nhiều tập mà không đếm trùng.Toán tin
- Nguyên lý DirichletNhiều vật hơn ngăn kéo thì có ngăn chứa từ hai vật trở lên.Toán tin
- Vị trí thắng, vị trí thuaTính ngược từ cuối trò chơi để biết ai thắng.Toán tin
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.
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
- Tìm kiếm nhị phân theo đáp ánĐoán đáp án rồi kiểm tra, mỗi lần loại một nửa khoảng.
- Tham lam trong thi đấuSắp xếp theo tiêu chí đúng, chứng minh bằng đổi chỗ hai phần tử.
- Meet in the middleChia đôi n phần tử, từ 2ⁿ khả năng xuống khoảng 2 × 2ⁿᐟ².
- Tìm kiếm tam phânTìm cực trị của hàm tăng rồi giảm.
11Kỹ năng thiTự kiểm tra lời giải trước khi nộp.0/1
- Sinh test và stress testTìm test sai bằng chương trình vét cạn và dữ liệu ngẫu nhiên.
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
- Ngăn xếp đơn điệu, hàng đợi đơn điệuPhần tử lớn hơn gần nhất, nhỏ nhất trên cửa sổ trượt.
- set, multiset, map có thứ tựTập luôn sắp xếp: thêm, xóa, tìm phần tử gần nhất trong log n bước.
- Disjoint Set Union (DSU)Gộp hai nhóm và hỏi hai phần tử có cùng nhóm không.
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
- Bảng thưa (Sparse Table)Nhỏ nhất trên đoạn trong một phép tính khi mảng không đổi.
- Cây Fenwick (BIT)Sửa phần tử, tính tổng tiền tố trong log n bước, đếm nghịch thế.
14Quy hoạch độngCác dạng quy hoạch động kinh điển.0/5
- Dãy con tăng dài nhất (LIS)Từ n² xuống n log n bằng tìm kiếm nhị phân.
- Xâu con chung dài nhất (LCS)So khớp hai xâu bằng bảng hai chiều.
- Bài toán cái túiChọn đồ vật với giới hạn khối lượng: 0/1, không giới hạn, có số lượng.
- Quy hoạch động trên đoạnTrạng thái là đoạn [l, r], ghép từ các đoạn ngắn hơn.
- Quy hoạch động chữ sốĐếm số trong [L, R] thỏa điều kiện về chữ số.Toán tin
15Đồ thịDuyệt, đường đi ngắn nhất, cây khung.0/5
- BFS, DFS trên lướiĐếm vùng, đường đi ngắn nhất trên bảng ô vuông.
- Sắp xếp tô-pôThứ tự làm việc khi có ràng buộc trước sau, quy hoạch động trên DAG.
- Đường đi ngắn nhấtDijkstra, BFS 0-1, Bellman-Ford, SPFA, Floyd.
- Cây khung nhỏ nhấtKruskal, Prim: nối mọi đỉnh với tổng chi phí nhỏ nhất.
- Đường đi và chu trình EulerĐi qua mỗi cạnh đúng một lần.
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
- Lũy thừa nhanhTính a mũ b theo modulo trong log b bước.Toán tin
- Thuật toán Euclid mở rộngGiải ax + by = d, tìm nghịch đảo modulo.Toán tin
- Định lý số dư Trung HoaGiải hệ phương trình đồng dư.Toán tin
- Trò chơi Nim, định lý Sprague-GrundyXOR các đống để biết ai thắng.Toán tin
17Hình học tọa độTính toán trên điểm, đoạn thẳng, đa giác.0/3
- Điểm, khoảng cách và tích có hướngBa điểm rẽ trái hay rẽ phải, hai đoạn thẳng có cắt nhau.Toán tin
- Diện tích đa giác và điểm nguyênCông thức dây giày, định lý Pick.Toán tin
- Đường quétXử lý sự kiện theo thứ tự tọa độ: hợp hình chữ nhật, cặp điểm gần nhất.
18Xử lý xâu cơ bảnSo sánh xâu con nhanh, xâu đối xứng.0/2
- Hash xâuSo sánh hai đoạn xâu bằng một phép so sánh số.
- Xâu đối xứng, thuật toán ManacherMọi xâu con đối xứng dài nhất tại từng tâm trong n bước.
Giai đoạn Chuyên sâu
Thi học sinh giỏi quốc gia, lập trình thi đấu (ICPC).
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
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
- Tổ tiên chung gần nhất (LCA)Nhảy nhị phân, khoảng cách hai đỉnh trên cây.
- Euler tour trên câyĐánh số đỉnh theo thứ tự DFS để cây con thành một đoạn liên tiếp.
- Quy hoạch động trên câyTính từ lá lên gốc, đổi gốc.
- Gộp nhỏ vào lớn (small to large)Luôn gộp tập nhỏ vào tập lớn, tổng cộng n log n bước.
- Phân rã nặng nhẹ (HLD)Chia đường đi trên cây thành log n đoạn liên tiếp.Chưa có bài
- Phân tách trọng tâmChia cây theo trọng tâm để đếm đường đi.Chưa có bài
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
22Đồ thị nâng caoCấu trúc liên thông, ghép cặp và luồng.0/2
- Khớp, cầu, thành phần liên thông mạnhĐỉnh, cạnh mà bỏ đi thì đồ thị bị tách, thuật toán Tarjan.
- Đồ thị hai phía và ghép cặpTô hai màu, ghép cặp cực đại bằng đường tăng.
- 2-SATChọn đúng hoặc sai cho mỗi biến để thỏa mọi ràng buộc hai biến.Chưa có bài
- Luồng cực đạiLát cắt nhỏ nhất, thuật toán Dinic.Chưa có bài
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
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
- Chia khối theo giá trị n // iChỉ có khoảng 2√n giá trị khác nhau của n chia i.Toán tin
- Hàm Euler, định lý EulerĐếm số nguyên tố cùng nhau với n, rút gọn số mũ.Toán tin
- Hàm nhân tính, hàm MöbiusSàng tuyến tính, đảo Möbius.Toán tin
- Miller-Rabin, Pollard rhoKiểm tra nguyên tố và phân tích thừa số với số đến 10¹⁸.Toán tin
- Tổ hợp modulo: Legendre, Kummer, LucasTính C(n, k) theo modulo số nguyên tố nhỏ.Toán tin
- Xác suất và kỳ vọngTính kỳ vọng bằng tính chất tuyến tính.Toán tin
- Bao lồi, kỹ thuật xoay compaBao lồi, đường kính tập điểm.Toán tin
- Nhân nhanh đa thức (FFT)Nhân hai đa thức bậc n trong n log n bước.Chưa có bài
Ước lượng thời gian chạy
Phần tiêu đề “Ước lượng thời gian chạy”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.