Hướng dẫn cho LQDOJ CUP 2022 - Round 7 - SETSEQ

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: kitsune

Subtask \(1\) (\(20\%\) số điểm): \(n \leq 15\).

Tutorial

Xây dựng một tập hợp như đề yêu cầu sau đó sắp xếp lại. Sau đó tìm dãy \(b\) trong tập hợp và in ra vị trí của nó.
Độ phức tạp: \(\mathcal{O}(2^n \times n^2)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500005;

int n;
int a[MAX_N];
vector<int> c;
vector<vector<int> > all;

void backtrack(int i) {
    if (i == n + 1) {
        if (!c.empty()) {
            all.push_back(c);
        }
        return;
    }

    backtrack(i + 1);
    c.push_back(a[i]);
    backtrack(i + 1);
    c.pop_back();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("SETSEQ.inp", "r", stdin);
    freopen("SETSEQ.out", "w", stdout);

    int m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<int> b(m);
    for (auto &x : b) {
        cin >> x;
    }

    backtrack(1);

    sort(all.begin(), all.end());
    all.resize(distance(all.begin(), unique(all.begin(), all.end())));

    for (int i = 0; i < (int)all.size(); i++) {
        if (b == all[i]) {
            cout << i + 1 << "\n";
            return 0;
        }
    }

    cout << -1 << "\n";

    return 0;
}

Subtask \(2\) (\(25\%\) số điểm): \(n \leq 5 \times 10^3\) và tất cả số nguyên trong dãy \(a\) đôi một phân biệt.

Tutorial

Để kiểm tra xem dãy \(b\) có phải là dãy con của \(a\) hay không, ta có thể dùng hai con trỏ \(i\) và \(j\) (con trỏ \(i\) trên dãy \(a\) và con trỏ \(j\) trên dãy \(b\)). Với mỗi vị trí \(j\) từ \(1\) đến \(m\), ta sẽ tìm vị trí \(i\) nhỏ nhất mà dãy \(b_{1\ldots j}\) là một dãy con của dãy \(a_{1\ldots i}\) bằng cách dịch \(i\) từ trái qua phải cho đến khi tìm thấy. Sau đó, đặt \(pos_j = i\) (sẽ dùng sau này). Nếu \(i\) không tồn tại thì đồng nghĩa với việc dãy \(b\) không phải là dãy con của dãy \(a\).
Thay vì tìm vị trí của dãy \(b\), ta sẽ tìm số lượng dãy con \(c\) của \(a\) và có thứ tự từ điển nhỏ hơn dãy \(b\) xong cộng thêm \(1\).
Các trường hợp xảy ra là:

\(c\) là một tiền tố của \(b\) (\(c \neq b\)): Trong trường hợp này, số lượng dãy \(c\) thỏa mãn là \(m - 1\).
Tồn tại một vị trí \(i\) (\(1 \leq i \leq \min(|c|, |b|)\)) mà với mọi \(j\) (\(1 \leq j < i\)) \(c_j = b_j\) và \(c_i < b_i\): Ta sẽ duyệt các vị trí \(i\) này tăng dần từ \(1\) đến \(m\). Gọi \(f_j\) là số lượng dãy con phân biệt của dãy \(a\) mà bắt đầu tại vị trí \(j\). Vì trong subtask này, các số nguyên trong dãy \(a\) đôi một phân biệt, nên ta dễ dàng có được \(f_j = 2^{n - j + 1}\). Vậy số lượng dãy \(c\) thỏa mãn là \(\displaystyle \sum_{j = pos_{i - 1} + 1}^{n} f_{j + 1}\) với \(a_j < b_i\) (mặc định \(pos_0 = 0\)).

Đáp án sẽ là tổng số lượng dãy con thỏa mãn trong các trường hợp trên.
Độ phức tạp: \(\mathcal{O}(n \times m)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500005;
const int MOD = 1e9 + 7;

int n, m;
int a[MAX_N], b[MAX_N];
int pos[MAX_N], pw2[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("SETSEQ.inp", "r", stdin);
    freopen("SETSEQ.out", "w", stdout);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    bool chk = false;
    pos[0] = 0;
    for (int i = 1, j = 1; i <= n; i++) {
        if (a[i] == b[j]) {
            pos[j] = i;
            if (++j == m + 1) {
                chk = true;
                break;
            }
        }
    }

    if (!chk) {
        cout << -1 << "\n";
        return 0;
    }

    pw2[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw2[i] = pw2[i - 1] * 2 % MOD;
    }

    int ans = m;
    for (int i = 1; i <= m; i++) {
        for (int j = pos[i - 1] + 1; j <= n; j++) {
            if (a[j] < b[i]) {
                (ans += pw2[n - j]) %= MOD;
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

Subtask \(3\) (\(15\%\) số điểm): Tất cả số nguyên trong dãy \(a\) đôi một phân biệt.

Tutorial

Vì dãy \(pos\) tăng dần nên ta có thể quản lý các vị trí \(j\) thỏa mãn bằng Fenwick tree. Để dễ xử lý, ta có thể duyệt ngược từ phải qua trái, đến vị trí \(j\) nào, ta sẽ tăng giá trị tại vị trí \(a_j\) trên cây thêm \(f_{j + 1}\). Đến vị trí \(i\) nào, ta sẽ cộng đáp án với những giá trị tại những vị trí nhỏ hơn \(b_i\) trên cây.
Độ phức tạp: \(\mathcal{O}((n + m) \times \log n)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500005;
const int MOD = 1e9 + 7;

int tree[MAX_N];

void update(int pos, int val) {
    for (int i = pos; i < MAX_N; i += i & -i) {
        (tree[i] += val) %= MOD;
    }
}

int query(int pos) {
    int res = 0;
    for (int i = pos; i > 0; i -= i & -i) {
        (res += tree[i]) %= MOD;
    }

    return res;
}

int n, m;
int a[MAX_N], b[MAX_N];
int pos[MAX_N], pw2[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("SETSEQ.inp", "r", stdin);
    freopen("SETSEQ.out", "w", stdout);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    bool chk = false;
    pos[0] = 0;
    for (int i = 1, j = 1; i <= n; i++) {
        if (a[i] == b[j]) {
            pos[j] = i;
            if (++j == m + 1) {
                chk = true;
                break;
            }
        }
    }

    if (!chk) {
        cout << -1 << "\n";
        return 0;
    }

    pw2[0] = 1;
    for (int i = 1; i <= n; i++) {
        pw2[i] = pw2[i - 1] * 2 % MOD;
    }

    int ans = m;
    for (int i = m, j = n; i >= 1; i--) {
        while (j >= pos[i - 1] + 1) {
            update(a[j], pw2[n - j]);
            j--;
        }

        (ans += query(b[i] - 1)) %= MOD;
    }

    cout << ans << "\n";

    return 0;
}

Subtask \(4\) (\(25\%\) số điểm): \(n \leq 5 \times 10^3\).

Tutorial

Ý tưởng cũng giống subtask 2 nhưng ta cần loại bỏ các trường hợp lặp.
Số lượng dãy con phân biệt của dãy \(a\) mà bắt đầu tại vị trí \(j\) lúc này là \(f_j = 2\times f_{j + 1} - f_{last_{a_j} + 1}\), trong đó \(last_{a_j}\) là vị trí \(k\) nhỏ nhất sao cho \(j < k \leq n\) và \(a_k = a_j\). Nếu không tồn tại \(last_{a_j}\) thì ta sẽ không tính \(f_{last_{a_j} + 1}\) vào \(f_j\).
Số lượng dãy \(c\) thỏa mãn lúc này là \(\displaystyle \sum_{j = pos_{i - 1} + 1}^{n} f_{j + 1}\) với \(a_j < b_i\) và không tồn tại \(k\) sao cho \(pos_{i - 1} + 1 \leq k < j\) và \(a_k = a_j\).
Độ phức tạp: \(\mathcal{O}(n \times m)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500005;
const int MOD = 1e9 + 7;

int a[MAX_N], b[MAX_N];
int pos[MAX_N], dp[MAX_N], last[MAX_N];
bool used[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("SETSEQ.inp", "r", stdin);
    freopen("SETSEQ.out", "w", stdout);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    bool chk = false;
    pos[0] = 0;
    for (int i = 1, j = 1; i <= n; i++) {
        if (a[i] == b[j]) {
            pos[j] = i;
            if (++j == m + 1) {
                chk = true;
                break;
            }
        }
    }

    if (!chk) {
        cout << -1 << "\n";
        return 0;
    }

    dp[n + 1] = 1;
    for (int i = n; i >= 1; i--) {
        dp[i] = 2 * dp[i + 1] % MOD;
        if (last[a[i]]) {
            (dp[i] -= dp[last[a[i]] + 1] - MOD) %= MOD;
        }

        last[a[i]] = i;
    }

    int ans = m;
    for (int i = 1; i <= m; i++) {
        fill(used + 1, used + n + 1, false);
        for (int j = pos[i - 1] + 1; j <= n; j++) {
            if (a[j] < b[i] && !used[a[j]]) {
                (ans += dp[j + 1]) %= MOD;
                used[a[j]] = true;
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

Subtask \(5\) (\(15\%\) số điểm): không có ràng buộc gì thêm.

Tutorial

Cũng như subtask 3, ta có thể quản lý các vị trí \(j\) thảo mãn bằng Fenwick tree và giờ thêm dãy \(last\). Ta duyệt ngược từ phải qua trái, đến vị trí \(j\) nào, ta sẽ tăng giá trị tại vị trí \(a_j\) trên cây thêm \(f_{j + 1} - f_{last_{a_j} + 1}\). Đến vị trí \(i\) nào, ta sẽ cộng đáp án với những giá trị tại những vị trí nhỏ hơn \(b_i\) trên cây.
Độ phức tạp: \(\mathcal{O}((n + m) \times \log n)\).

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500005;
const int MOD = 1e9 + 7;

int tree[MAX_N];

void update(int pos, int val) {
    for (int i = pos; i < MAX_N; i += i & -i) {
        (tree[i] += val) %= MOD;
    }
}

int query(int pos) {
    int res = 0;
    for (int i = pos; i > 0; i -= i & -i) {
        (res += tree[i]) %= MOD;
    }

    return res;
}

int n, m;
int a[MAX_N], b[MAX_N];
int pos[MAX_N], dp[MAX_N], last[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    freopen("SETSEQ.inp", "r", stdin);
    freopen("SETSEQ.out", "w", stdout);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    bool chk = false;
    pos[0] = 0;
    for (int i = 1, j = 1; i <= n; i++) {
        if (a[i] == b[j]) {
            pos[j] = i;
            if (++j == m + 1) {
                chk = true;
                break;
            }
        }
    }

    if (!chk) {
        cout << -1 << "\n";
        return 0;
    }

    int ans = m;
    dp[n + 1] = 1;
    for (int i = m, j = n; i >= 1; i--) {
        while (j >= pos[i - 1] + 1) {
            dp[j] = 2 * dp[j + 1] % MOD;
            if (last[a[j]]) {
                (dp[j] -= dp[last[a[j]] + 1] - MOD) %= MOD;
                update(a[j], -dp[last[a[j]] + 1] + MOD);
            }

            update(a[j], dp[j + 1]);
            last[a[j]] = j;
            j--;
        }

        (ans += query(b[i] - 1)) %= MOD;
    }

    cout << ans << "\n";

    return 0;
}

Bonus

Challenge

Hãy thử giải bài này khi đề cho \(k\) và bắt mình phải tìm dãy thứ \(k\) trong tập hợp

Bình luận

Tải bình luận...

Không có bình luận nào.