USACO 2025 - Making Mexes
Xem PDF
Điểm:
1000 (p)
Thời gian:
4.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho một mảng \(a\) gồm \(N\) số nguyên không âm \(a_1,a_2,\dots,a_N\) (\(1\le N\le 2\cdot 10^5\), \(0\le a_i\le N\)). Trong một thao tác, bạn có thể thay đổi bất kỳ phần tử nào của \(a\) thành một số nguyên không âm bất kỳ.
mex của một mảng là số nguyên không âm nhỏ nhất không xuất hiện trong mảng. Với mỗi \(i\) từ \(0\) đến \(N\), hãy tính số thao tác tối thiểu cần thiết để mex của \(a\) bằng \(i\).
Dữ liệu vào
Dòng đầu tiên chứa \(N\).
Dòng tiếp theo chứa \(a_1,a_2,\dots,a_N\).
Dữ liệu ra
Với mỗi \(i\) từ \(0\) đến \(N\), in trên một dòng riêng số thao tác tối thiểu ứng với \(i\). Lưu ý rằng luôn có thể làm cho mex của \(a\) bằng bất kỳ \(i\) nào từ \(0\) đến \(N\).
Ví dụ
Ví dụ 1
Input
4
2 2 2 0Output
1
0
3
1
2Giải thích
- Để mex của \(a\) bằng \(0\), ta có thể đổi \(a_4\) thành \(3\) (hoặc bất kỳ số nguyên dương nào). Trong mảng thu được \([2,2,2,3]\), \(0\) là số nguyên không âm nhỏ nhất không xuất hiện, nên \(0\) là mex của mảng.
- Để mex của \(a\) bằng \(1\), ta không cần thay đổi gì vì \(1\) đã là số nguyên không âm nhỏ nhất không xuất hiện trong \(a=[2,2,2,0]\).
- Để mex của \(a\) bằng \(2\), ta cần thay đổi ba phần tử đầu tiên của \(a\). Chẳng hạn, ta có thể đổi \(a\) thành \([3,1,1,0]\).
Phân nhóm
- Dữ liệu 2–6: \(N\le 10^3\).
- Dữ liệu 7–11: Không có ràng buộc bổ sung.
Nguồn
USACO 2025 February Contest, Bronze — Making Mexes. Tác giả: Benjamin Qi.
Kỳ thi:
- USACO 2025 - Tháng 2 - Hạng Đồng (1 Tháng 2., 2025)
Bình luận