Bài A: Thống kê bài tập hoàn thành

Đây là bài kiểm tra cơ bản, yêu cầu đếm số lượng chữ cái trong chuỗi đầu vào thỏa mãn điều kiện: số lần xuất hiện của chữ cái phải lớn hơn hoặc bằng vị trí tương ứng trong bảng chữ cái (A=1, B=2,...). Sử dụng mảng đếm để lưu tần suất xuất hiện, sau đó kiểm tra điều kiện cho từng chữ cái.

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

void giaiQuyet() {
    int doDai;
    cin >> doDai;
    string chuoi;
    cin >> chuoi;
    
    int dem[26] = {0};
    for (char c : chuoi) {
        dem[c - 'A']++;
    }
    
    int ketQua = 0;
    for (int i = 0; i < 26; i++) {
        if (dem[i] >= i + 1) ketQua++;
    }
    
    cout << ketQua << endl;
}

Bài B: Sắp xếp chuỗi số

Cần tạo dãy số có k phần tử đầu tăng dần từ 1 đến k, phần còn lại giảm dần từ n xuống k+1. Thực hiện bằng cách in lần lượt các giá trị theo thứ tự yêu cầu.

void sinhDaySo() {
    int n, k;
    cin >> n >> k;
    
    for (int i = 1; i <= k; i++) {
        cout << i << " ";
    }
    for (int i = n; i > k; i--) {
        cout << i << " ";
    }
    cout << endl;
}

Bài C: Tối ưu hóa kinh nghiệm

Sử dụng tiền tố và giá trị tối ưu để tính toán hiệu quả. Tính mảng tổng tiền tố cho mảng a và mảng giá trị lớn nhất cho mảng b. Với mỗi vị trí i, tính toán kinh nghiệm tối đa có thể đạt được.

typedef long long ll;
const int MAX = 200005;

void toiUuHoa() {
    int soNhiemVu, gioTroChoi;
    cin >> soNhiemVu >> gioTroChoi;
    
    vector<ll> tongTienTo(soNhiemVu + 1, 0);
    vector<ll> giaTriMax(soNhiemVu + 1, 0);
    
    for (int i = 1; i <= soNhiemVu; i++) {
        int giaTriA;
        cin >> giaTriA;
        tongTienTo[i] = tongTienTo[i-1] + giaTriA;
    }
    
    for (int i = 1; i <= soNhiemVu; i++) {
        int giaTriB;
        cin >> giaTriB;
        giaTriMax[i] = max(giaTriMax[i-1], (ll)giaTriB);
    }
    
    ll kinhNghiemToiDa = 0;
    for (int i = 0; i <= soNhiemVu; i++) {
        if (i > gioTroChoi) break;
        ll hienTai = tongTienTo[i] + giaTriMax[i] * max(0LL, gioTroChoi - i);
        kinhNghiemToiDa = max(kinhNghiemToiDa, hienTai);
    }
    
    cout << kinhNghiemToiDa << endl;
}

Bài D: Tối ưu ba hoạt động

Giải pháp tối ưu bằng cách sắp xếp và kiểm tra các trường hợp kết hợp. Sử dụng cấu trúc dữ liệu để lưu giá trị và chỉ số, sau đó tìm bộ ba giá trị lớn nhất với các chỉ số khác nhau.

struct HoatDong {
    int giaTri;
    int chiSo;
};

void toiUuBaHoatDong() {
    int n;
    cin >> n;
    
    vector<HoatDong> A(n), B(n), C(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i].giaTri;
        A[i].chiSo = i;
    }
    // Lặp tương tự cho mảng B và C
    
    auto sapXep = [](const HoatDong& x, const HoatDong& y) {
        return x.giaTri > y.giaTri;
    };
    sort(A.begin(), A.end(), sapXep);
    sort(B.begin(), B.end(), sapXep);
    sort(C.begin(), C.end(), sapXep);
    
    auto timGiaTri = [&](const vector<HoatDong>& x, const vector<HoatDong>& y, 
                        int chiSo1, int chiSo2) -> int {
        for (int i = 0; i < n; i++) {
            if (y[i].chiSo != chiSo1 && y[i].chiSo != chiSo2) {
                return y[i].giaTri;
            }
        }
        return 0;
    };
    
    ll ketQuaToiDa = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                if (A[i].chiSo != B[j].chiSo && 
                    A[i].chiSo != C[k].chiSo &&
                    B[j].chiSo != C[k].chiSo) {
                    ketQuaToiDa = max(ketQuaToiDa, 
                        (ll)A[i].giaTri + B[j].giaTri + C[k].giaTri);
                }
            }
        }
    }
    cout << ketQuaToiDa << endl;
}

Bài E: Trò chơi với bi

Sắp xếp các phần tử theo tổng a[i] + b[i] giảm dần. Sau đó luân phiên loại bỏ giá trị từ hai mảng theo thứ tự chẵn/lẻ để tính toán điểm số tối ưu.

void troChoiBi() {
    int n;
    cin >> n;
    
    vector<int> 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<pair<int, int>> danhSach;
    for (int i = 0; i < n; i++) {
        danhSach.push_back({a[i] + b[i], i});
    }
    
    sort(danhSach.rbegin(), danhSach.rend());
    
    int diem = 0;
    for (int i = 0; i < n; i++) {
        int chiSo = danhSach[i].second;
        if (i % 2 == 0) {
            diem += (a[chiSo] - 1);
        } else {
            diem -= (b[chiSo] - 1);
        }
    }
    
    cout << diem << endl;
}

Bài F: Cạnh tranh lập trình

Áp dụng duyệt cây và phân tích cấu trúc cây. Với mỗi nút, tính toán khả năng kết hợp dựa trên kích thước cây con. Sử dụng chiến lược tham lam để xác định số cặp tối đa có thể tạo thành.

const int MAX_N = 200010;
vector<int> ke[MAX_N];
int kichThuocCay[MAX_N];
int ketQua = 0;

int tinhKichThuoc(int u) {
    kichThuocCay[u] = 1;
    for (int v : ke[u]) {
        kichThuocCay[u] += tinhKichThuoc(v);
    }
    return kichThuocCay[u];
}

void duyetCay(int u, int daKetHop) {
    daKetHop = max(0, daKetHop - 1);
    int tongCon = 0;
    int cayConLonNhat = 0;
    
    for (int v : ke[u]) {
        tongCon += kichThuocCay[v];
        if (kichThuocCay[v] > kichThuocCay[cayConLonNhat]) {
            cayConLonNhat = v;
        }
    }
    
    if (cayConLonNhat == 0) return;
    
    if (kichThuocCay[cayConLonNhat] <= tongCon / 2) {
        ketQua += (tongCon - daKetHop) / 2;
    } else {
        int conLai = tongCon - kichThuocCay[cayConLonNhat];
        ketQua += conLai;
        duyetCay(cayConLonNhat, daKetHop + conLai);
    }
}

void giaiBaiF() {
    int n;
    cin >> n;
    
    for (int i = 2; i <= n; i++) {
        int cha;
        cin >> cha;
        ke[cha].push_back(i);
    }
    
    tinhKichThuoc(1);
    duyetCay(1, 0);
    cout << ketQua << endl;
}