Mình có note lại solution của các bài VNOI Online 2016, các bạn có thể tham khảo.
Bài VOMOVREC:
Cần cực tiểu hóa khoảng cách di chuyển max của các hình nhữ nhật. Ta sẽ tìm kiếm nhị phân kết quả của bài toán. Với mỗi giá trị chia nhị phân V, ta sẽ “nở” các hình chữ nhật ra về bốn phía một độ dài bằng V. Lúc này điều kiện cần và đủ để tất cả các hình chữ nhật ban đầu có thể di chuyển với khoảng cách không quá V thỏa mãn yêu cầu là tất cả các hình chữ nhật đã được nở có phần giao. Điều kiện N hình chữ nhật có phần giao chung hay không là max(X1) < min(X2) và max(Y1) < min(Y2).
Bài VOXOR:
Bài này yêu sử dụng kiến thức về Trie. Mỗi số có thể coi như một xâu nhị phân 31 bit (vì 10^9 < 2^31). Sau khi chèn các xâu nhị phân vào cây Trie, với mỗi node của cây ta tính thêm trường size là số lá trong gốc cây con. Dựa vào trường size này ta dễ dàng thực hiện truy vấn tìm số hạng thứ K, việc này có thể thực hiện tương tự như việc tìm kiếm một node trên cây BST, ta sẽ đi từ gốc xuống lá, tại mỗi node thì nếu k <= size(cây con trái) thì ta nhảy sang trái, nếu không thì nhảy sang phải và cộng kết quả thêm một lượng lũy thừa 2 tương ứng với độ sâu của node hiện tại.
Để xử lí truy vấn xor tất cả các số, ta chỉ việc quản lí thêm một mảng flipped[] ở mỗi độ cao. Phép xor với X chỉ đơn giản là thay đổi trạng thái của flipped[] ở những vị trí bit 1 của X.
Bài VOROOM: Solution của chính tác giả: https://docs.google.com/document/d/1lKJl227zaFexMjEVPeoD5HP1bXRkGtOcLtf4n8U9dv8/edit?usp=sharing
Bài VOGAME:
Dựa theo luật chơi có thể phát hiện ra một bất biến: “tính chẵn lẻ của số bi màu đỏ là không đổi”. Vì vậy nến kết quả của bài toán chính là số bi màu đỏ modulo 2 !!! Để giải quyết trọn vẹn bài toán ta chỉ cần để ý là dãy A được sinh ra theo quy tắc trong đề tuẩn hoàn theo chu kỳ (D+1), nhờ vậy có thể tính ra số bi đỏ trong O(D).
Bài VOLAND:
Cá nhân mình thấy bài này thuật toán không có gì khó, tuy nhiên để cài đặt chính xác trong thời gian hạn hẹp thì không đơn giản.
Bài này sử dụng kỹ thuật mảng cộng dồn 2D để có thể truy vấn nhanh tổng của một hình chữ nhật trong O(1). Để tính nhanh tổng của một hình thoi thì ta quay bảng một góc 45 độ (nhìn theo đường chéo), và hình thoi sẽ trở thành hình chữ nhật.
Bước tiếp theo là ta sẽ for các đường cắt của hai hình (vì hai hình rời nhau nên sẽ tồn tại đường thẳng mà hai hình nằm trên hai nửa mặt phẳng). Các đường cắt cần thiết có thể nằm ngang, nằm dọc, hoặc xiên góc 45 độ. Ta sẽ giải quyết trường hợp đường cắt nằm ngang, trong đó hình chữ nhật ở trên, còn hình thoi ở dưới, các trường hợp khác tương tự: Tạo mảng Up[], Down[] trong đó Up[i] là hình chữ nhật có tổng lớn nhất nằm gọn trong khoảng từ hàng 1 đến hàng I, tương tự Down[i] là hình thoi max gọn trong khoảng hàng i đến hàng m. Kết quả của trường hợp này sẽ là max(Up[i] + Down[i+1]).
Để code được gọn thì ta chỉ cần giải quyết một số trường hợp cơ sở, rồi lần lượt quay bảng 90 độ và sử dụng lại code.
Bài VOMARIO:
Sử dụng Interval Tree để quản lí tập các đoạn thẳng. Có thể dễ dàng tìm được công thức QHĐ O(N^2) với F(i) = số năng lượng max đến lượt chơi thứ i. Để giảm độ phức tạp thì có thể dùng IT để cập nhật nhanh.
Chi tiết ở bài này có thể đọc comment trên forum VNOI.
