Hướng dẫn cho PVHOI3 - Bài 1: Gắp thú bông

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

Subtask 1: \(m = n = 1, q \leq 1000, r_1 \leq 1000\)

Với subtask này, ta có \(r_1 \leq 1000\) con thú bông và \(q \leq 1000\) truy vấn. Do đó, ta có thể sinh ra tất cả các con thú bông và sắp xếp chúng theo thứ tự. Với từng truy vấn trong \(q\) truy vấn, ta duyệt trong \(\mathcal{O}(r_1)\) để tìm lượt chơi đầu tiên thỏa mãn số tiền thu được \(\geq t_i\).

Độ phức tạp: \(\mathcal{O}(q \times r_1 \times n) = \mathcal{O}(q \times r_1)\).

Code tham khảo

C++

// O(q*max(r))
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int N = 1e5+5;
const ull INF = 9e18;

int numPivots, numRanges, numQueries;
ull pivots[N], cost[N];
int L[N], R[N];
ull queries[N];

void Input() {
    cin >> numPivots >> numRanges >> numQueries;
    for(int i = 1; i <= numPivots; ++i) cin >> pivots[i];
    for(int i = 0; i <= numPivots; ++i) cin >> cost[i];
    for(int i = 1; i <= numRanges; ++i) cin >> L[i] >> R[i];
    for(int i = 1; i <= numQueries; ++i) cin >> queries[i];
}

void Solve() {
    pivots[numPivots+1] = INF; pivots[0] = 0;

    for(int i = 1; i <= numQueries; ++i) {
        int ans = -1, pivot_id = 0;
        ull paid = 0, price = 0;

        for(int j = L[1]; j <= R[1]; ++j) {
            while (pivot_id < numPivots && paid >= pivots[pivot_id+1]) ++pivot_id;
            paid += cost[pivot_id];
            price += j;

            if (price >= queries[i] + paid)  {
                ans = j - L[1] + 1;
                break;
            }
        }
        cout << ans << ' ';
    }
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("GAPTHU.INP", "r")) {
        freopen("GAPTHU.INP", "r", stdin);
        freopen("GAPTHU.OUT", "w", stdout);
    }
    Input(), Solve();
    return 0;
}

Subtask 2: \(m = n = 1\)

Ở subtask này, ta có \(r_1 \leq 10^7\) con thú bông và \(q \leq 10^5\) truy vấn.

Nhận xét

Do \(s_1 < s_2 < \dots < s_n\) và \(p_0 > p_1 > \dots > p_n\), nên tổng tiền lời sau mỗi lần gắp thú là một hàm không giảm. Nói cách khác, gọi \(gain(j)\) là tổng tiền lời sau \(j\) lượt chơi, ta có \(gain(0) = 0 \leq gain(1) \leq \dots \leq gain(r_1)\).

Sắp xếp các truy vấn theo độ lớn tăng dần, gọi \(ans(i)\) là đáp án cho truy vấn thứ \(i\) (theo thứ tự đã sắp xếp). Khi đó, ta có \(ans(i-1) \leq ans(i)\) với \(1 < i \leq q\).

Lời giải

Dùng kĩ thuật hai con trỏ, duyệt lần lượt các truy vấn theo thứ tự độ lớn tăng dần. Tại truy vấn thứ \(i\), ta duy trì số lượng lượt chơi tối thiểu để thỏa mãn truy vấn, số lượng tiền đã bỏ ra và tổng tiền lời khi gắp những con gấu này. Khi giá trị truy vấn tăng lên, ta gắp thêm những con thú tiếp theo cho đến khi số tiền lời thỏa mãn.

Độ phức tạp: \(\mathcal{O}(q + r_1)\)

Code tham khảo

C++

// O(q + r_1)
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int N = 1e5+5;
const ull INF = 9e18;

int numPivots, numRanges, numQueries;
ull pivots[N], cost[N];
int L[N], R[N];
pair<ull, int> queries[N];
int ans[N];

