Kỳ thi VOI 2016 đã kết thúc.
Bài 1:
Nhận xét:
- Có thể sort lại dãy
- Có thể chọn tất cả các số bằng nhau.
Như vậy đầu tiên chúng ta có thuật N*2^10 hồn nhiên như sau:
- Sort lại, gộp các số bằng nhau lại thành 1.
- Đặt F(i, mask) = độ dài dãy lớn nhất nếu ta chọn các số từ A1 --> Ai, mask là dãy bit độ dài 10. Trong 10 số Ai, A(i-1), A(i-2)... thì ta chỉ chọn các số có trong mask. Gọi tập các số đc chọn trong 10 số đó là S(mask). Từ F(i, mask) ta tính đc F(i+1, mask'). Để kiểm tra thỏa mãn tính chất đề bài thì ở trạng thái (i+1, mask') cần xét xem có 2 số nào trong S(mask') mà có hiệu là 1, 8 hoặc 9 hay không.
Bài 2:
(Theo bạn bvd);
Nhận xét:
- Cách vận chuyển tiết kiệm xăng nhất là vận chuyển toàn bộ lượng xăng có thể ở bể chứa trước đến bể chứa sau
Từ đó thu đc thuật toán với độ phức tạp L/D
Bài 3:
-_-
Bài 4:
Chia hình thoi thành 4 tam giác vuông.
F1(i, j) = độ dài cạnh lớn nhất của tam giác vuông có đỉnh góc vuông là (i, j) và 2 cạnh của nó hướng lên trên và sang trái.
Như vậy:
- F1(i, j) = 0 nếu ô (i, j) và (i-1, j) hoặc (i, j-1) có cọc.
- Ngược lại F1(i, j) = 1 + max(F1(i-1, j), F1(i,j-1))
Tương tự tính 4 tam giác 4 hướng: F1, F2, F3, F4.
Sau đó ở (i, j) thì hình thoi lớn nhất có tâm ở (i, j) là min(F1(i,j), F2(i,j), F3(i,j), F4(i,j))
Bài 5:
Với mỗi biểu thức sinh tất cả các giá trị có thể có ra. Sau đó làm cặp ghép.
Để ko phải xử lý số lớn thì cứ tính tràn số 64 bit. Nếu sợ sai thì tính thêm giá trị MOD 10^9 + 7.
Bài 6:
(Lời giải bởi Kiên IOI 2015)
Bài này có 2 bước:
- Với mỗi cây, cần tính xem là nếu nó đổ sang trái (hoặc sang phải), thì đổ đến tối đa là bao nhiêu. Đặt 2 cái này là Fright(i) và Fleft(i).
- Sau khi có Fleft(i) và Fright(i), xét 2*N đoạn: [Fleft(i), i] và [i, Fright(i)]. Bài toán đưa về chọn ra ít đoạn nhất sao cho phủ đc tất cả 1..N và ko có 2 đoạn nào có điểm chung (để tránh chọn cả 2 cái left và right của i).
Bước 1:
- Với mỗi i, Fright(i) = max(Fright(i+1).. Fright(i+Hi)).
- Như vậy có thể tính đc bằng BIT hoặc IT --> O(N*logN)
- Ngoài ra có thể tính O(N) dùng stack như sau:
- Ở i ta duy trì 1 stack chứa tất cả các giá trị có thể dùng để cập nhật cho Fright(i).
- Rõ ràng, nếu i < j và Fright(i) > Fright(j) thì j vô dụng, nên ta có thể vứt ra khỏi stack.
- Như vậy, trong stack, nếu có i < j thì Fright(i) < Fright(j)
- Ở i, đầu tiên loại những j ở đỉnh của stack, vừa loại vừa cập nhật Fright(i). Quá trình này dừng lại khi có Fright(i) < đỉnh stack < Fright(đỉnh stack). Cuối cùng ta thêm i vào stack, thì vẫn đảm bảo tính chất nêu trên.
- Mỗi đỉnh vào stack và ra khỏi stack 1 lần, nên đpt là O(N).
Bước 2 thì các đoạn rời nhau, nên ta có thể QHD trong O(N) khá đơn giản.
