Giải bài tập từ A đến D - Educational Codeforces Round 160 (Rated for Div. 2)

A. Tăng điểm xếp hạng

Đây là bài toán có thể giải bằng phương pháp đơn giản. Chúng ta sẽ duyệt qua chuỗi và chia nó thành hai phần. Nếu phần đầu nhỏ hơn phần sau, chúng ta in ra kết quả. Nếu duyệt hết chuỗi mà không tìm thấy trường hợp nào, chúng ta in ra -1.

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

int chuyenSo(string s) {
    stringstream ss;
    ss << s;
    int so;
    ss >> so;
    return so;
}

void giaiBai() {
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++) {
        if ((i < s.length() - 1 && s[i + 1] != '0') || i == s.length() - 1) {
            int so1 = chuyenSo(s.substr(0, i + 1));
            int so2 = chuyenSo(s.substr(i + 1));
            if (so1 < so2) {
                cout << so1 << " " << so2 << endl;
                return;
            }
        }
    }
    cout << "-1" << endl;
}

int main() {
    giaiBai();
    return 0;
}

B. Hoán vị và Xóa bỏ

Bài toán này sử dụng thuật toán tham lam. Đầu tiên, chúng ta đếm số lượng ký tự '0' và '1' trong chuỗi. Sau đó, chúng ta duyệt lại chuỗi, thay thế '1' bằng '0' và ngược lại. Khi một trong hai loại ký tự hết, chúng ta biết rằng các ký tự còn lại cần bị xóa, và kết quả là độ dài chuỗi trừ vị trí hiện tại.

#include <iostream>
#include <string>
using namespace std;

void giaiBai() {
    string s;
    cin >> s;
    int dem0 = 0, dem1 = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '0') dem0++;
        else dem1++;
    }
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '1') dem0--;
        else dem1--;
        if (dem0 < 0 || dem1 < 0) {
            cout << s.length() - i << endl;
            return;
        }
    }
    cout << 0 << endl;
}

int main() {
    giaiBai();
    return 0;
}

C. Trò chơi với Tập hợp đa

Chúng ta sử dụng một mảng để đếm số lượng các lũy thừa của 2. Ví dụ, dem[2] biểu thị số lượng 2 mũ 2. Khi kiểm tra một số có thể được tạo từ các số hiện có, chúng ta sao chép mảng dem, sau đó duyệt từ bit thấp đến bit cao của số cần kiểm tra (vì các bit thấp có thể tạo thành bit cao, nhưng ngược lại không đúng). Nếu bit thứ i của số là 1 và dem[i] >= 1, chúng ta giảm dem[i] đi 1 và thêm dem[i]/2 vào vị trí bit cao hơn. Nếu dem[i] == 0, nghĩa là không thể tạo số đó, chúng ta in "NO". Nếu duyệt hết mảng, chúng ta in "YES".

#include <iostream>
#include <cstring>
using namespace std;

int dem[32];

void giaiBai() {
    int thaoTac, so;
    cin >> thaoTac >> so;
    if (thaoTac == 1) {
        dem[so]++;
    } else {
        int saoChep[32];
        memcpy(saoChep, dem, sizeof(dem));
        for (int i = 0; i < 31; i++) {
            if (so & 1) {
                if (saoChep[i]) {
                    saoChep[i]--;
                } else {
                    cout << "NO" << endl;
                    return;
                }
            }
            so >>= 1;
            if (i < 30) {
                saoChep[i + 1] += saoChep[i] / 2;
            }
        }
        cout << "YES" << endl;
    }
}

int main() {
    giaiBai();
    return 0;
}

D. Thu gọn Mảng

Bài toán sử dụng phương pháp quy hoạch động. Chúng ta sử dụng dp(i, 0/1) để biểu thị việc có chọn số thứ i hay không, last_min(i) để biểu thị chỉ số của số gần nhất và nhỏ hơn nums[i] trong khoảng từ 1 đến i-1, và sum[i] để biểu thị tổng số mảng có thể đạt được từ i số đầu tiên.

#include <iostream>
#include <stack>
using namespace std;

const int N = 3e5 + 10, MOD = 998244353;
// dp(i, 0/1) biểu thị việc có chọn số thứ i hay không
// last_min(i) biểu thị chỉ số của số gần nhất và nhỏ hơn nums[i] trong khoảng từ 1 đến i-1
// sum[i] biểu thị tổng số mảng có thể đạt được từ i số đầu tiên
long long dp[N][2], last_min[N], sum[N];
long long nums[N];
int n;

void giaiBai() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> nums[i];
        last_min[i] = 0;
        sum[i] = 0;
        dp[i][0] = dp[i][1] = 0;
    }
    
    stack<int> nganXep; // Sử dụng stack đơn điệu để xử lý last_min
    for (int i = 1; i <= n; i++) {
        while (nganXep.size() && nums[nganXep.top()] > nums[i]) {
            nganXep.pop();
        }
        if (nganXep.size()) {
            last_min[i] = nganXep.top();
        }
        nganXep.push(i);
    }
    
    dp[0][0] = 1;
    sum[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (last_min[i]) {
            // Nếu chọn nums[i], cần trừ đi các trường hợp chứa last_min[i]
            dp[i][1] = (sum[i - 1] - sum[last_min[i] - 1] + dp[last_min[i]][0] + MOD) % MOD;
            // Nếu không chọn nums[i], thêm tất cả các trường hợp của last_min
            dp[i][0] = (dp[last_min[i]][1] + dp[last_min[i]][0]) % MOD;
        } else {
            // Nếu không có số nào nhỏ hơn nums[i], nums[i] luôn có thể chọn
            dp[i][1] = sum[i - 1];
        }
        // Cộng dồn tổng số cách
        sum[i] = (sum[i - 1] + dp[i][1]) % MOD;
    }
    cout << (dp[n][0] + dp[n][1]) % MOD << endl;
}

int main() {
    giaiBai();
    return 0;
}