Hướng dẫn giải của Chép bài
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.
Tác giả:
Subtask ~1~ : ~1 \leq N \leq 1000~.
- Khi xét đến thí sinh thứ ~i~, ta có thể đánh dấu lại những thí sinh phía trước mà ~i~ có thể chép bài.
- Kiểm tra những thí sinh mà chưa bị đánh dấu.
- Độ phức tạp : ~O(N^2)~.
Subtask ~2~ : ~1 \leq N \leq 5 \times 10^5~.
- Khi xét đến thí sinh thứ ~i~, ta có thể kiểm tra xem liệu có thí sinh nào có thể chép bài của thí sinh ~i~ hay không bằng cách xét ngược từ ~N \to 1~ và kết hợp các cấu trúc dữ liệu.
- Độ phức tạp : ~O(NlogN)~.
Subtaks ~3~ : Không có ràng buộc gì thêm.
- Cách 1 : Ý tưởng giống subtask ~1~, ta có thể dùng mảng cộng dồn để đánh dấu thay vì dùng thêm một vòng lặp.
- Cách 2 : Ý tưởng giống subtask ~2~, ta có thể dùng 2 con trỏ để xét thay vì dùng CTDL.
- Độ phức tạp : ~O(N)~.
Bình luận