Phân tích bài toán hệ số Binomial biến thể

Trong bài toán này, chúng ta được cung cấp một đoạn mã giả lập cách tính một bảng tương tự như tam giác Pascal nhưng có quy luật thay đổi. Đề bài yêu cầu tính giá trị tại các vị trí $(n_i, k_i)$ dựa trên quy tắc tính toán đó.

Bằng cách thực hiện chạy thử (dry run) hoặc lập bảng giá trị nhỏ, ta có thể nhận thấy quy luật của bảng số này. Thay vì tuân theo công thức Pascal truyền thống $C(n, k) = C(n-1, k-1) + C(n-1, k)$, quy tắc trong đề bài dẫn đến kết quả $C[n][k] = 2^k \pmod{10^9 + 7}$. Điều này có nghĩa là giá trị không phụ thuộc vào $n$ mà chỉ phụ thuộc vào $k$ (với điều kiện $n \ge k$).

Để giải quyết bài toán với giới hạn dữ liệu lớn, chúng ta sử dụng thuật toán lũy thừa nhanh để tính $2^k$ trong độ phức tạp $O(\log k)$.

#include <iostream>
#include <vector>

using namespace std;

long long fast_pow(long long base, long long exp) {
    long long res = 1;
    const long long MOD = 1e9 + 7;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    vector<int> n_vals(t), k_vals(t);
    for (int i = 0; i < t; ++i) cin >> n_vals[i];
    for (int i = 0; i < t; ++i) cin >> k_vals[i];

    for (int i = 0; i < t; ++i) {
        cout << fast_pow(2, k_vals[i]) << "\n";
    }

    return 0;
}

Tối ưu chiến thuật chọn thẻ bài trong trò chơi mới

Bài toán yêu cầu tìm số lượng thẻ bài tối đa có thể chọn sao cho: các thẻ bài phải có giá trị liên tiếp hoặc bằng nhau, và tổng số loại thẻ khác nhau không vượt quá $k$.

Để giải quyết bài toán này, chúng ta thực hiện các bước sau:

1. Thống kê tần suất: Sử dụng một cấu trúc dữ liệu (như std::map hoặc mảng đã sắp xếp) để đếm số lần xuất hiện của từng loại thẻ.
2. Phân đoạn dữ liệu: Chia các loại thẻ thành các nhóm liên tiếp. Nếu hai loại thẻ có giá trị chênh lệch lớn hơn 1, chúng không thể thuộc cùng một dãy chọn.
3. Sử dụng cửa sổ trượt (Sliding Window): Trên mỗi đoạn các thẻ có giá trị liên tiếp ($x, x+1, x+2, \dots$), ta duy trì một cửa sổ có độ dài tối đa là $k$. Tổng số lượng thẻ trong cửa sổ này chính là ứng cử viên cho kết quả tối ưu.

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

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        counts[x]++;
    }

    vector<pair<int, int>> items;
    for (auto const& [val, freq] : counts) {
        items.push_back({val, freq});
    }

    long long max_cards = 0;
    int total_types = items.size();
    int right = 0;
    long long current_sum = 0;

    for (int left = 0; left < total_types; ++left) {
        if (right < left) {
            right = left;
            current_sum = 0;
        }
        
        while (right < total_types) {
            if (right > left && items[right].first != items[right - 1].first + 1) {
                break;
            }
            if (right - left + 1 > k) {
                break;
            }
            current_sum += items[right].second;
            right++;
        }
        
        max_cards = max(max_cards, current_sum);
        current_sum -= items[left].second;
    }

    cout << max_cards << "\n";
}

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

Trong cách tiếp cận trên, độ phức tạp thời gian chủ yếu nằm ở việc sắp xếp hoặc sử dụng map ($O(N \log N)$) và kỹ thuật hai con trỏ ($O(N)$). Điều này đảm bảo chương trình chạy hiệu quả trong giới hạn thời gian cho phép của các hệ thống chấm bài trực tuyến.