Viblo Algorithm

I. Giới thiệu

Những bài toán truy vấn đoạn luôn luôn là chủ đề thú vị trong các kì thi lập trình. Một số thao tác truy vấn đoạn đơn giản có thể kể đến là tính tổng đoạn con, tìm max/min đoạn con hay tìm của đoạn con,...Những thao tác này nếu như không có sự hỗ trợ của các cấu trúc dữ liệu thì sẽ tốn độ phức tạp thời gian là thường dẫn đến lỗi TLE trong các bài toán multi-testcase.

Chia căn ...

I. Lời mở đầu

Trong các kì thi lập trình thi đấu, ngoài việc suy nghĩ thuật toán, các thí sinh còn phải đau đầu với một công việc, đó là tối ưu thời gian chạy chương trình. Nguyên do là vì, trong các kì thi này, ràng buộc về thời gian chạy của các bài tập khá ngặt nghèo, thường là $10,50,1$ giây. Trong những trường hợp như vậy, ngoài việc tìm ra thuật toán tốt, các kĩ thuật để tối ưu thời gian...

Đây là bài viết số $21,$ mời các bạn nhấn vào đây.

III. Ứng dụng của mảng hiệu

1. Ứng dụng cơ bản

Bài toán cơ bản của mảng hiệu là bài toán cập nhật đoạn, được phát biểu như sau:

"Cho dãy số gồm phần tử. Bạn được cho trước truy vấn, với mỗi truy vấn yêu cầu cập nhật các giá trị có vị trí thuộc đoạn thêm đơn vị.

Yêu cầu: In ra mảng sau khi thực hiện tất cả truy vấn?"

Input:

• Dòn...

I. Giới thiệu chung

Những bài toán trên mảng là chủ đề rất quen thuộc ở các kì thi lập trình. Mảng tổng tiền tố và Mảng hiệu là hai kĩ thuật bổ trợ, giúp đẩy nhanh tốc độ tính toán của một số thao tác trên mảng. Trong chuyên đề này, chúng ta sẽ cùng tìm hiểu về cách xây dựng và những ứng dụng của hai kĩ thuật nói trên.

1. Khái niệm

Mảng tổng tiền tố

Với mảng gồm phần tử ta xây dựng một m...

I. Bài toán sắp xếp

Sắp xếp là một khái niệm mà chúng ta dễ dàng gặp trong cuộc sống cũng như trong công việc. Cùng lấy một vài ví dụ:

• Sắp xếp lại đồ đạc trong phòng, trong nhà.
• Sắp xếp các tài liệu trong tủ sách theo thứ tự.
• Sắp xếp công việc cho anh em trong công ty.

Trong Tin học, việc sắp xếp luôn luôn diễn ra không ngừng mà đôi khi chúng ta không nhận ra. Chẳng hạn, trong mỗi fold...

I. Tổng quan về bit và xử lý bit

Chúng ta đều biết rằng máy tính làm việc với các giá trị nhị phân $0 - 1,$ gọi là các bit, nhờ vậy máy tính hoạt động vô cùng nhanh. Trong lập trình thi đấu, việc áp dụng các bit nhị phân để xử lý bài toán là một kĩ thuật cực kì thú vị, không chỉ giúp cho tốc độ thuật toán được cải thiện đáng kể, mà còn làm tối ưu bộ nhớ và đơn giản hóa chương trình. Kĩ thuật n...

Đây là bài viết số 2 thuộc bài học Cấp phát bộ nhớ động và Danh sách liên kết của chuyên đề lập trình C++ cơ bản. Để nắm vững bài viết này, trước tiên các bạn hãy tìm đọc lại các bài viết trước đây gồm các kiến thức liên quan:

• Địa chỉ ảo, Tham chiếu và Con trỏ trong C++.
• Hoạt động nâng cao với con trỏ trong C++.
• Kĩ thuật Cấp phát bộ nhớ động trong C++.

I. Giới thiệu chung

Đối với những...

I. Phân loại các vùng nhớ trên bộ nhớ ảo

Qua một số bài học về con trỏ, chúng ta đã biết rằng việc lưu trữ dữ liệu trong khi lập trình C++ được quản lý dựa trên kĩ thuật Bộ nhớ ảo (Virtual Memory). Việc nắm rõ các phân vùng của bộ nhớ ảo và chức năng của chúng rất quan trọng trong khi lập trình, nó sẽ giúp lập trình viên hiểu rõ cơ chế lưu trữ dữ liệu, từ đó quản lý bộ nhớ một cách hợp lý. Vậy...

Đây là bài viết số 2 thuộc series bài viết Tham chiếu, Địa chỉ và Con trỏ trong C++ của chuyên đề lập trình C++ cơ bản định hướng thi HSG Tin học.

Để hiểu rõ về bài viết này, các bạn hãy tìm đọc lại các bài viết trước đây trong series này:

• Địa chỉ ảo, Tham chiếu và Con trỏ.

I. Con trỏ và mảng một chiều

Chúng ta biết rằng chức năng của con trỏ là để lưu trữ một địa chỉ của một vùng nhớ trê...

Để hiểu được những kiến thức được đề cập trong bài viết này, bạn đọc cần nắm vững các kiến thức liên quan tới Thao tác xử lý bit (Bit manipulation). Các bạn có thể tìm đọc bài viết về kiến thức này tại đây.

