Hướng dẫn cho LQDOJ CUP 2022 - Final Round - XMAS

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: letangphuquy

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

Tutorial

Đặt \(dp(l,r) =\) true / false tương ứng với việc có thể xóa hết toàn bộ số trong đoạn \([l, r]\) không?
Hai trường hợp:

\(a[l] + a[r] = k\), nếu \(dp(l + 1, r - 1)\) đúng thì \(dp(l, r)\) cũng đúng
Nếu tồn tại \(i : l \leq i < r\) mà \(dp(l, i)\) và \(dp(i + 1, r)\) đều đúng thì \(dp(l, r)\) là đúng.

Độ phức tạp: \(\mathcal{O}(n^{3})\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 105;

int n, k, numQuery;
int a[MAX_N];
bool dp[MAX_N][MAX_N];

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

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

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

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

    for (int len = 4; len <= n; len += 2) {
        for (int left = 1, right = len; right <= n; left++, right++) {
            dp[left][right] = (a[left] + a[right] == k) && dp[left + 1][right - 1];
            for (int mid = left + 1; mid < right; mid += 2) {
                dp[left][right] |= dp[left][mid] && dp[mid + 1][right];
            }
        }
    }

    while (numQuery--) {
        int left, right;
        cin >> left >> right;
        cout << (dp[left][right] ? "YES\n" : "NO\n");
    }

    return 0;
}

Subtask \(2\) (\(30\%\) số điểm): \(n \leq 5 \times 10^{5}, q \leq 10\)

Tutorial

Để giải subtask này, ta cần các nhận xét sau:

nếu có 2 lựa chọn xóa bên trái trước, hoặc xóa bên phải trước, \([k - a, a, k-a]\), có thể xóa cặp nào cũng được vì mảng tạo thành sau đó là như nhau.
nếu gặp bất kì cặp nào xóa được thì cứ xóa trước.

Do đó, với mỗi truy vấn, ta có thể mô phỏng lại quá trình xóa trong \(O(n)\)
Độ phức tạp: \(\mathcal{O}(n \times q)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500005;

int n, k, numQuery;
int a[MAX_N];

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

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

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

    while (numQuery--) {
        int left, right;
        cin >> left >> right;
        stack<int> st;

        for (int i = left; i <= right; i++) {
            if (st.empty()) {
                st.push(a[i]);
            } else if (st.top() + a[i] != k) {
                st.push(a[i]);
            } else {
                st.pop();
            }
        }

        cout << (st.empty() ? "YES\n" : "NO\n");
    }

    return 0;
}

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

Tutorial

Đặt \(p[i]\) là vị trí gần \(i\) nhất, \(p[i]<i\) và \(a[p[i]] + a[i] = k\), sao cho đoạn con \(p[i] \ldots i\) có thể xóa được.
Nếu không tồn tại vị trí như vậy, quy ước \(p[i]\) là một giá trị đặc biệt nào đó (\(0,-1,\dots\))
Dùng các \(p\) trước đó để tính \(p\) hiện tại:

đặt \(p[i] = i - 1\)
chừng nào mà tổng \(a[p[i]] + a[i] \neq k\), gán \(p[i] = p[p[i]] - 1\)

Khi truy vấn: ta dùng mảng \(p\) để "nhảy" về theo quy tắc như trên.
Các thao tác này có thể tăng tốc bằng bảng thưa.
Độ phức tạp: \(\mathcal{O}((q+n)\log_{2} n)\)

Solution

C++

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 500005;

int n, k, a[MAX_N], p[MAX_N], ip[MAX_N];
int numQuery, l[MAX_N], r[MAX_N];
bool ans[MAX_N];
vector<int> ids[MAX_N];
map<int, int> mark[MAX_N];
map<int, bool> reach[MAX_N];

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

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

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> numQuery;
    for (int i = 1; i <= numQuery; i++) {
        cin >> l[i] >> r[i];
        ids[r[i]].push_back(i);
    }

    a[0] = -1;
    reach[0][0] = true;
    for (int i = 1; i <= n; i++) {
        p[i] = mark[i - 1][k - a[i]];
        ip[p[i]] = i;
        if (p[i]) {
            swap(mark[i], mark[p[i] - 1]);
            swap(reach[i], reach[p[i] - 1]);
        }
        mark[i][a[i]] = i;
        reach[i][i] = true;
        for (int id : ids[i]) {
            ans[id] = reach[r[id]][l[id] - 1];
        }
    }

    for (int i = 1; i <= numQuery; i++) {
        cout << (ans[i] ? "YES\n" : "NO\n");
    }

    return 0;
}

Bình luận

0

anhthu030412 9:59 p.m. 12 Tháng 7, 2023

Nếu chép code sẽ dẫn đến khóa tk mà sao còn để code vào hướng dẫn ạ?

2 phản hồi