Hướng dẫn giải của Dream Land
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Gợi ý
Subtask ~1~:
- Duyệt qua tất cả các đoạn con liên tiếp có độ dài ~k~.
- Với mỗi đoạn con có độ dài ~k~, duyệt qua các phần tử để đếm số loại vé (có thể sử dụng mảng hoặc
set). - Độ phức tạp: ~O(n*k).
Subtask ~2~:
- Áp dụng kĩ thuật hai con trỏ để tính được số loại vé trong đoạn con có độ dài ~k~.
- Lưu ý: vì có nhiều test nên khi đặt lại giá trị ban đầu của mảng đánh dấu ta không nên đặt lại tất cả mảng mà chỉ đặt lại các phần tử xuất hiện trong mảng.
- Độ phức tạp: ~O(n)~.
Bình luận