void Input() {
    cin >> numPivots >> numRanges >> numQueries;
    for(int i = 1; i <= numPivots; ++i) cin >> pivots[i];
    for(int i = 0; i <= numPivots; ++i) cin >> cost[i];
    for(int i = 1; i <= numRanges; ++i) cin >> L[i] >> R[i];
    for(int i = 1; i <= numQueries; ++i) {
        cin >> queries[i].first;
        queries[i].second = i;
    }
}

void Solve() {
    pivots[numPivots+1] = INF; pivots[0] = 0;

    sort(queries+1, queries+1+numQueries);

    int j = L[1]-1, pivot_id = 0;
    ull paid = 0, price = 0;
    for(int i = 1; i <= numQueries; ++i) { 
        while (j < R[1] && price < queries[i].first + paid) {
            ++j;
            while (pivot_id < numPivots && paid >= pivots[pivot_id+1]) ++pivot_id;
            paid += cost[pivot_id];
            price += j;
        }
        if (price >= queries[i].first + paid) ans[queries[i].second] = j - L[1] + 1;
        else ans[queries[i].second] = -1;
    }

    for(int i = 1; i <= numQueries; ++i)
        cout << ans[i] << ' ';
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("GAPTHU.INP", "r")) {
        freopen("GAPTHU.INP", "r", stdin);
        freopen("GAPTHU.OUT", "w", stdout);
    }
    Input(), Solve();
    return 0;
}

Subtask 3: \(n = 1\)

Ở subtask này, số lượng con thú có thể gắp lên đến \(\sum_i r_i - l_i +1 \leq 10^7 \times 10^5 = 10^{12}\). Khi này, việc duyệt qua từng lượt chơi không còn khả thi.

Tuy nhiên, nhờ nhận xét \(gain(j-1) \leq gain(j)\) từ subtask 2, ta nhận ra có thể xác định số lượng lượt chơi nhờ kĩ thuật tìm kiếm nhị phân. Nhiệm vụ của ta bây giờ là xác định tổng tiền lời sau \(x\) lượt chơi bất kì một cách nhanh chóng.

Ta tiến hành đi tính các nhãn \(toy(i)\) - số lượng thú bông có giá trị \(\leq i\) và \(price(i)\) - tổng giá trị của các thú bông có giá trị \(\leq i\). \(toy(i)\) được xác định bằng kĩ thuật mảng cộng dồn, \(price(i)\) cũng được xác định trong quá trình tính \(toy(i)\).

Đoạn code sau mô tả cách tính:

C++

for(int i = 1; i <= n; ++i) {
    toy[l[i]]++; toy[r[i]+1]--;
}

price[0] = 0;
for(int i = 1; i < MAXR; ++i) {
    toy[i] += toy[i-1]; //Đến đây toy[i] = số lượng thú bông có giá trị i
    price[i] = price[i-1] + toy[i]*i;
}

for(int i = 1; i < MAXR; ++i) toy[i] += toy[i-1];

Khi đó, ta có thể xác định số lượng tiền thu được sau \(x\) lượt chơi trong \(\mathcal{O}(\log n)\) bằng tìm kiếm nhị phân và số tiền bỏ ra để chơi \(x\) lượt này trong \(\mathcal{O}(1)\) bằng cách xét hai trường hợp.

Độ phức tạp: \(\mathcal{O}(m + q \times \log(\text{số thú bông}) \times \log r_i)\)

Code tham khảo

C++

// O(q*log(R)*log(toys))
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5+5, MAXR = 1e7+5;
const ull INF = 9e18;

int numPivots, numRanges, numQueries;
ull pivots[N], cost[N];
ull preToys[MAXR], prePrice[MAXR];

void Input() {
    cin >> numPivots >> numRanges >> numQueries;
    for(int i = 1; i <= numPivots; ++i) cin >> pivots[i];
    for(int i = 0; i <= numPivots; ++i) cin >> cost[i];
}

ull paid(ull num) {
    ull num1 = min((pivots[1]+ cost[0]-1)/cost[0], num);
    if (INF/cost[1] <= num-num1) return INF;
    return num1*cost[0] + (num-num1)*cost[1];
}

