#
Tag: competitive programming
See all tags.
Rất cảm ơn SmolLemon, một thành viên của ChuyentinORZ, đã contribute cho ChuyentinORZ Wiki! Các bạn có thể xem repo gốc
Ngôn ngữ lập trình C++ là một trong ngôn ngữ được sử dụng phổ biến, nếu không muốn nói là phổ biến nhất trong lập trình thi đấu.
Trong các bài toán lập trình, bài sẽ yêu cầu ta nhập vào dữ liệu, và in ra kết quả tương ứng. Ta sẽ ví dụ về cách nhập xuất dữ liệu trong C
Ở C++ và nhiều ngôn ngữ lập trình ta sẽ bắt gặp các kiểu dữ liệu được biểu diễn ở dạng nhị phân như sau:
Dưới đây là một số mẹo cho C++ trong lập trình thi đấu.
Toán học có vai trò quan trọng trong lập trình thi đấu.
Khi viết chương trình giải quyết các bài toán, ta cần phải tuân thủ những giới hạn mà bài toán đặt ra về thời gian và bộ nhớ.
Một số nhị phân là một số được biểu diễn trong hệ cơ số 2 - các được biểu diễn bằng 2 chữ số 0 và 1. Trong lập trình, kiểu dữ liệu lưu các số nguyên có
Thuật toán sắp xếp là thuật toán tối quan trọng trong lập trình thi đấu.
Bài toán mở đầu: Cho một mảng a chứa n phần tử phân biệt được sắp xếp tăng dần. Kiểm tra xem có tồn tại phần tử có giá trị x trong mảng hay không.
Kĩ thuật hai con trỏ là kĩ thuật sử dụng hai con trỏ để thực hiện việc duyệt các phần tử trong mảng.
Stack (ngăn xếp) là một CTDL lưu trữ các phần tử gồm 2 thao tác chính:
Queue (hàng đợi) là một CTDL lưu trữ các phần tử gồm 2 thao tác chính:
Hàng đợi hai đầu (Double-ended queue - deque, dequeue) là một CTDL cho phép việc thêm và loại bỏ phần tử ở đầu và cuối phần tử.
Ta có bài toán sau: Cho một mảng a có n phần tử và q truy vấn có dạng (l, r).
Quay lại với bài toán ở phần bảng thưa:
Cây chỉ số nhị phân (Binary Index Tree) hay cây Fenwick (Fenwick Tree) là một CTDL giúp ta trả lời các truy vấn trên đoạn một cách hiệu quả.
CTDL Disjoint Sets Union (DSU) hay với tên gọi khác là Union-Find Disjoint Sets (UFDS) là một CTDL quản lí các tập hợp không giao nhau, tức là các tập...
Duyệt toàn bộ (Complete search), hay với các tên gọi khác như duyệt trâu, vét cạn, brute force, là một mô hình thuật toán.
Greed is good. Greed is right. Greed works. Greed clarifies, cuts through, and captures the essence of the evolutionary spirit.
"Divide et impera. Veni, vidi, vici" - Julius Caesar
Pending
Quy hoạch động chữ số hay Digit DP chỉ các bài toán sử dụng quy hoạch động liên quan đến các chữ số.
Trước khi đến với lí thuyết đồ thị, ta có một câu hỏi nhỏ như sau:
Được xuất hiện trên VNOI Wiki
Thứ tự tô-pô (Topological Ordering) của một đồ thị có hướng G = (V, E) là thứ tự sắp xếp của các đỉnh trên một đoạn thẳng sao cho với mỗi cạnh
Khi giải quyết nhiều bài toán lý thuyết đồ thị, ta phải duyệt qua tất cả các đỉnh của đồ thị đó.
Thuật toán tìm kiếm theo chiều rộng (Breadth-First Search - BFS) là một thuật toán tìm kiếm trên đồ thị.
Thuật toán tìm kiếm theo chiều sâu (Depth-First Search - DFS) là một thuật toán tìm kiếm/duyệt trên đồ thị.
Hai thuật toán tìm kiếm trên đồ thị đã được nói ở phần trước tuy đơn giản nhưng lại có tính ứng dụng rất cao. Ta sẽ điểm qua một số ứng dụng của nó.