Hướng dẫn giải của Tình tay ba


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.

Với giới hạn ~n \le 100~, chúng ta có thể sử dụng ~3~ vòng lặp để kiểm tra: với ba con bò ~i, j, k~ khác nhau, chúng sẽ tạo thành mối tình tay ba nếu ~p[i] = j~, ~p[j] = k~ và ~p[k] = i~. Độ phức tạp của cách làm này là ~O(n^3)~.

Ngoài ra, chúng ta có thể làm nhanh hơn bằng cách kiểm tra từng con bò: xét con bò thứ ~i~, đặt ~j = p[i]~, ~k = p[j]~, ~l = p[k]~; khi đó, con bò ~i~ sẽ nằm trong mối tình tay ba nếu ~l = i~; hay ngắn gọn hơn, chúng ta có thể kiểm tra điều kiện ~p[p[p[i]]] = i~. Độ phức tạp của cách làm này là ~O(n)~.


Bình luận

Hãy đọc nội quy trước khi bình luận.


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