1 năm, 6 tháng trước

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.

1 năm, 6 tháng trước

bro có thể cho em hỏi sub 2 bài VOMARIO làm thế nào với ạ??

a cho e xin tài liệu trie mà cài đặt trie dễ nhất với ạ, e search mà cài khó quá

1 năm, 6 tháng trước
Trả lời vodanhnam
  Hiện bài gốc

trie ở đây nè bạn

http://vnoi.info/library/121/4973/

1 năm, 6 tháng trước
Trả lời vodanhnam
  Hiện bài gốc

QHĐ O(N^2).

Code tham khảo:

vector<long long> dp(n + 1);
long long ans = 0;
for (int i = 1; i <= n; ++i) {
    dp[i] = -INF;
    for (int j = 0; j < i; ++j) if (dp[j] - w[j] * abs(x[i] - x[j]) >= 0)
        dp[i] = max(dp[i], dp[j] + e[i] - w[j] * abs(x[i] - x[j]));
    ans = max(ans, dp[i]);
}

 

1 năm, 6 tháng trước

Cho hỏi bài VOLAND : 
Bạn có thể chỉ rõ quay bảng 1 góc 45 độ là ntn không. Mình không code nổi

1 năm, 6 tháng trước

bạn ơi, bài VOMOVREC nhỡ trường hợp này thì sao bạn

mình có ba hình cn là hcn màu xanh đâm, đỏ, với cam

khi t=1 thì 3 tụi nó bung ra (màu lợt hơn) , những nơi 2 màu chồng lên thì mình có gạch ấy

theo thuật thì t=1 thì chúng đã giao nhau rồi, nhưng thực chất đâu đc nhỉ ?

1 năm, 6 tháng trước
Trả lời bacthosan
  Hiện bài gốc

Sau khi quay mảng MxN ta sẽ có một bảng vuông (M+N-1)

Ô (i,j) trong bảng ban đầu sẽ là ô (i+j-1,i-j+n) trong bảng mới.

1 năm, 6 tháng trước
Trả lời tsminh_3
  Hiện bài gốc

Ở đây giao nhau là có một ô nào đấy nằm trong tất cả các hình chữ nhật, bạn xem lại điều kiện max(X1) < min(X2) và max(Y1) < min(Y2).

Trong hình thì cái màu cam và màu xanh không giao nhau.

1 năm, 6 tháng trước
Trả lời ladpro98
  Hiện bài gốc

à, mình nhầm đề tý @@ thanks bạn :D

1 năm, 6 tháng trước

mình không hiểu "xoaybảng" là làm ntn ?

1 năm, 6 tháng trước
Trả lời ladpro98
  Hiện bài gốc

à em nhầm. ý em là sub3 bài VOMARIO làm ntn ạ??

1 năm, 6 tháng trước
Trả lời khangvinhc3
  Hiện bài gốc

Xoay bảng 45 độ mình đã giải thích cho bạn bacthosan ở trên.

Xoay bảng 90 độ tức là biến bản MxN thành NxM, hàng thành cột và cột thành hàng.

1 năm, 6 tháng trước
Trả lời vodanhnam
  Hiện bài gốc

Nếu bạn biết cách sử dụng BIT (hoặc IT) thì có thể giải được subtask này khá đơn giản. Để tính F(i) ta sử dụng 2 cây BIT truy vấn sang trái và sang phải của x[i]. Cách làm tương tự như bài BGMINE.

1 năm, 6 tháng trước

Bài VOROOM tôi có solution như sau: (tôi xin được thuật lại chi tiết quá trình giải)

Đầu tiên, khi đang làm subtast 2, tôi nhận thấy rằng trong các lần tìm cặp ghép cực đại, N lần DFS đầu đều cho cặp ghép giống nhau, không phụ thuộc vào cạnh thêm vào. Vì vậy ta có thể lưu lại cặp ghép ban đầu (khi chưa thêm cạnh) và dùng lại cho tất cả các lần sau. Tiếp theo, tôi thấy rằng chỉ cần thêm 1 cạnh là đủ, vì nếu thêm cạnh đó mà tồn tại cặp ghép đầy đủ thì cạnh thứ 2 có thể chọn bất kì trong N cạnh còn lại. Đến lúc này ta chỉ cần DFS để xem trong các phòng đã ghép có bao nhiêu phòng có đường mở đến phòng chưa ghép, gọi con số này là X, kết quả của bài toán là N*X-(X-1)*X/2.

Để tìm cặp ghép với N=10^5 có thể dùng thuật toán Kopcroft-Karp.

1 năm, 6 tháng trước
Trả lời Anonymous
  Hiện bài gốc

Cảm ơn bạn đã chia sẻ ý tưởng. Mình thấy thuật toán này tự nhiên hơn solution của tác giả.

1 năm, 6 tháng trước
Trả lời Anonymous
  Hiện bài gốc

Em là newbie, anh có thể nói rõ thuật toán Hopcroft-Karp được không ạ?

1 năm, 6 tháng trước
Trả lời anhvu_cbl
  Hiện bài gốc

Ở mỗi bước ta bỏ các đỉnh bên X chưa ghép vào hàng đợi, BFS để tìm đường mở (nhiều đường mở), sau khi BFS xong thì tiến hành tăng cặp ghép như thuật toán bình thường. Độ phức tạp xấu nhất là \(O(M\sqrt{N})\). Nói ngắn gọn thì thuật toán là vậy.

1 năm, 6 tháng trước

code bài movrec của mình rất đơn giản:

tìm xmax, ymax, umin, vmin (x,y:góc trái dưới);

rồi lấy max (abs(xmax-umin),abs(ymax-vmin))

kq=max div 2 +1

1 năm, 6 tháng trước

Cho mình hỏi bài  VOLAND

Phần duyệt đường thẳng cắt 2 hình là đường xin góc 45 độ code như nào. Khó quá mình code mãi không ra.
tks bạn

1 năm, 6 tháng trước
Trả lời ladpro98
  Hiện bài gốc

a có thể nó rõ dùng BIT (hoặc IT) sub3 bài này ko ạ. a nói em vẫn chưa hiểu ?