Bài 1: Tổng số cặp số tốt I

Đối với bài toán này, chúng ta cần đếm số lượng cặp chỉ số (i, j) sao cho nums1[i] chia hết cho nums2[j] * k. Do giới hạn kích thước của mảng là nhỏ (n, m <= 50), chúng ta có thể sử dụng phương pháp mô phỏng trực tiếp (brute-force) bằng cách duyệt qua tất cả các cặp có thể.

class Solution {
public:
    int numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int count = 0;
        for (int x : nums1) {
            for (int y : nums2) {
                if (x % (y * k) == 0) {
                    count++;
                }
            }
        }
        return count;
    }
};

Bài 2: Nén chuỗi III

Yêu cầu của bài toán là nén chuỗi đầu vào theo nguyên tắc Run-Length Encoding nhưng với một ràng buộc đặc biệt: mỗi nhóm kí tự liên tiếp không được vượt quá 9. Chúng ta sẽ duyệt qua chuỗi, đếm số lượng kí tự giống nhau liên tiếp. Khi đạt tới giới hạn 9 hoặc gặp kí tự khác, ta thêm số lượng và kí tự đó vào kết quả, rồi reset bộ đếm.

class Solution {
public:
    string compressedString(string word) {
        string result;
        int i = 0;
        int n = word.length();
        while (i < n) {
            char currentChar = word[i];
            int runLength = 0;
            // Đếm số lượng kí tự liên tiếp, tối đa 9
            while (i < n && word[i] == currentChar && runLength < 9) {
                i++;
                runLength++;
            }
            result.push_back(runLength + '0');
            result.push_back(currentChar);
        }
        return result;
    }
};

Bài 3: Tổng số cặp số tốt II

Với phiên bản này, giới hạn dữ liệu tăng lên đáng kể khiến phương pháp vét cạn trở nên không khả thi. Thay vào đó, ta sử dụng phương pháp đóng góp kết hợp với Hash Map. Đầu tiên, ta lưu tần suất xuất hiện của các giá trị nums2[j] * k. Sau đó, với từng phần tử x trong nums1, ta liệt kê tất cả các ước số của x. Tổng hợp tần suất của các ước số này từ Map sẽ cho ta kết quả.

class Solution {
public:
    long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        unordered_map<long long, int> frequency;
        // Lưu tần số của các bội số k trong nums2
        for (int val : nums2) {
            long long key = (long long)val * k;
            frequency[key]++;
        }
        
        long long totalPairs = 0;
        for (int x : nums1) {
            // Duyệt các ước số của x
            for (long long d = 1; d * d <= x; ++d) {
                if (x % d == 0) {
                    if (frequency.count(d)) totalPairs += frequency[d];
                    long long complement = x / d;
                    if (complement != d && frequency.count(complement)) {
                        totalPairs += frequency[complement];
                    }
                }
            }
        }
        return totalPairs;
    }
};

Bài 4: Tổng lớn nhất của dãy con không chứa phần tử kề nhau

Đây là một biến thể của bài toán "House Robber" kinh điển nhưng yêu cầu xử lý các thao tác cập nhật giá trị trên mảng. Để giải quyết hiệu quả, ta sử dụng Cây phân đoạn (Segment Tree). Mỗi nút của cây sẽ lưu trữ 4 trạng thái giá trị lớn nhất của đoạn tương ứng: trạng thái khi phần tử đầu tiên được chọn/bỏ qua và trạng thái khi phần tử cuối cùng được chọn/bỏ qua. Khi gộp hai nút con, ta cần đảm bảo không chọn hai phần tử kề nhau ở điểm nối.

class Solution {
public:
    const int MOD = 1e9 + 7;
    vector<array<long long, 4>> tree;

    // Gộp hai nút con left và right
    // Chỉ số: 0: đầu bỏ qua, 1: đầu chọn, 2: cuối bỏ qua, 3: cuối chọn
    array<long long, 4> merge(const array<long long, 4>& left, const array<long long, 4>& right) {
        array<long long, 4> node;
        node[0] = max(left[0] + right[0], left[0] + right[1]); // Đầu mới bỏ qua
        node[1] = left[1] + right[0];                         // Đầu mới chọn (phải nối với đoạn sau bỏ qua)
        node[2] = max(left[2] + right[2], left[3] + right[2]); // Cuối mới bỏ qua
        node[3] = left[2] + right[3];                         // Cuối mới chọn (phải nối với đoạn trước bỏ qua)
        return node;
    }

    void build(int idx, int l, int r, const vector<int>& nums) {
        if (l == r) {
            int val = max(nums[l], 0);
            tree[idx] = {0, val, 0, val};
            return;
        }
        int mid = l + (r - l) / 2;
        build(idx * 2, l, mid, nums);
        build(idx * 2 + 1, mid + 1, r, nums);
        tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
    }

    void update(int idx, int l, int r, int pos, int newVal) {
        if (l == r) {
            int val = max(newVal, 0);
            tree[idx] = {0, val, 0, val};
            return;
        }
        int mid = l + (r - l) / 2;
        if (pos <= mid) update(idx * 2, l, mid, pos, newVal);
        else update(idx * 2 + 1, mid + 1, r, pos, newVal);
        tree[idx] = merge(tree[idx * 2], tree[idx * 2 + 1]);
    }

    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        tree.resize(4 * n + 5);
        build(1, 0, n - 1, nums);
        
        long long result = 0;
        for (auto& q : queries) {
            update(1, 0, n - 1, q[0], q[1]);
            // Kết quả tốt nhất là max giữa trạng thái đầu được chọn hoặc bỏ qua của gốc cây
            long long currentMax = max(tree[1][0], tree[1][1]);
            result = (result + currentMax) % MOD;
        }
        return result;
    }
};