ull price(ull num) {
    int maxPrice = 0;
    for(int step = MAXR>>1; step > 0; step >>= 1) {
        while (maxPrice+step < MAXR && preToys[maxPrice+step] <= num) 
            maxPrice += step;
    }
    return prePrice[maxPrice] + (num - preToys[maxPrice]) * (maxPrice + 1);
}

ll getAns(ull lowbound) {
    ll ans = -1;
    ull L = 1, R = preToys[MAXR-1];
    while (L <= R) {
        ull mid = (L+R) >> 1;
        (price(mid) >= lowbound + paid(mid)) ? ans = mid, R = mid-1 : L = mid+1;
    }
    return ans;
}

void Solve() {
    pivots[numPivots+1] = INF; pivots[0] = 0;

    for(int i = 1; i <= numRanges; ++i) {
        int L, R; cin >> L >> R;
        preToys[L]++; preToys[R+1]--;
    }
    for(int i = 1; i < MAXR; ++i) preToys[i] += preToys[i-1];
    for(int i = 1; i < MAXR; ++i) {
        prePrice[i] = prePrice[i-1] + preToys[i]*i;
        preToys[i] += preToys[i-1];
    };

    for(int i = 1; i <= numQueries; ++i) {
        ull qval; cin >> qval;
        cout << getAns(qval) << ' ';
    }
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("GAPTHU.INP", "r")) {
        freopen("GAPTHU.INP", "r", stdin);
        freopen("GAPTHU.OUT", "w", stdout);
    }
    Input(), Solve();
    return 0;
}

Subtask 4: \(n \leq 10\)

Lời giải subtask này tương tự với subtask 3, tuy nhiên để xác định số tiền bỏ ra sau \(x\) lượt chơi, ta cần duyệt \(\mathcal{O}(n)\).

Độ phức tạp: \(\mathcal{O}(m + n + q \times \log(\text{số thú bông}) \times (\log r_i + n))\)

Code tham khảo

C++

// O(q*(log(R) + n)*log(toys))
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5+5, MAXR = 1e7+5;
const ull INF = 9e18;

int numPivots, numRanges, numQueries;
ull pivots[N], cost[N];
ull preToys[MAXR], prePrice[MAXR];

void Input() {
    cin >> numPivots >> numRanges >> numQueries;
    for(int i = 1; i <= numPivots; ++i) cin >> pivots[i];
    for(int i = 0; i <= numPivots; ++i) cin >> cost[i];
}

ull paid(ull num) {
    ull ans = 0;
    ull used = 0;
    for(int i = 0; i <= numPivots; ++i) {
        ull cur = min((pivots[i+1] - used - cost[i] + 1)/cost[i], num - used);
        if (INF/cost[i] <= cur || INF - cur*cost[i] <= ans) return INF;
        ans += cur * cost[i];
        used += cur;
        if (used == num) break;
    }
    return ans;
}

ull price(ull num) {
    int maxPrice = 0;
    for(int step = MAXR>>1; step > 0; step >>= 1) {
        while (maxPrice+step < MAXR && preToys[maxPrice+step] <= num) 
            maxPrice += step;
    }
    return prePrice[maxPrice] + (num - preToys[maxPrice]) * (maxPrice + 1);
}

ll getAns(ull lowbound) {
    ll ans = -1;
    ull L = 1, R = preToys[MAXR-1];
    while (L <= R) {
        ull mid = (L+R) >> 1;
        (price(mid) >= lowbound + paid(mid)) ? ans = mid, R = mid-1 : L = mid+1;
    }
    return ans;
}

void Solve() {
    pivots[numPivots+1] = INF; pivots[0] = 0;

    for(int i = 1; i <= numRanges; ++i) {
        int L, R; cin >> L >> R;
        preToys[L]++; preToys[R+1]--;
    }
    for(int i = 1; i < MAXR; ++i) preToys[i] += preToys[i-1];
    for(int i = 1; i < MAXR; ++i) {
        prePrice[i] = prePrice[i-1] + preToys[i]*i;
        preToys[i] += preToys[i-1];
    };

    for(int i = 1; i <= numQueries; ++i) {
        ull qval; cin >> qval;
        cout << getAns(qval) << ' ';
    }
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("GAPTHU.INP", "r")) {
        freopen("GAPTHU.INP", "r", stdin);
        freopen("GAPTHU.OUT", "w", stdout);
    }
    Input(), Solve();
    return 0;
}

Subtask 5: ràng buộc gốc

Tương tự như subtask 3 và 4, tuy nhiên do \(n\) lớn, ta cần tìm cách tính số tiền bỏ ra một cách nhanh hơn.

Ta tính trước \(turn(i)\) - số lượt chơi ít nhất để lượt chơi tiếp theo có giá \(p[i]\), và \(cost(i)\) - số tiền cần bỏ ra để chơi \(turn(i)\) lượt. Sau đó, ta có thể dùng tìm kiếm nhị phân để tính nhanh số tiền cần bỏ ra.

Độ phức tạp: \(\mathcal{O}(m + n + q \times \log(\text{số thú bông})\times(\log r_i + \log n))\)

Code tham khảo

C++

// O(q*(log(R) + log(n))*log(toys))
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
const int N = 1e5+5, MAXR = 1e7+5;
const ull INF = 9e18;

int numPivots, numRanges, numQueries;
ull pivots[N], cost[N];
ull preToys[MAXR], prePrice[MAXR];
ull preTurn[N], prePaid[N];

void Input() {
    cin >> numPivots >> numRanges >> numQueries;
    for(int i = 1; i <= numPivots; ++i) cin >> pivots[i];
    for(int i = 0; i <= numPivots; ++i) cin >> cost[i];
}

ull paid(ull num) {
    int i = upper_bound(preTurn, preTurn + 1 + numPivots, num) - preTurn - 1;
    if (INF/cost[i] <= num - preTurn[i]) return INF;
    return min(INF, prePaid[i] + (num - preTurn[i]) * cost[i]);
}

ull price(ull num) {
    int maxPrice = upper_bound(preToys, preToys+MAXR, num) - preToys - 1;
    return prePrice[maxPrice] + (num - preToys[maxPrice]) * (maxPrice + 1);
}

ll getAns(ull lowbound) {
    ll ans = -1;
    ull L = 1, R = preToys[MAXR-1];
    while (L <= R) {
        ull mid = (L+R) >> 1;
        (price(mid) >= lowbound + paid(mid)) ? ans = mid, R = mid-1 : L = mid+1;
    }
    return ans;
}

void Solve() {
    pivots[numPivots+1] = INF; pivots[0] = 0;

    for(int i = 1; i <= numRanges; ++i) {
        int L, R; cin >> L >> R;
        preToys[L]++, preToys[R+1]--;
    }
    for(int i = 1; i < MAXR; ++i) {
        preToys[i] += preToys[i-1];
        prePrice[i] = prePrice[i-1] + preToys[i]*i;
    }
    for(int i = 1; i < MAXR; ++i) preToys[i] += preToys[i-1];

    ull total = 0;
    preTurn[0] = prePaid[0] = 0;
    for(int i = 1; i <= numPivots; ++i) {
        if (total < INF) {
            if (pivots[i] <= total) prePaid[i] = prePaid[i-1], preTurn[i] = preTurn[i-1];
            else {
                ull cur = (pivots[i] - total + cost[i-1] - 1)/cost[i-1];
                if (INF/cur > cost[i-1] && INF - total > cost[i-1]*cur) total += cost[i-1]*cur;
                preTurn[i] = INF - cur > preTurn[i-1] ? cur + preTurn[i-1] : INF;
                prePaid[i] = total; 
            }
        } else preTurn[i] = prePaid[i] = INF;
    }

    for(int i = 1; i <= numQueries; ++i) {
        ll qval; cin >> qval;
        cout << getAns(qval) << " ";  
    }
}   

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen("GAPTHU.INP", "r")) {
        freopen("GAPTHU.INP", "r", stdin);
        freopen("GAPTHU.OUT", "w", stdout);
    }
    Input(), Solve();
    return 0;
}

Bình luận

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