Image Cover
Avatar

Viblo Algorithm

@algorithm

Report

Pinned Posts

Đâ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ê...

545
4
2 0

All posts

Thumbnail Image
324
3
1 0
Avatar Viblo Algorithm thg 6 13, 8:00 SA
6 min read

Sắp xếp với thời gian tuyến tính

Mở đầu

Ta đã làm quen với rất nhiều thuật toán sắp xếp. Độ phức tạp trung bình nhanh nhất trong các thuật toán sắp xếp là . Bạn có bao giờ tự hỏi rằng, ta có thể sắp xếp một mảng với độ phức tạp thời gian tuyến tính không 😄

Giải pháp

Counting sort

Nếu một mảng bao gồm số nguyên với phạm vi nhỏ (Ví dụ như tuổi thọ của một người chẳng hạn 😄). Ta có thể sử dụng thuật toán Counting Sort. ...

Thumbnail Image
104
2
0 0
Avatar Viblo Algorithm thg 5 31, 9:48 SA
13 min read

Quy hoạch động 7.4: Palindromes và Các bài toán QHĐ liên quan

I. Những bài toán cơ sở

Trong Lập trình thi đấu, xâu palindrome (xâu đối xứng) là một loại xâu kí tự đặc biệt. Đó là những xâu mà viết xuôi hay viết ngược đều giống nhau, chẳng hạn như ABBA hay TOEICCIEOT,...Nhờ tính chất đặc biệt này, người ta phát triển ra rất nhiều bài toán liên quan tới xâu palindrome, không chỉ ở trong xâu kí tự mà còn có th...

Thumbnail Image
237
2
2 0
Avatar Viblo Algorithm thg 5 17, 10:08 SA
17 min read

Giải thuật Tìm kiếm nhị phân nâng cao

I. Bài toán Tìm kiếm nhị phân tổng quát

Ở bài viết trước, mình đã giới thiệu tới các bạn những khái niệm cơ bản nhất về bài toán tìm kiếm trong Tin học, cũng như giới thiệu về hai giải thuật Tìm kiếm tuần tự và Tìm kiếm nhị phân. Trong bài viết này, mình sẽ tập trung nói về giải thuật Tìm kiếm nhị phân, nhưng sẽ là áp dụng trong một lớp ...

Thumbnail Image
492
2
0 0
Avatar Viblo Algorithm thg 5 3, 8:00 SA
13 min read

Thuật toán Đường quét (Sweep line algorithm)

I. Giới thiệu

Trong hình học tính toán, việc xét các điểm trên một mặt phẳng là bài toán thường xuyên xảy ra. Tuy nhiên, với dữ liệu lớn trong các bài toán Lập trình thi đấu, việc quét qua tất cả mọi điểm trên mặt phẳng dường như là bất khả thi, chính vì thế ta sẽ chỉ xét tới một số điểm cần thiết mà thôi.

Thuật toán đường quét (Sweep line algorithm) được xây dựng dựa trên tư tưởng nói trên. ...

Thumbnail Image
586
4
0 0
Avatar Viblo Algorithm thg 4 16, 9:00 SA
17 min read

Các thuật toán tìm Bao lồi (Convex hull)

Để hiểu được nội dung trong bài viết này, các bạn cần nắm vững các kiến thức về Hình học tính toán cơ bản. Các bạn có thể xem lại hai bài viết này tại các link dưới đây:

  • Những vấn đề cơ bản về Vector.
  • Sự giao nhau của các đường thẳng và Tính toán diện tích.

I. Định nghĩa Bao lồi

Bao lồi là một vấn đề rất thường xuyên xuất hiện trong các bài tập hình học tính toán của lập trình thi đấu. ...

Thumbnail Image
274
2
1 0
Avatar Viblo Algorithm thg 3 27, 10:17 SA
8 min read

Trie Tree (phần 2) - Trie nhị phân

Đây là bài viết số 2121 liên quan tới Trie Tree cơ bản tại đây: Trie Tree phần 1.

I. Giới thiệu chung

Ta đã biết rằng Trie là một cấu trúc dữ liệu dạng cây, sử dụng rất hiệu quả trong các bài toán liên quan tới quản lý danh sách xâu kí tự. Tuy nhiên, ít ai biết rằng Trie Tree còn có một ứng dụng nữa, đó là quản lý một tập số nguyên.

Bằng cách coi mỗi số là một xâu kí tự gồm toàn kí tự 0 và 1...

Thumbnail Image
653
3
0 0
Avatar Viblo Algorithm thg 3 22, 9:00 SA
14 min read

Trie Tree (phần 1) - Xử lý xâu kí tự

I. Giới thiệu chung

Trie là một cấu trúc dữ liệu dạng cây, hay còn gọi là Cây tiền tố (Suffix tree). Đây là một cấu trúc dữ liệu hữu ích sử dụng để quản lý một tập hợp các xâu kí tự, và có thể mở rộng ra các bài toán liên quan tới quản lý tập số nguyên (xem phần 2 của bài viết tại đây).

