Loại bỏ các đỉnh thuộc các chu trình sau đó đếm là đc bạn ơi :) O(n)

Cách làm bài 3 của em, hy vọng là không sai T.T:

Xét đồ thị 2 phía (các sửu nhi, các phòng), với mỗi TPLT, tính cU là số đỉnh bên trái, cV là số đỉnh bên phải. Vì là một TPLT nên hiển nhiên 2cU >= cU + cV - 1 (số cạnh >= số đỉnh - 1) ==> cU >= cV - 1.

Nếu cU > cV thì kết quả là 0, vì số phòng ít hơn số người.

Nếu cU = cV thì kệ nó.

Nếu cU = cV - 1: kết quả là cV * (n + 1 - cV) + cV(cV - 1)/2 (hoặc chọn 1 đỉnh trong TPLT này, 1 đỉnh ở TPLT khác hoặc chọn 2 đỉnh trong TPLT).

Mong các cao thủ nhận xét giúp em T.T

Sao đề năm nay khó thế nhỉ? :< Em không làm full được bài nào :( 

Bài 1 em làm thế này không biết có đúng không: Tìm max(xi), min(xi), max(yi), min(yi). Rồi tính trung bình cộng sau đó tính xem cần bao nhiều bước để di chuyển đến hv có tọa độ (i,j) (i+1,j+1).

Bài 2 em chịu, chỉ vét O(n^2logn). :V

Bài 3 em dùng for trâu+ cặp ghép và đếm. :v

Cách làm bài 3 của em, hy vọng là không sai T.T:

Xét đồ thị 2 phía (các sửu nhi, các phòng), với mỗi TPLT, tính cU là số đỉnh bên trái, cV là số đỉnh bên phải. Vì là một TPLT nên hiển nhiên 2cU >= cU + cV - 1 (số cạnh >= số đỉnh - 1) ==> cU >= cV - 1.

Nếu cU > cV thì kết quả là 0, vì số phòng ít hơn số người.

Nếu cU = cV thì kệ nó.

Nếu cU = cV - 1: kết quả là cV * (n + 1 - cV) + cV(cV - 1)/2 (hoặc chọn 1 đỉnh trong TPLT này, 1 đỉnh ở TPLT khác hoặc chọn 2 đỉnh trong TPLT).

Mong các cao thủ nhận xét giúp em T.T

tư tưởng lớn gặp nhau ở bài 1 rồi

Cách làm bài 3 của em, hy vọng là không sai T.T:

Xét đồ thị 2 phía (các sửu nhi, các phòng), với mỗi TPLT, tính cU là số đỉnh bên trái, cV là số đỉnh bên phải. Vì là một TPLT nên hiển nhiên 2cU >= cU + cV - 1 (số cạnh >= số đỉnh - 1) ==> cU >= cV - 1.

Nếu cU > cV thì kết quả là 0, vì số phòng ít hơn số người.

Nếu cU = cV thì kệ nó.

Nếu cU = cV - 1: kết quả là cV * (n + 1 - cV) + cV(cV - 1)/2 (hoặc chọn 1 đỉnh trong TPLT này, 1 đỉnh ở TPLT khác hoặc chọn 2 đỉnh trong TPLT).

Mong các cao thủ nhận xét giúp em T.T

bài 2 làm thế nào nhỉ, ai biết chỉ mình với :D

Bài này dùng trie, mỗi số coi như là một xâu nhị phân độ dài 32. Xây dựng cây trie của n xâu.

Bình thường khi truy vấn tìm phần từ thứ k thì sẽ duyệt từ gốc, đếm số con ở nút trái (0) nếu nó >= k thì rẽ trái, ngược lại rẽ phải. Ở bài này có thêm xor nên có lúc làm ngược: đếm số con ở nút phải, nếu nó >= k thì rẽ phải, ngược lại rẽ trái.

a không hiểu :-?

bài 1 với 2 còn bài 3 chưa đok
Bài 1 Nghĩ theo kiểu loang nên dùng chặt nhị phân rồi kiểm tra
Bài 2 Trie