Hướng dẫn cho LQDOJ CUP 2022 - Final Round (SV) - 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: zipdang04, letangphuquy

Subtask 3

Đặ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 \le i < r\) mà \(dp(l,i)\) và \(dp(i+1,r)\) đều đúng thì \(dp(l,r)\) là đúng.

ĐPT \(O(n^3)\)

Code mẫu (đxmh)

C++

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

#define MAX 1000001

#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define FORD(type, i, b, a) for(type i = (b); i >= (a); i--)

int n, k, q;
int a[MAX]; 

bool f[101][101];

void input();
main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();

    FOR(int, i, 1, n - 1)
        f[i][i + 1] = a[i] + a[i + 1] == k;
    for (int len = 4; len <= n; len += 2)
        for (int beg = 1, end = len; end <= n; beg++, end++){
            f[beg][end] = (a[beg] + a[end] == k) && f[beg + 1][end - 1];
            for (int mid = beg + 1; mid < end; mid += 2)
                f[beg][end] |= f[beg][mid] && f[mid + 1][end];
        }

    FOR(int, i, 1, q){
        int l, r; cin >> l >> r;
        cout << (f[l][r] ? "YES\n" : "NO\n");
    }
}
void input() {
    freopen("xmas.inp", "r", stdin);
    freopen("xmas.out", "w", stdout);
    cin >> n >> k;
    FOR(int, i, 1, n) cin >> a[i];
    cin >> q;
}

Subtask 4

Để 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)\) và đạt được ĐPT \(O(nq)\)

Code mẫu (đxmh)

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

#define MAX 500001

int n, k, q;
int a[MAX];

main(){
    freopen("xmas.inp", "r", stdin);
    freopen("xmas.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];

    cin >> q;
    for (int _ = 1; _ <= q; _++){
        int l, r; cin >> l >> r;
        stack<int> st;

        for (int i = l; i <= r; i++){
            if (st.empty())
                st.push(a[i]);
            else if (st.top() + a[i] != k)
                st.push(a[i]);
            else            // nếu thỏa mãn thì
                st.pop();   // ghép pop phần tử top để ghép với a[i]
        }

        if (st.empty())
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

Bình luận

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

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