Link các bài viết C++ cơ bản của thầy giáo được đính kèm ở từng bài! Bài 1: Giới thiệu Lập trình thi đấu và ngôn ngữ lập trình C++ (1b) 1.1. Giới thiệu môn học Lập trình thi đấu. 1.2. Khái niệm về chương trình và lập trình. 1.3. Giới thiệu ngôn ngữ lập trình C++. 1.4. Cài đặt phần mềm Code::Blocks và tạo chương đầu tiên. 1.5. Cấu trúc một chương trình C++. 1.6. Toán tử số học và Toán hạng. 1.7. Một số loại toán tử khác trong C++ (đọc thêm).

image

Trong lập trình nói chung và lập trình thi đấu nói riêng, kĩ thuật hai con trỏ (two pointers) là một kĩ thuật rất hiệu quả để giải quyết các bài toán trên mảng hoặc chuỗi. Kĩ thuật này giúp tiết kiệm không gian lưu trữ, giảm thời gian chạy của giải thuật rất hiệu quả. Vậy kĩ thuật hai con trỏ là gì? Đúng như tên gọi của nó, kĩ thuật này sử dụng hai con trỏ đồng thời để kiểm soát hai vị trí trên mảng hoặc chuỗi. Tuy nhiên khác với khái niệm con trỏ mà chúng ta thường biết (là một biến trỏ vào địa chỉ trong bộ nhớ máy tính của một đối tượng), con trỏ trong kĩ thuật này chỉ đơn giản là những biến kiểm soát vị trí trên mảng hoặc chuỗi, trong đó có một biến luôn luôn không vượt quá biến còn lại. Hình vẽ dưới đây là một minh họa: image Trong rất nhiều bài toán trên mảng hoặc chuỗi, chúng ta sẽ phải quét qua các cặp giá trị, hoặc những đoạn liên tiếp trên dãy số. Nếu như sử dụng những vòng lặp lồng nhau, hoặc kết hợp các cấu trúc dữ liệu để kiểm soát các đoạn giá trị thì thời gian chạy của giải thuật sẽ không thể đảm bảo. Vậy giải pháp là gì? Chính là kĩ thuật two pointers - một giải pháp vừa tiết kiệm không gian lưu trữ, vừa giảm thời gian thực thi của giải thuật (thông thường xuống $O(n)$). Khi sử dụng two-pointers, thay vì chỉ truy cập được một phần tử của dãy, ta sẽ truy cập được đồng thời hai phần tử của dãy ở mỗi lần lặp, qua đó giảm số thao tác cần thực hiện đi rất nhiều. Kĩ thuật này có thể chia làm ba dạng thường gặp:

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 $\text{GCD}$ 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à $O(n),$ thường dẫn đến lỗi TLE trong các bài toán multi-testcase. Chia căn (Squaroot Decomposition) chính là một phương pháp (hay cấu trúc dữ liệu) hiệu quả để hỗ trợ các thao tác trên giảm độ phức tạp xuống còn $O(\sqrt{n}),$ nhanh hơn rất nhiều so với thuật toán duyệt thông thường. Trong bài viết này, tôi sẽ giới thiệu tới các bạn dạng đơn giản nhất của kĩ thuật này: Chia mảng ra làm $\sqrt{n}$ khối (blocks), thường dùng để giải quyết các bài toán truy vấn đoạn. Ta sẽ cùng phân tích một bài toán kinh điển để hiểu rõ hơn về ý tưởng của phương pháp này: "Cho một mảng $A$ gồm $n$ phần tử $a_1, a_2, \dots, a_n$. Hãy xây dựng một cấu trúc dữ liệu để tìm ra tổng của đoạn con $[l, r]$ bất kì chỉ trong $O(\sqrt{n})?$" Input: