hjxhjx, nghe tren vnoi vo nguoi AC 8 bai noi giai thuat, toan la nhung cai ma khong the nao ngo toi T_T
Bài D: đơn giản chỉ là trâu bò. Bạn cần viết hàm cắt 1 đa giác thành 2 đa giác nhỏ hơn và giữ lấy phần chứa trạm nghiên cứu.
Bài C: việc khó nhất là tính trọng số các cạnh còn lại thì rất đơn giản.
tính trọng số thì copy nguyên si phần cắt đa giác ở bài D lại là có thể tính được trọng số rồi.
Bài E:
Quy hoạch động F[i, j] là cách sắp xếp tốt nhất cho i từ đầu tiên trên j dòng.
F[i, j] = min(F[k, j - 1] + (độ xấu đoạn từ k + 1 đến i) )
Độ phức tạp trên lý thuyết là 1000^2 * 100 nhưng chạy tương đối nhanh
Bài F:
Dijkstra heap 2 lần.
Lần 1: tính khoảng cách min từ S -> mọi đỉnh khác
Lần 2: đảo ngược chiều của các cung, dijkstra từ T. Ta sẽ tính được khoảng cách min từ mọi đỉnh tới T.
For các cạnh được xét để thêm vào và tìm kết quả.
Độ phức tạp: MlogN + K
Bài G: bó tay
Bài H:
Đầu tiên tìm bao lồi của 2 tập điểm. Dễ dàng nhận thấy khoảng cách xa nhất là khoảng cách giữa 2 điểm thuộc bao lồi của 2 tập này.
Đến đây có 2 cách làm:
- For trâu. (trên lý thuyết là N^2) nhưng thực tế lại chạy khá nhanh vì số điểm trên bao lồi ít. Các bạn sẽ nhận thấy điều này nếu các bạn thử sinh 1 đa giác lồi với giới hạn -10000 10000 xem được bao nhiêu điểm.
- Có cách O(NlogN) khác. Khi xét mỗi điểm thuộc bao lồi 1, kc tới các điểm thuộc bao lồi thứ 2 sẽ tạo thành hàm lồi. Ta có thể tìm được điểm xa nhất.
Bài I:
Bài này quy hoạch động F[b,g,k,t] là số cách để sắp xếp b nam, g nữ, k hướng dẫn viên và người đi cuối cùng là t.
Công thức của F tương đối dài nhưng không quá khó, các bạn thử viết ra xem.
Trang Chính 
Latest images 
Đăng ký 
Đăng Nhập 
Tiêu đề: Đề thi ACM 2008 (Tiếng Việt) 
27.11.08 16:50