Cấu trúc của Trie rất đơn giản, nó là một cây kiểm soát các kí tự của một xâu trên từng cạnh, cho phép lưu ...

Thumbnail Image
818
10
3 0
Avatar Viblo Algorithm thg 2 21, 8:00 SA
26 min read

Bài toán đường đi ngắn nhất (phần 2) - Thuật toán Dijkstra và Ford Bellman

Đây là bài viết số 2 trong series bài viết về Bài toán đường đi ngắn nhất trên đồ thị. Để theo dõi lại phần 1 của series, các bạn hãy nhấn vào đây.

I. Tổng quan

  1. Phát biểu bài toán

Ta đã biết về thuật toán Floyd - Warshall trong bài toán tìm đường đi ngắn nhất giữa mọi cặp đỉnh trước...

Thumbnail Image
293
3
0 0
Avatar Viblo Algorithm thg 1 30, 8:00 SA
5 min read

Số học đồng dư (Phần 2): Phương trình đồng dư tuyến tính

Trong bài viết này, chúng ta sẽ cùng thảo luận về phương pháp giải của phương trình đồng dư tuyến tính - một dạng phương trình khá quen thuộc trong số học đồng dư nhưng lại không được đề cập trong chương trình Toán cấp THCS - THPT. Đó là phương trình có dạng:

Mặc dù chỉ phổ biến trong các chuyên đề HSG Toán, nhưng trong Tin học thì phương trình này lại khá thú vị và có thể áp dụng để giải quyế...

Thumbnail Image
481
3
1 0
Avatar Viblo Algorithm thg 1 19, 8:00 SA
17 min read

Chia căn (phần 2) - Mo's algorithm

Đây là bài viết số 2121 về Chia căn tại đây.

I. Giới thiệu chung

Ở bài viết phần 1,n1051,n \le 10^5). Chia căn còn có những ứng dụng to lớn hơn nữa, cộng thêm việc cài đặt đơn giản, khiến cho nó trở thành một kĩ thuật vô cùng hữu ích trong phòng thi.

Tiếp nối các ứng dụng của Chia căn, trong bài viết này chúng ta sẽ cùng bàn về kĩ thuật tăng tốc độ trả lời các truy vấn bằng cách sắp xếp chúng th...

Thumbnail Image
632
4
2 0
Avatar Viblo Algorithm thg 12 22, 2023 8:00 SA
19 min read

Chia căn (phần 1) - Giới thiệu về Chia căn

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 ...

Thumbnail Image
2.2K
5
3 0
Avatar Viblo Algorithm thg 12 20, 2023 8:00 SA
22 min read

Các kĩ năng thi cử 10.1: Kĩ thuật tối ưu tốc độ chương trình C++

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,110,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...

Thumbnail Image
265
2
0 0
Avatar Viblo Algorithm thg 12 18, 2023 8:00 SA
12 min read

Quy hoạch động 5.5: Mảng tổng tiền tố và Mảng hiệu (phần 2)

Đây là bài viết số 21,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...
Thumbnail Image
847
2
0 0
Avatar Viblo Algorithm thg 12 15, 2023 8:00 SA
18 min read

Quy hoạch động 5.5: Mảng tổng tiền tố và Mảng hiệu (phần 1)

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...

Thumbnail Image
702
2
2 1
Avatar Viblo Algorithm thg 12 13, 2023 7:35 SA
18 min read

Sắp xếp và Tìm kiếm 2.1: Bài toán Sắp xếp và các giải thuật Sắp xếp thông dụng

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...

Thumbnail Image
2.0K
8
2 0
Avatar Viblo Algorithm thg 11 16, 2023 2:50 SA
21 min read

Thao tác xử lý bit và ứng dụng (Bit Manipulation)

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 01,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...

Thumbnail Image
557
3
0 0
Avatar Viblo Algorithm thg 11 15, 2023 5:48 SA
19 min read

Bài 14: Cấp phát bộ nhớ động và Danh sách liên kết (Phần 2) - Danh sách liên kết (Linked List)

Đâ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...

Thumbnail Image
676
3
0 0
Avatar Viblo Algorithm thg 11 15, 2023 5:44 SA
18 min read

Bài 14: Cấp phát bộ nhớ động và Danh sách liên kết (phần 1) - Kĩ thuật Cấp phát bộ 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...

Thumbnail Image
545
4
2 0
Avatar Viblo Algorithm thg 11 15, 2023 4:59 SA
18 min read

Bài 9: Con trỏ (phần 2) - Hoạt động nâng cao với con trỏ trong C++

Đâ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ê...

Thumbnail Image
3.5K
5
1 1
Avatar Viblo Algorithm thg 11 10, 2023 7:53 SA
20 min read

Quy hoạch động Bitmask

Để 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ì...

Viblo
Let's register a Viblo Account to get more interesting posts.