trang chủ / bài tập / goodcycl / lời giải

Dịch Vòng Tốt

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.

Tác giả:

huunguyen

Lời giải: Good Cyclic Shifts

Hướng tiếp cận

Hoán vị $p$ là tốt khi và chỉ khi $p$ tránh dãy con $321$ (không tồn tại $i < j < k$ sao cho $p_{i} > p_{j} > p_{k}$ ).

Thuật toán O(N)

Tìm phần tử lớn hơn gần nhất bên trái (theo vòng): dùng monotonic stack.
Tìm phần tử nhỏ hơn gần nhất bên phải (theo vòng): tương tự với stack ngược.
Với mỗi phần tử $i$ , nếu cả hai tồn tại và tạo thành mẫu $321$ , đánh dấu khoảng các phép dịch bị cấm bằng mảng hiệu.
Tính prefix sum và liệt kê các phép dịch không bị cấm.

Độ phức tạp

Thời gian: $O (N)$
Bộ nhớ: $O (N)$

Bình luận

Không có bình luận tại thời điểm này.