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.

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]


Bình luận

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