USACO 2025 - Min Max Subarrays
Xem PDFLưu ý: Giới hạn thời gian của bài này là 3 giây, bằng 1,5 lần mặc định.
Bạn được cho một mảng số nguyên độ dài \(N\) là \(a_1,a_2,\dots,a_N\) (\(2\le N\le 10^6\), \(1\le a_i\le N\)). Hãy in ra tổng đáp án của bài toán con dưới đây trên tất cả \(N(N+1)/2\) mảng con liên tiếp của \(a\).
Cho một danh sách số nguyên không rỗng, hãy luân phiên thực hiện các thao tác sau (bắt đầu bằng thao tác thứ nhất) cho đến khi danh sách có đúng một phần tử:
- Thay hai số nguyên liên tiếp trong danh sách bằng giá trị nhỏ nhất của chúng.
- Thay hai số nguyên liên tiếp trong danh sách bằng giá trị lớn nhất của chúng.
Hãy xác định giá trị lớn nhất có thể của số nguyên cuối cùng còn lại.
Ví dụ:
[4, 10, 3] -> [4, 3] -> [4]
[3, 4, 10] -> [3, 10] -> [10]
Trong mảng đầu tiên, \((10,3)\) được thay bằng \(\min(10,3)=3\) và \((4,3)\) được thay bằng \(\max(4,3)=4\).
Dữ liệu vào
Dòng đầu tiên chứa \(N\).
Dòng thứ hai chứa \(a_1,a_2,\dots,a_N\).
Dữ liệu ra
In ra tổng đáp án của bài toán con trên tất cả các mảng con.
Ví dụ
Ví dụ 1
Input
2
2 1Output
4Giải thích
Đáp án cho \([2]\) là \(2\), đáp án cho \([1]\) là \(1\), và đáp án cho \([2,1]\) là \(1\).
Vì vậy, kết quả cần in là \(2+1+1=4\).
Ví dụ 2
Input
3
3 1 3Output
12Ví dụ 3
Input
4
2 4 1 3Output
22Giải thích
Xét mảng con \([2,4,1,3]\).
- Áp dụng thao tác thứ nhất lên \((1,3)\), mảng mới là \([2,4,1]\).
- Áp dụng thao tác thứ hai lên \((4,1)\), mảng mới là \([2,4]\).
- Áp dụng thao tác thứ ba lên \((2,4)\), số cuối cùng là \(2\).
Có thể chứng minh \(2\) là giá trị lớn nhất có thể của số cuối cùng.
Phân nhóm
- Dữ liệu 4–5: \(N\le 100\).
- Dữ liệu 6–7: \(N\le 5000\).
- Dữ liệu 8–9: \(\max(a)\le 10\).
- Dữ liệu 10–13: Không có ràng buộc bổ sung.
Nguồn
USACO 2025 February Contest, Platinum — Min Max Subarrays. Tác giả: Benjamin Qi.
Kỳ thi:
- USACO 2025 - Tháng 2 - Hạng Bạch Kim (1 Tháng 2., 2025)
Bình luận