Lời giải các bài VOI 2016

Forum VNOI đã tạm ngừng hoạt động. Các bạn có thể hỏi bài trên Group Facebook của bọn mình.

8 năm, 3 tháng trước

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:

Cách vận chuyển tiết kiệm xăng nhất là vận chuyển toàn bộ lượng xăng có 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.

▲

▼

abcdef6199

8 năm, 3 tháng trước

Trả lời RR
Hiện bài gốc

Em nghĩ là ra 2 chứ ạ. Đề nói là cưa lần lượt mà anh, nên nó đổ rồi thì làm sao đổ lần 2 được nữa ạ.

▲

▼

ladpro98

8 năm, 3 tháng trước

Mình đã code lại solution O(N) cho bài DONCAY dựa trên ý tưởng của bạn Vương Hy (đã comment ở trên).

#include <bits/stdc++.h>
using namespace std;

const int N = 4e6 + 6;

int n;
int a[N];
int L[N], R[N];
int dp[N], trace[N];

void initialize() {
    vector<int> S;
    for (int i = 1; i <= n; ++i) {
        L[i] = i;
        while (!S.empty() && S.back() > i - a[i]) L[i] = min(L[i], L[S.back()]), S.pop_back();
        S.push_back(i);
    }
    S.clear();
    for (int i = n; i >= 1; --i) {
        R[i] = i;
        while (!S.empty() && S.back() < i + a[i]) R[i] = max(R[i], R[S.back()]), S.pop_back();
        S.push_back(i);
    }
}

void solve() {
    for (int i = 1; i <= n; ++i) dp[i] = i, trace[i] = -i;
    vector<int> S;
    for (int i = 1; i <= n; ++i) {
        if (dp[i] > dp[L[i] - 1] + 1) dp[i] = dp[L[i] - 1] + 1, trace[i] = -(L[i]);
        while (!S.empty() && R[S.back()] < i) S.pop_back();
        if (!S.empty() && dp[i] > dp[S.back() - 1] + 1) {
            dp[i] = dp[S.back() - 1] + 1;
            trace[i] = S.back();
        }
        if (S.empty() || (dp[S.back() - 1] > dp[i - 1])) S.push_back(i);
    }
    cout << dp[n] << endl;
    for (int i = n; i; i = abs(trace[i]) - 1) cout << (trace[i] < 0 ? -i : trace[i]) << ' ';
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    initialize();
    solve();
}