Hướng dẫn cho LQDOJ Cup 2023 - Round 8 - Paint

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\)

Tutorial

Ta không cần quan tâm đến thứ tự dùng cây cọ mà chỉ cần dùng cọ sơn liên tiếp nhau, khi đó, đáp án là \(\left\lceil\frac{n}{a + 2 \times b}\right\rceil\) (làm tròn lên).

Độ phức tạp: \(O(1)\).

Solution

C++

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

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 2e3 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "paint";

int p[siz];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    int n, a, b;
    cin >> n >> a >> b;

    rep (i, 1, n) {
        cin >> p[i];
    }

    if (a + b >= n) {
        cout << 1 << "\n";
        return 0;
    }

    cout << (n + a + 2 * b - 1) / (a + 2 * b) << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

Subtask \(2\)

Tutorial

Nếu giá trị \(w\) thoả mãn thì giá trị \(w + 1\) cũng thoả mãn. Ngược lại, nếu giá trị \(w\) không thoả mãn thì giá trị \(w - 1\) cũng không thoả mãn. Vì vậy ta có thể sử dụng tìm kiếm nhị phân để tìm kiếm giá trị \(w\) nhỏ nhất thoả mãn.

Với một giá trị \(w\), ta có thể sử dụng thuật toán tham lam để kiểm tra xem có thể sơn hết các ô hay không. Ta sẽ sơn bắt đầu từ ô chưa được sơn đầu tiên, tìm ô chưa được sơn cuối cùng mà ta có thể sơn đến đó và lặp lại thuật toán ở vị trí tiếp theo.

Lưu ý, sắp xếp lại vị trí của các ô trước khi thực hiện thuật toán vì các vị trí được cho có thể chưa được sắp xếp.

Độ phức tạp: \(O(n \times \log_2 10^9)\).

Solution

C++

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

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 2e3 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "paint";

int n, a, b;
int p[siz];

