Tìm hiểu cấu trúc dữ liệu quan trọng có ứng dụng mở rộng. bảng băm [bảng băm]. Xây dựng các hàm cơ bản để nâng cao. hàm Robert Sedgewick, đa thức, dịch chuyển tuần hoàn,… Phân tích các phương pháp giải quyết xung đột. chuỗi riêng biệt, mở địa chỉ,… Giới thiệu bài toán Bộ nhớ cache ít được sử dụng gần đây nhất [LRU Cache]
Application file
Lộ trình này được xây dựng để chuẩn bị cho cuộc thi ôn thi Olympic tin học SV & ACM-ICPC, nhưng bạn cũng có thể sử dụng để
- Khác biệt thi lập trình
- standard is for the phỏng vấn bài thi
- Nâng cao kỹ năng thuật toán
- Phục vụ các môn học tại trường học
- đam mê
Yêu cầu với người học
- Biết ít nhất một ngôn ngữ lập trình [Bạn phải có khả năng lập trình với ngôn ngữ đó]
- Có kiến thức & hiểu biết cơ bản về các Cấu hình dữ liệu cơ bản [Mảng, Ngăn xếp, Hàng đợi,…][Nếu bạn không biết một số trong đó, hãy tìm hiểu nó khi cần sử dụng trong lộ trình này]
Tái bút. Tôi có nói Bất kỳ ngôn ngữ nào, nhưng trong lộ trình này hầu hết sử dụng C, C++ và một chút Java, bạn vẫn có thể theo lộ trình này mà không nhất định phải biết các ngôn ngữ đó
Trong lộ trình ôn thi Olympic tin học & ACM này, chúng tôi sẽ chia sẻ liên kết tới các tài nguyên, chúng tôi khi viết lại những gì đã có. Chúng tôi chỉ tập hợp các tài nguyên hữu ích lại một chỗ, và bạn có thể dễ dàng theo dõi để học. Lộ trình này cũng bao gồm các thuật toán và cấu trúc dữ liệu. Bạn nên đi theo lộ trình này theo từng tuần đã được chúng tôi chỉ định
Hướng dẫn dành cho bạn
- Go to the resource resource to learn
- Tập trung suy nghĩ, cố gắng code và không xem lời giải
- Khi bạn gặp khó khăn [bạn đã cố gắng hết sức] hoặc đã hoàn thành nhiệm vụ, hãy xem lời giải, so sánh với lời giải của bạn và xem đâu là lời giải tốt nhất cho bài toán đó. Bạn có thể sẽ tìm được những thứ hay ho từ lời giải thích của người khác
- Khi bạn cảm thấy hài lòng với kiến thức đã có, hãy nhớ giải quyết các bài toán của phần kiến thức đó
- Khi bạn hoàn thành hoặc gặp sự cố, hãy xem xét các giải pháp khác và tìm xem bạn có gặp lỗi gì không và nhận được một giải pháp tốt hơn
Một số trang web luyện tập
Trong lộ trình ôn thi Olympic tin học & ACM này, chúng tôi sẽ sử dụng một số tài nguyên cho việc luyện tập. Như đã nói ở trên, các bài toán đã có sẵn, chúng tôi chỉ giúp bạn thấy chúng dễ dàng hơn. Đây là các trang web / công cụ chúng tôi sử dụng trong suốt lộ trình
- luyện mã
- Leetcode
- spj
- Hackerrank
- Topcoder
- mật mã
- ánh sáng
- ACM-Timus
Tôi cung cấp tên của họ bởi vì có thể bạn sẽ không thể cập nhật lời giải của bạn hoặc xem bài toán. Vấn đề sẽ tốt hơn nếu bạn tạo cho mình một tài khoản trên đó
Các kiến thức cần học
Đây là danh sách các chủ đề có trong lộ trình này
Constructor data[DS]
- ngăn xếp
- hàng đợi
- Hàng đợi ưu tiên
- Bản đồ băm
- Danh sách liên kết
- Cây
- đống
- Cây nâng cao
- cố gắng
- cây phân khúc
- Cây Fenwick hoặc cây chỉ số nhị phân
- RMQ
- Phân tích SQRT
- Cấu trúc dữ liệu rời rạc
- C++ STL [tùy chọn]
Giải thuật [Algo]
- Lý thuyết số
- Số nguyên tố [Sàng Eratosthenes]
- Thuật toán GCD và LCM Euclids
- lũy thừa mô-đun
- Số học dài [Multi, Add]
- Thừa số nguyên tố hiệu quả
- Tổ hợp[Xác suất-Tổ hợp-Hoán vị-Ma trận. ]
- hình học tính toán
- Hoạt động nguyên thủy
- Trực giác
- Đa giác bên trong, bên ngoài
- Thực hiện CCW
- Điểm bất biến ADT
- Thân tàu lồi
- Vấn đề cặp gần nhất
- đường giao nhau
- Hoạt động nguyên thủy
- Sắp xếp
- Sắp xếp nhanh chóng
- sắp xếp đếm
- Hợp nhất Sắp xếp
- Đang tìm kiếm
- Tìm kiếm nhị phân
- Tìm kiếm bậc ba
- Lý thuyết đồ thị
- Tìm kiếm theo chiều sâu [DFS]
- Tìm kiếm theo chiều rộng đầu tiên [BFS]
- Con đường ngắn nhất của Dijkstra
- Cây bao trùm tối thiểu
- Ford Bellman
- Floyd Warshall
- LCA [Tổ tiên chung thấp nhất]
- Lưu lượng tối đa / Cắt tối thiểu
- Lập trình năng động
- ba lô
- Phép nhân chuỗi ma trận
- Đổi xu
- Kadane
- Dãy con tăng dài nhất [với RMQ]
- Dây
- thuật toán Z
- Cây/Mảng hậu tố
- Thuật toán Knuth-Morris-Pratt [KMP]
- Thuật toán Rabin-Karp
- Băm
- Thao tác bit
- lý thuyết trò chơi
- trò chơi nim
- Số bẩn thỉu
- Định lý Sprague-Grundy
- Thuật toán nâng cao tùy chọn
- Cây AVL
- tô màu đồ thị
- Thuật toán Mos
- Cây Palindromic
- Phân hủy ánh sáng nặng
- Lập trình động theo hồ sơ
- cắt que
- Sắp xếp tô pô
- DP với Bitmask - Lập trình động
- Phương Trình Diophantine - Toán
- Lũ lụt - Graph
Lộ trình học tham khảo
Dưới đây là lộ trình ôn thi Olympic tin học & ACM-ICPC các bạn tham khảo. Mình có để liên kết đến hướng dẫn chi tiết hơn cho mỗi tuần tại cột Tuần. Các bạn chỉ việc tiếp tục theo dõi nội dung chi tiết bạn trong đó
Chủ đề tuầnChủ đề tùy chọnThông báo- Ký hiệu chữ O lớn
- Số nguyên tố [Sàng Eratosthenes]
- Thừa số nguyên tố hiệu quả
- lũy thừa mô-đun
- Thuật toán GCD và LCM Euclids
- Số học dài [Multi, Sum, Div, Sub]
- C++ STL. véc tơ
- C++ STL. Cặp
- C++ STL. vòng lặp
- Sắp xếp nhanh chóng
- sắp xếp đếm
- C++ STL. Sợi dây
- C++ STL. Bộ
- C++ STL. Bản đồ
- Hợp nhất Sắp xếp
- Tìm kiếm nhị phân
- Tìm kiếm bậc ba
- Hàng đợi [ĐS]
- Ngăn xếp [ĐS]
- Tìm kiếm đầu tiên theo chiều rộng
- Độ sâu tìm kiếm đầu tiên
- C++ STL. Xếp hàng
- C++ STL. Cây rơm
- Danh sách liên kết [DS]
- Con đường ngắn nhất của Dijkstra
- Cây bao trùm tối thiểu [MST]
- Floyd Warshall
- Phát hiện chu kỳ [Union Find]
- ba lô
- Đổi xu
- Kadane
- Cây [ĐS]
- Cây phân đoạn [DS]
- Phạm vi truy vấn tối thiểu [RMQ]
- Tổ tiên chung thấp nhất [LCA]
- Sắp xếp tô pô
- Ford Bellman
- Lưu lượng tối đa / Cắt tối thiểu
- Dãy con tăng dài nhất [với RMQ]
- Phân hủy ánh sáng nặng
- Hoạt động nguyên thủy
- Trực giác
- Đa giác bên trong, bên ngoài
- Thực hiện CCW
- Điểm bất biến ADT
- Thân tàu lồi
- Vấn đề cặp gần nhất
- đường giao nhau
- Thử [DS]
- Cây/Mảng hậu tố [DS]
- Thuật toán Knuth-Morris-Pratt [KMP]
- Thuật toán Rabin-Karp
- đống [DS]
- Hàng đợi ưu tiên [DS]
- tổ hợp
- thuật toán Z
- Băm
- Cấu trúc dữ liệu rời rạc [DS]
- Phép nhân chuỗi ma trận
- Phân rã SQRT [DS]
- Thuật toán Mos
- cắt que
- trò chơi nim
- Số bẩn thỉu
- Định lý Sprague-Grundy
- Cây Fenwick hoặc cây chỉ số nhị phân [DS]
- Thao tác bit
- Cây Palindromic
- Cây AVL
- Phân hủy ánh sáng nặng
- Lập trình động theo hồ sơ
- tô màu đồ thị
Tài liệu tham khảo
- Diễn đàn VNOI
- Lưu trữ tài liệu, đề thi của Olympic ACM-ICPC
- Đề thi OLP-ACM qua các năm
- Thi trực tuyến khu vực 2017. https. //hochiminh17. katti. com/vấn đề
- Thi trực tuyến khu vực 2018. https. //hà nội18. katti. com/vấn đề
- Lời giải ACM các năm. https. //github. com/acm icpc-vietnam/acm icpc-vietnam. github. io
- Các thuật toán được sử dụng trong lập trình cạnh tranh
- Cách chuẩn bị cho ACM - ICPC
Chúc các bạn tân sinh viên tham gia mùa thi Olympic & ACM-ICPC thành công
- THẺ
- acm icpc
- cấu trúc dữ liệu
- giải thuật
- olympic tin học sinh
Nguyễn Văn Hiếu
Sáng lập cộng đồng Lập Trình Không Khó với mong muốn giúp đỡ các bạn trẻ trên con đường trở thành những lập trình viên tương lai. Tất cả những gì tôi viết ra đây chỉ đơn giản là cơ sở thích ghi lại các kiến thức mà tôi tích lũy được