I. Mở đầu

Các phép toán thao tác bit là những phép toán rất thú vị của những ngôn ngữ lập trì...

III. Một số bài toán áp dụng giải thuật quay lui

Bây giờ, tôi sẽ giới thiệu tới các bạn một số bài toán ví dụ kinh điển về giải thuật quay lui. Hãy cùng nhau phân tích chúng và đối chiếu lại với phương pháp chung ở bài viết trước để hiểu rõ hơn về lý thuyết phương pháp nhé!

1. Bài toán xếp hậu

Đề bài

Một bàn cờ vua đang để trống. Câ...

I. Mở đầu

Những bài toán liên quan tới truy vấn trên đoạn là khá phổ biến trong lập trình thi đấu. Có thể kể đến một số bài toán tiêu biểu như: Tìm giá trị min/max trên đoạn (Range Minimum Queries), Tính tổng trên đoạn (Range Sum Queries),...Cùng với sự phát triển của các bài toán này, các cấu trúc dữ liệu để giải quyết chúng cũng được sinh ra như Cây phân đoạn (Interval Tree), Cây nhị phân ch...

Đây là phần ba của series bài viết về Xử lý số nguyên lớn trong C++. Trước khi đọc bài này, các bạn cần biết cách biểu diễn số nguyên lớn, cũng như các phép toán so sánh, cộng, trừ và nhân số lớn. Nếu như chưa nắm vững, các bạn hãy tìm đọc lại tại các bài viết trước đây:

• <a href="https://viblo.asia/p/xu-ly-so-nguyen-lon-phan-1-nhapxuat-phep-so-sanh-phep-cong-va-phep-tru-V3m5WQpxZO7" title="" target="_blank">Các phép...

I. Đặt vấn đề

Trong lập trình thi đấu nói riêng và trong khoa học máy tính nói chung, vấn đề xử lý chuỗi kí tự là vấn đề rất phổ biến. Các bài toán về chuỗi vô cùng đa dạng, và một trong số những dạng toán hay gặp chính là tìm kiếm và so khớp chuỗi. Bài toán dưới đây là một ví dụ cơ bản nhất:

"Cho một chuỗi kí tự độ dài và một chuỗi kí tự độ dài . Cần trả lời câu hỏi: Chuỗi kí tự xuất hiệ...

Tổng quan

Thuật toán Bellman-Ford là thuật toán dùng để tìm đường đi ngắn nhất từ một đỉnh tới các đỉnh còn lại trong đồ thị có trọng số. Cùng một vấn đề nhưng thuật toán Bellman-Ford chậm hơn so với thuật toán Dijkstra nhưng lại đa năng hơn ở chỗ thuật toán có thể xử lý trên đồ thị có cạnh mang trọng số âm. Thuật toán được đề xuất lần đầu tiên bởi Alfonso Shimbel (1955), nhưng được đặt tên th...

Trong chuyên đề này, tôi sẽ chia sẻ tới các bạn một kĩ thuật khá hữu ích trong các kì thi lập trình, sử dụng cho các bài toán liên quan tới nhiều truy vấn cập nhật tăng/giảm một đoạn liên tiếp trên dãy số hoặc ma trận. Chúng ta sẽ tiếp cận các kĩ thuật này thông qua một số bài toán cụ thể để cho dễ hình dung. Những bài toán tôi giới thiệu dưới đây cũng có thể coi là những kĩ thuật cơ bản của tr...

Trong bài viết phần 1 về chủ đề Hình học tính toán, chúng ta đã cùng nghiên cứu về cách sử dụng vector trong các bài toán hình học. Còn trong bài viết này, tôi sẽ giới thiệu những vấn đề liên quan tới đường thẳng, giao điểm và sử dụng kiến thức về đại số tuyến tính để tính toán giao điểm, tính toán diện tích, qua đó áp dụng trong những bài toán hình học của lập trình thi đấu.

I. Biểu diễn đườn...

I. Lời nói đầu

Như các bạn đã biết, trong chương trình Toán phổ thông, chúng ta đã được nghiên cứu khá nhiều về các bài toán liên quan tới chủ đề Hình học. Tuy nhiên, không chỉ trong môn Toán, mà trong môn Tin học, các bài toán Hình học cũng là một chủ đề khá quen thuộc, thậm chí còn "khó nhai" trong các kì thi lập trình. Hình học tính toán (Computational Geometry) là một nhánh của ngành Khoa ...

I. Giới thiệu chung

Ánh xạ là một cấu trúc dữ liệu có tính ứng dụng rất cao trong lập trình. Về bản chất, cấu trúc dữ liệu này được cài đặt thủ công (dựa trên cây nhị phân tự cân bằng hoặc bảng băm), tuy nhiên việc cài đặt thủ công rất dài dòng và phức tạp, lại dễ xảy ra nhầm lẫn. Vì thế, những ngôn ngữ lập trình hiện đại đã giải quyê...

I. Giới thiệu chung

Với những ai đã và đang học lập trình, đặc biệt là lập trình thi đấu, thì những cấu trúc dữ liệu như set, map hay dictionary có lẽ là rất quen thuộc. Tên gọi của chúng có thể khác nhau ở các ngôn ngữ, nhưng tác dụng thì không hề thay đổi. Ứng dụng của chúng lớn đến mức, nhiều tài liệu khi hướng dẫn về lập trình cơ bản ...