Hướng dẫn giải của [PTNK - TS10 - 2025] Bài 1: STREAK
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 viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Tóm tắt đề bài
Cho dãy gồm ~n~ xâu, mỗi xâu chỉ có dạng là ONLINE hoặc OFFLINE hoặc IDLE. Hãy tìm dãy các xâu liên tiếp dài nhất, mà các xâu trong đó đều là ONLINE.
Giới hạn: ~n \le 1440~.
Lời giải
Ta duy trì hai biến:
- ~cur~ là độ dài của dãy con kết thúc tại vị trí ~i~ đang xét, mà toàn bộ là xâu
ONLINE. Dễ thấy, nếu xâu thứ ~i~ không phải làONLINE, thì ~cur = 0~. - ~res~ là kết quả hiện tại. Ta thực hiện thuật toán như sau: với mỗi xâu ~i~:
- Nếu xâu thứ ~i~ là
ONLINE, đương nhiên ~cur~ cộng thêm ~1~, do ta có thêm một xâu. - Ngược lại, ~cur = 0~, vì dãy con liên tiếp hiện tại không còn toàn bộ là
ONLINEnữa. - Để tránh sai sót, dù vào trường hợp nào, ta đều cập nhật ~res = max (res, cur)~.
Độ phức tạp: ~O~ ~(n)~.
Bình luận