Thành phố Cuồng loạn

Giới thiệu Tài liệu này ghi lại quá trình học tập các thuật toán cơ bản từ khóa học của AcWing, bao gồm các chủ đề chính như sắp xếp nhanh, tìm kiếm nhị phân, tổng tiền tố, phép toán bit và thuật toán hai con trỏ. Sắp xếp nhanh (Quick Sort) Bài toán 1: Sắp xếp cơ bản #include <iostream> using namespace std; const int MAX_SIZE = 10001 ...

Problem A: Interval Coverage with Exclusions Given a sequence of operations on an integer range [p, q] (initially [1, 10^9]), each operation falls into one of three types: Type 1: increase the lower bound to max(current lower bound, k) Type 2: decrease the upper bound to min(current upper bound, k) Type 3: add value k to a list of excluded poin ...

Hôm nay ngoài hai kỹ thuật kinh điển là mảng tiền tố và mảng hiệu, chúng ta còn làm quen với một công cụ thiết yếu khi xử lý dữ liệu thưa: rời rạc hóa. Mảng tiền tố (Prefix Sum) Mảng tiền tố chủ yếu giải quyết các bài toán truy vấn đoạn không cập nhật, đặc biệt khi hàm truy vấn có tính chất khả trừ: giá trị trên đoạn [l, r] có thể suy ra từ g ...

Bài A: Tối ưu giá trị cuối cùng sau dãy phép toán Cho một mảng gồm n số nguyên phân biệt. Ta được thực hiện hai loại thao tác: Phép trừ: chọn hai phần tử x, y và thay bằng x - y. Phép lấy dư: chọn hai phần tử x, y và thay bằng x % y. Mục tiêu là thu được giá trị lớn nhất có thể sau khi thực hiện đúng n-1 thao tác. Nhận xét: Với phép tr ...