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 ạ?

3

letangphuquy 3:31 p.m. 13 Tháng 7, 2023

nhiều bài khi đọc code thì ta sẽ rõ ràng ý tưởng hơn em nhé, trên CodeForces cũng vậy. quan trọng là em sử dụng như thế nào.

giống như em mua sách bài tập, thì cũng có phần lời giải ở đằng sau. em có thể chọn chép vào trước khi đến lớp hoặc làm đàng hoàng mà.

2

Yuki 3:11 p.m. 13 Tháng 7, 2023

Mục đích của việc ban cũng chỉ là răn đe, vì những hành vi "trẩu" khi làm bài tập thật ra chỉ có hại cho bản thân bạn thôi, chứ không phải ai cả. Bạn chép, if thì có thể AC nhưng sẽ không hiểu được sâu sắc, và đương nhiên là không học được thuật toán, ý tưởng của bài đó... Tệ hơn nữa là ảnh hưởng tới những bạn khác, code đấy có thể bạn khác dành ra rất nhiều thời gian để suy nghĩ, code, debug; nhưng bạn chỉ if test trong 10 phút và copy để nộp lại? Điều đó gây nên cảm giác rất khó chịu.
Việc răn đe nhằm giúp tạo môi trường học tập lành mạnh hơn cho LQDOJ.
Source: letangphuquy