bool check(int w) {
    int cnt = 0;
    rep (i, 1, n) {
        cnt++;
        int j = i;
        while (j < n && p[j + 1] - p[i] + 1 <= w) {
            j++;
        }

        i = j;
    }

    return cnt <= a;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    cin >> n >> a >> b;

    rep (i, 1, n) {
        cin >> p[i];
    }

    if (a + b >= n) {
        cout << 1 << "\n";
        return 0;
    }

    sort(p + 1, p + n + 1);

    int ans = -1;
    for (int lb = 1, rb = 1e9; lb <= rb; ) {
        int mb = (lb + rb) / 2;

        if (check(mb)) {
            ans = mb;
            rb = mb - 1;
        } else {
            lb = mb + 1;
        }
    }

    cout << ans << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

Subtask \(3\)

Tutorial

Lúc này ta cần quan tâm đến thứ tự dùng cây cọ. Ta vẫn dùng tìm kiếm nhị phân như subtask 2 nhưng lúc kiểm tra, thay vì tham lam, ta sẽ sử dụng quy hoạch động.

Nếu \(a + b \geq n\) thì đáp án là \(1\). Sau này, giá trị của \(a\) và \(b\) không thể vượt quá \(n\).

Gọi \(dp(i, x, y)\) nghĩa là có thể sơn đến ô chưa được sơn thứ \(i\) với \(x\) cây cọ kích thước \(w\) và \(y\) cây cọ kích thước \(2 \times w\) được hay không.

Có hai trường hợp:

Chọn cây cọ kích thước \(w\): \(dp(j_1, x - 1, y)\).
Chọn cây cọ kích thước \(2 \times w\): \(dp(j_2, x, y - 1)\).

Trong đó, \(j_1\) là vị trí của ô chưa được sơn gần nhất về phía bên trái so với \(i\) mà cây cọ kích thước \(w\) không thể sơn từ ô \(x_i\) đến ô \(x_{j_1}\), tương tự với \(j_2\) cho cây cọ kích thước \(2 \times w\).

Kết hợp cả hai trường hợp lại, ta tính được \(dp(i, x, y)\). Kết quả kiểm tra sẽ là \(dp(n, x, y)\) với \(0 \leq x \leq a\) và \(0 \leq y \leq b\).

Độ phức tạp: \(O(n^3 \times \log_2 10^9)\).

Solution

C++

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

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 2e2 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "paint";

int n, a, b;
int p[siz];
bool dp[siz][siz][siz];

bool check(int w) {
    memset(dp, false, sizeof(dp));
    dp[0][0][0] = true;
    rep (i, 1, n) {
        int j_1 = lower_bound(p + 1, p + n + 1, p[i] - w + 1) - p - 1;
        int j_2 = lower_bound(p + 1, p + n + 1, p[i] - 2 * w + 1) - p - 1;
        rep (x, 0, a) rep (y, 0, b) {
            if (x > 0) {
                dp[i][x][y] |= dp[j_1][x - 1][y];
            }

            if (y > 0) {
                dp[i][x][y] |= dp[j_2][x][y - 1];
            }
        }
    }

    rep (x, 0, a) rep (y, 0, b) {
        if (dp[n][x][y]) {
            return true;
        }
    }

    return false;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    cin >> n >> a >> b;

    rep (i, 1, n) {
        cin >> p[i];
    }

    if (a + b >= n) {
        cout << 1 << "\n";
        return 0;
    }

    sort(p + 1, p + n + 1);

    int ans = -1;
    for (int lb = 1, rb = 1e9; lb <= rb; ) {
        int mb = (lb + rb) / 2;

        if (check(mb)) {
            ans = mb;
            rb = mb - 1;
        } else {
            lb = mb + 1;
        }
    }

    cout << ans << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

Subtask \(4\)

Tutorial

Tương tự như subtask 3, thay vì lưu trạng thái \(y\), ta có thể đưa nó ra ngoài.

Gọi \(dp(i, x)\) là số lượng cây cọ kích thước \(2 \times w\) ít nhất để sơn đến ô chưa được sơn thứ \(i\) với \(x\) cây cọ kích thước \(w\).

Tương tự, có hai trường hợp:

Chọn cây cọ kích thước \(w\): \(dp(j_1, x - 1)\).
Chọn cây cọ kích thước \(2 \times w\): \(dp(j_2, x) + 1\).

Kết hợp cả hai trường hợp lại, ta tính được \(dp(i, x)\). Kết quả kiểm tra sẽ là thoả mãn nếu tồn tại \(x\) sao cho \(0 \leq x \leq a\) và \(dp(n, x) \leq b\).

Độ phức tạp: \(O(n^2 \times \log_2 10^9)\).

Solution

C++

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

#define fi first
#define se second
#define mp make_pair
//#define int long long
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i = (int)(l); i <= (int)(r); i++)
#define per(i, r, l) for (int i = (int)(r); i >= (int)(l); i--)

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template<typename _Tp> bool minimize(_Tp& __a, const _Tp& __b) { if (__a > __b) { __a = __b; return true; } return false; }
template<typename _Tp> bool maximize(_Tp& __a, const _Tp& __b) { if (__a < __b) { __a = __b; return true; } return false; }

const int siz = 2e3 + 2;
const int SIZ = 1e6 + 2;
const int mod = 1e9 + 7;
const int maxx = 2e9;
const ll MAXX = 1e18;
const string file = "paint";

int n, a, b;
int p[siz];
int dp[siz][siz];

bool check(int w) {
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    rep (i, 1, n) {
        int j_1 = lower_bound(p + 1, p + n + 1, p[i] - w + 1) - p - 1;
        int j_2 = lower_bound(p + 1, p + n + 1, p[i] - 2 * w + 1) - p - 1;
        rep (k, 0, a) {
            if (k > 0) {
                minimize(dp[i][k], dp[j_1][k - 1]);
            }
            minimize(dp[i][k], dp[j_2][k] + 1);
        }
    }

    rep (k, 0, a) {
        if (dp[n][k] <= b) {
            return true;
        }
    }

    return false;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (fopen((file + ".inp").c_str(), "r")) {
        freopen((file + ".inp").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    }

    cin >> n >> a >> b;

    rep (i, 1, n) {
        cin >> p[i];
    }

    if (a + b >= n) {
        cout << 1 << "\n";
        return 0;
    }

    sort(p + 1, p + n + 1);

    int ans = -1;
    for (int lb = 1, rb = 1e9; lb <= rb; ) {
        int mb = (lb + rb) / 2;

        if (check(mb)) {
            ans = mb;
            rb = mb - 1;
        } else {
            lb = mb + 1;
        }
    }

    cout << ans << "\n";

//    cerr << "Time: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";

    return 0;
}

Bình luận

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

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