Thông tin
Sau đây là lời giải của Đề 5 trong chuỗi đề ôn tập TS10 & THTB 2025.
Bạn đọc có thể nộp và chấm bài TẠI ĐÂYs
Chuẩn bị bởi team Logica, thuộc khuôn khổ dự án The Algitect (ALGI Project)
Ta duyệt qua mọi bộ phần tử trong mảng rồi tìm giá trị lớn nhất của chúng.
Cách tính UCLN của ba số
__gcd(x, y)
Độ phức tạp thời gian: .
Với tượng trưng cho độ phức tạp của hàm
__gcd()
.
Nhận xét
Vì mà , nên kết quả của bài chắc chắn sẽ nhỏ hơn hoặc bằng .
Do đó, chúng ta có cách tiếp cận khác: Duyệt từng số và kiểm tra xem đó có phải của một bộ ba số bất kỳ trong mảng hay không.
Dễ thấy, nếu thì phải thỏa mãn:
Hay là ước chung của , tức là trong mảng tồn tại ít nhất số chia hết cho .
Để thực hiện được điều trên, ta gọi là số lượng số j có trong mảng , và số thỏa mãn điều kiện nếu với là bội của .
Giải thích
Mặc dù số thỏa mãn điều kiện trên chưa chắc là của .
Tuy nhiên, điều này không ảnh hưởng đến kết quả, vì ta sẽ lấy kết quả lớn nhất.
VD:
thỏa, đồng thời (đáp án chuẩn) cũng thỏa.
Độ phức tạp thời gian: với .
Với mỗi số từ đến , ta phải duyệt qua tất cả các bội của nó. Do đó số thao tác là:
Tip
Ta có thể tính như sau:
Tính bằng cách lấy chia nguyên cho 2: x = (r-l+1)/2;
Vì mảng đã được sắp xếp tăng dần, với mỗi truy vấn ta dễ dàng tính được trọng số của đoạn là . Sau đó chỉ cần so sánh giá trị này với .
Độ phức tạp thời gian:
Nhận xét
Ta không cần tính chính xác trọng số của đoạn.
Thay vào đó ta chỉ cần quan tâm trọng số của đoạn lớn hơn hay nhỏ hơn .
Để giá trị nhỏ thứ của đoạn lớn hơn hoặc bằng , thì mọi phần tử sau phần tử trên cũng phải lớn hơn hoặc bằng , tức là đoạn đó phải có ít nhất + 1 phần tử lớn hơn hoặc bằng .
VD: Đoạn có phần tử, . Để phần tử nhỏ thứ lớn hơn hoặc bằng thì mọi phần tử nhỏ thứ cũng phải lớn hơn hoặc bằng .
Như vậy, bài toán trở thành đếm số lượng số trong đoạn lớn hơn hoặc bằng . Dễ dàng thực hiện được điều này bằng cách gán:
Sau đó sử dụng mảng cộng dồn (prefix sum) để tính nhanh số lượng số trong đoạn.
Độ phức tạp thời gian: .
Nhận xét
Giá trị không thể lớn hơn phạm vi có đồng cỏ.
Như vậy, vì nên .
Ta có thể duyệt từng giá trị và kiểm tra xem giá trị này có hợp lệ hay không như sau:
Đi theo chiều dương của trục số, nếu ta đặt một con bò ở vị trí thì ta sẽ đặt con bò tiếp theo ở vị trí nhỏ nhất thỏa nhằm để dành những thảm cỏ ở xa hơn cho những con bò còn lại.
Để làm được như vậy, ta cần sắp xếp các đồng cỏ theo thứ tự tăng dần của đầu mút phải. Sau đó khởi tạo một con trỏ tại đồng cỏ đầu tiên tượng trưng cho vị trí để đặt bò, cùng lúc với việc đặt bò, ta sẽ di chuyển con trỏ từng chút một để tìm đồng cỏ gần nhất thỏa mãn điều kiện về khoảng cách.
Độ phức tạp thời gian: với là phạm vi có cỏ.
Kế thừa tư tưởng của subtask 1, tuy nhiên có thêm nhận xét quan trọng sau đây:
Nhận xét
Vì khoảng cách giữa hai con bò càng nhỏ thì số bò đặt được càng nhiều, ngược lại với khi khoảng cách càng lớn, nên:
Đây là điều kiện cần thiết để thực hiện tìm kiếm nhị phân trên tập đáp án. Thay vì phải duyệt hết mọi giá trị để thử, ta chỉ phải thử giá trị với là khoảng tối đa mà có tồn tại cỏ.
Độ phức tạp thời gian: .
Áp dụng quy hoạch động.
Định nghĩa:
Khởi gán:
Công thức (với ):
Kết quả: .
Độ phức tạp thời gian: