Tổng quan về bộ đề

Bộ đề này tập trung vào các kỹ thuật cơ bản trong lập trình thi đấu như thuật toán tham lam, xử lý dãy số và cấu trúc dữ liệu cây. Dưới đây là phân tích chi tiết và cách tiếp cận tối ưu cho các bài toán từ A đến D.

Bài A: Tối ưu hóa thao tác trên dãy số

Vấn đề cốt lõi là xác định thứ tự thực hiện thao tác để tối đa hóa số lượng phần tử dương trong mảng. Vì giá trị của phần tử tại vị trí i bị ảnh hưởng bởi phần tử tại vị trí i+1, chiến lược hiệu quả là duyệt từ cuối mảng về đầu.

Khi duyệt ngược, nếu phần tử kề sau có giá trị không âm, việc cộng nó vào phần tử hiện tại sẽ không làm giảm khả năng trở thành số dương của phần tử hiện tại. Ngược lại, nếu phần tử kề sau âm, việc cộng vào sẽ chỉ làm giảm giá trị hiện tại. Do đó, điều kiện thực hiện là khi arr[i+1] >= 0. Sau khi hoàn tất các phép cộng, ta đếm số lượng phần tử dương.

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int size;
    cin >> size;
    vector<long long> arr(size);
    for (int i = 0; i < size; ++i) {
        cin >> arr[i];
    }

    for (int i = size - 2; i >= 0; --i) {
        if (arr[i + 1] >= 0) {
            arr[i] += arr[i + 1];
        }
    }

    int positiveCount = 0;
    for (long long val : arr) {
        if (val > 0) positiveCount++;
    }
    cout << positiveCount << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testCases;
    cin >> testCases;
    while (testCases--) {
        solve();
    }
    return 0;
}

Bài B: Chiến lược Mex và Max

Bài toán yêu cầu xây dựng dãy số sao cho tổng của giá trị lớn nhất (Max) và giá trị Mex đạt tối ưu. Chiến lược tham lam ở đây là đặt phần tử lớn nhất của dãy vào vị trí đầu tiên. Điều này đảm bảo mọi tiền tố đều có giá trị Max bằng giá trị lớn nhất của toàn bộ dãy.

Sau khi cố định phần tử lớn nhất, mục tiêu là tăng giá trị Mex nhanh nhất có thể. Các phần tử còn lại nên được sắp xếp tăng dần. Tuy nhiên, để tối ưu hóa tốc độ tăng Mex, các giá trị trùng lặp không đóng góp vào việc tăng Mex ngay lập tức nên có thể được đẩy xuống cuối. Công thức tính toán cần xử lý trường hợp đặc biệt khi Mex đạt đến giá trị bằng Max + 1.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    sort(a.begin(), a.end());
    long long maxVal = a.back();
    long long mex = 0;

    for (int i = 0; i < n; ++i) {
        if (a[i] == mex) mex++;
    }

    long long totalScore = maxVal * n + (mex * (mex + 1)) / 2;
    totalScore += (n - mex - 1) * mex;

    if (maxVal < mex) {
        totalScore = totalScore - maxVal + mex;
    }

    cout << totalScore << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Bài C: Cân bằng dãy ngoặc

Để kiểm tra tính hợp lệ của dãy ngoặc mà không cần栈 (stack), ta có thể quy đổi ngoặc mở thành +1 và ngoặc đóng thành -1. Một dãy hợp lệ khi tổng toàn bộ bằng 0 và mọi tổng tiền tố đều không âm.

Với hai dãy cần kiểm tra đồng thời, ta duy trì hai biến tổng tiền tố. Tại mỗi bước, để tránh việc một tổng bị âm trong khi tổng kia quá lớn, ta gán giá trị nhỏ hơn trong hai lựa chọn cho biến tổng đang lớn hơn và ngược lại. Nếu tại bất kỳ thời điểm nào một trong hai tổng trở thành âm, dãy không hợp lệ. Cuối cùng, cả hai tổng phải cùng về 0.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

void solve() {
    int n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;

    vector<int> val1(n), val2(n);
    for (int i = 0; i < n; ++i) val1[i] = (s1[i] == '(' ? 1 : -1);
    for (int i = 0; i < n; ++i) val2[i] = (s2[i] == '(' ? 1 : -1);

    long long sum1 = 0, sum2 = 0;
    bool possible = true;

    for (int i = 0; i < n; ++i) {
        int v1 = val1[i];
        int v2 = val2[i];
        
        if (sum1 < sum2) {
            sum1 += v1;
            sum2 += v2;
        } else {
            sum1 += v2;
            sum2 += v1;
        }

        if (sum1 < 0 || sum2 < 0) {
            possible = false;
            break;
        }
    }

    if (possible && sum1 == 0 && sum2 == 0) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Bài D: Kỳ vọng số nghịch thế

Bài toán yêu cầu tính số nghịch thế kỳ vọng khi kết hợp hai dãy số. Cách tiếp cận là tính tổng số nghịch thế của tất cả các cặp có thể tạo thành, sau đó chia cho tổng số trường hợp. Sử dụng cây chỉ số nhị phân (BIT) kết hợp với rời rạc hóa giúp đếm số lượng phần tử nhỏ hơn hiệu quả.

Đầu tiên, tính tổng nghịch thế ignoring điều kiện chỉ số khác nhau. Sau đó, trừ đi các trường hợp trùng chỉ số (nghĩa là a[i] kết hợp với b[i]). Kết quả cuối cùng cần nhân với nghịch đảo modular của tổng số cặp để ra kỳ vọng.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long MOD = 998244353;

struct FenwickTree {
    int size;
    vector<long long> tree;
    FenwickTree(int n) : size(n), tree(n + 1, 0) {}
    void add(int idx, long long val) {
        for (++idx; idx <= size; idx += idx & -idx)
            tree[idx] += val;
    }
    long long query(int idx) {
        long long sum = 0;
        for (++idx; idx > 0; idx -= idx & -idx)
            sum += tree[idx];
        return sum;
    }
};

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, MOD - 2);
}

void solve() {
    int n;
    cin >> n;
    vector<long long> A(n), B(n);
    for (int i = 0; i < n; ++i) cin >> A[i];
    for (int i = 0; i < n; ++i) cin >> B[i];

    vector<long long> products;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            products.push_back(A[i] * B[j]);

    vector<long long> sortedProd = products;
    sort(sortedProd.begin(), sortedProd.end());
    sortedProd.erase(unique(sortedProd.begin(), sortedProd.end()), sortedProd.end());

    auto getRank = [&](long long val) {
        return lower_bound(sortedProd.begin(), sortedProd.end(), val) - sortedProd.begin();
    };

    FenwickTree bit(sortedProd.size());
    long long totalInversions = 0;
    int totalElements = n * n;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            long long val = A[i] * B[j];
            int rank = getRank(val);
            totalInversions = (totalInversions + bit.query(rank - 1)) % MOD;
        }
        for (int j = 0; j < n; ++j) {
            long long val = A[i] * B[j];
            int rank = getRank(val);
            bit.add(rank, 1);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (A[j] > A[i]) {
                totalInversions = (totalInversions - n + MOD) % MOD;
            }
        }
    }

    long long denominator = (1LL * n * (n - 1)) % MOD;
    long long ans = (totalInversions * modInverse(denominator)) % MOD;
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Các bài toán nâng cao

Các bài toán E và F yêu cầu kiến thức sâu hơn về lý thuyết số đồng dư, thuật toán CRT mở rộng hoặc phân tích cây (Tree Decomposition). Do độ phức tạp cao và ít người giải được trong thời gian thi, các giải pháp này thường không được đề cập chi tiết trong các buổi tổng quan cơ bản.