Bài viết này khám phá các giải pháp cho một số vấn đề thuật toán, bao gồm các bài toán từ một cuộc thi lập trình và một số bài toán quy hoạch động phức tạp hơn.

Các Bài Toán từ Cuộc Thi Lập Trình

Bài Toán 1: Chia nhóm

Bài toán yêu cầu tính số lượng nhóm tối thiểu cần thiết để chứa một số lượng phần tử nhất định, biết rằng mỗi nhóm có một sức chứa cố định. Đây là một bài toán cơ bản, có thể giải quyết bằng cách sử dụng phép chia và làm tròn lên.

Ví dụ: Nếu có y phần tử và mỗi nhóm chứa được x phần tử, số nhóm cần thiết là y/x nếu y chia hết cho x, hoặc y/x + 1 nếu không chia hết.

#include <iostream>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL); // Tăng tốc độ nhập xuất
    
    int tongSoPhanTu, kichThuocMoiNhom;
    std::cin >> tongSoPhanTu >> kichThuocMoiNhom;
    
    int ketQua = tongSoPhanTu / kichThuocMoiNhom;
    if (tongSoPhanTu % kichThuocMoiNhom != 0) {
        ketQua++; // Nếu có phần dư, cần thêm một nhóm
    }
    
    std::cout << ketQua << '\n';
    
    return 0;
}

Bài Toán 2: Tổng lớn nhất

Cho một dãy các số nguyên, nhiệm vụ là tìm tổng lớn nhất có thể đạt được bằng cách loại bỏ một số phần tử. Chiến lược tối ưu ở đây là một cách tiếp cận tham lam: chỉ giữ lại và cộng tất cả các số dương. Bất kỳ số âm nào cũng sẽ làm giảm tổng, trong khi số 0 không ảnh hưởng.

#include <iostream>

// Hàm tính tổng lớn nhất cho một trường hợp kiểm thử
long long calculateMaxSum() {
    int countElements, unusedLimit; // unusedLimit tương ứng với 'k' trong đề gốc, không dùng trong logic này
    std::cin >> countElements >> unusedLimit;
    
    long long currentSum = 0;
    for (int i = 0; i < countElements; ++i) {
        int elementValue;
        std::cin >> elementValue;
        if (elementValue > 0) {
            currentSum += elementValue; // Chỉ cộng các số dương
        }
    }
    return currentSum;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int testCases;
    std::cin >> testCases;
    while (testCases--) {
        std::cout << calculateMaxSum() << '\n';
    }
    
    return 0;
}

Bài Toán 3: Chuỗi nhị phân tối giản

Bài toán yêu cầu thực hiện các phép loại bỏ trên một chuỗi nhị phân: nếu hai ký tự liền kề giống nhau, chúng có thể bị loại bỏ. Mục tiêu là tìm số lượng cặp ký tự tối đa có thể loại bỏ. Ví dụ, "00110" có thể trở thành "00" rồi "110", sau đó "11" thành "0", cuối cùng là chuỗi rỗng. Số thao tác tối đa bằng một nửa độ dài chuỗi còn lại sau khi không thể loại bỏ thêm.

Một cách hiệu quả để giải quyết vấn đề này là sử dụng cấu trúc dữ liệu ngăn xếp (stack). Khi duyệt qua chuỗi, nếu ký tự hiện tại khớp với ký tự ở đỉnh ngăn xếp, chúng ta có thể coi như chúng triệt tiêu nhau và loại bỏ ký tự ở đỉnh (pop). Ngược lại, nếu không khớp, ký tự hiện tại được thêm vào ngăn xếp (push).

#include <iostream>
#include <string>
#include <stack>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    
    int numTestCases;
    std::cin >> numTestCases;
    while (numTestCases--) {
        int stringLength;
        std::string binaryString;
        std::cin >> stringLength >> binaryString;

        std::stack<char> charStack; // Ngăn xếp để xử lý chuỗi
        for (char currentChar : binaryString) {
            if (!charStack.empty() && charStack.top() == currentChar) {
                charStack.pop(); // Nếu ký tự hiện tại khớp với đỉnh ngăn xếp, loại bỏ
            } else {
                charStack.push(currentChar); // Ngược lại, thêm vào ngăn xếp
            }
        }
        // Số lượng thao tác là một nửa số ký tự còn lại trong ngăn xếp
        std::cout << charStack.size() / 2 << '\n';
    }
    return 0;
}

Bài Toán 4: Số thao tác tối thiểu

Cho hai số nguyên dương A và B, chúng ta cần tìm số thao tác tối thiểu (1, 2 hoặc 3) để chúng trở nên "liên quan". Hai số được gọi là liên quan nếu chúng bằng nhau (A == B) hoặc phép AND bitwise của chúng bằng 0 ((A & B) == 0).

Các thao tác có thể thực hiện trên A và B bao gồm: A & B, A | B, A ^ B, và GCD(A, B). Chúng ta có thể tạo một số mới Z bằng cách áp dụng một trong các phép toán này cho A và B, hoặc chính A với A, hoặc B với B.

• 1 thao tác: Nếu A và B đã liên quan ngay từ đầu.
• 2 thao tác: Nếu có thể thực hiện một phép toán (ví dụ: Z = A & B) sao cho Z và A liên quan, hoặc Z và B liên quan.
• 3 thao tác: Trong mọi trường hợp khác, luôn có thể đạt được trong 3 thao tác. Điều này là do ta có thể tạo ra hai số giống nhau trong hai bước, rồi XOR chúng để ra 0, khiến chúng liên quan.

#include <iostream>
#include <numeric> // Cho std::gcd

// Hàm kiểm tra xem hai số có "liên quan trực tiếp" hay không
bool checkDirectRelation(long long val1, long long val2) {
    return (val1 == val2) || ((val1 & val2) == 0);
}

// Hàm tính số thao tác tối thiểu
void calculateMinOperations() {
    long long valA, valB;
    std::cin >> valA >> valB;

    // Trường hợp 1: valA và valB đã liên quan trực tiếp
    if (checkDirectRelation(valA, valB)) {
        std::cout << "1\n";
        return;
    }

    // Trường hợp 2: Có thể tạo ra một số mới để chúng trở nên liên quan trong 2 bước
    long long resAnd = valA & valB;
    long long resOr = valA | valB;
    long long resXor = valA ^ valB;
    long long resGcd = std::gcd(valA, valB); // Ước chung lớn nhất

    // Kiểm tra xem bất kỳ giá trị nào được tạo ra (resAnd, resOr, resXor, resGcd)
    // có thể tạo thành mối liên hệ trực tiếp với valA hoặc valB hay không.
    if (checkDirectRelation(resAnd, valA) || checkDirectRelation(resAnd, valB) ||
        checkDirectRelation(resOr, valA) || checkDirectRelation(resOr, valB) ||
        checkDirectRelation(resXor, valA) || checkDirectRelation(resXor, valB) ||
        checkDirectRelation(resGcd, valA) || checkDirectRelation(resGcd, valB)) {
        std::cout << "2\n";
        return;
    }

    // Trường hợp 3: Nếu không nằm trong 2 trường hợp trên, 3 thao tác là đủ
    std::cout << "3\n";
}

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

Bài Toán Quy Hoạch Động: Vấn đề Cái Túi (Knapsack)

Bài Toán Cái Túi 0/1 Cơ Bản

Bài toán cái túi 0/1 cổ điển yêu cầu chọn một tập hợp các vật phẩm, mỗi vật phẩm có một trọng lượng (chi phí) và một giá trị, sao cho tổng trọng lượng không vượt quá một sức chứa cho trước, đồng thời tối đa hóa tổng giá trị. Đây là một vấn đề quy hoạch động tiêu chuẩn.

#include <iostream>
#include <vector>
#include <algorithm> // Cho std::max

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

    int capacityLimit, numItems;
    std::cin >> capacityLimit >> numItems;

    std::vector<int> itemCosts(numItems + 1);
    std::vector<int> itemValues(numItems + 1);
    for (int i = 1; i <= numItems; ++i) {
        std::cin >> itemCosts[i] >> itemValues[i];
    }

    // Bảng DP: dpTable[i][j] lưu giá trị tối đa với i vật phẩm và sức chứa j
    std::vector<std::vector<int>> dpTable(numItems + 1, std::vector<int>(capacityLimit + 1, 0));

    for (int i = 1; i <= numItems; ++i) { // Duyệt qua từng vật phẩm
        for (int j = 1; j <= capacityLimit; ++j) { // Duyệt qua từng mức sức chứa
            if (j >= itemCosts[i]) {
                // Có hai lựa chọn:
                // 1. Không chọn vật phẩm i: Giá trị là dpTable[i-1][j]
                // 2. Chọn vật phẩm i: Giá trị là dpTable[i-1][j - itemCosts[i]] + itemValues[i]
                dpTable[i][j] = std::max(dpTable[i - 1][j], dpTable[i - 1][j - itemCosts[i]] + itemValues[i]);
            } else {
                // Không thể chọn vật phẩm i vì sức chứa không đủ
                dpTable[i][j] = dpTable[i - 1][j];
            }
        }
    }

    std::cout << dpTable[numItems][capacityLimit] << '\n';

    return 0;
}
```

#include <iostream>
#include <vector>
#include <numeric> // Cho std::iota
#include <algorithm> // Cho std::max

const int MAX_ELEMENTS = 10005; 

// Cấu trúc dữ liệu Union-Find
std::vector<int> parent(MAX_ELEMENTS);
std::vector<int> groupTotalCost(MAX_ELEMENTS);   // Tổng chi phí của nhóm (gốc tại chỉ mục này)
std::vector<int> groupTotalValue(MAX_ELEMENTS);  // Tổng lợi nhuận của nhóm (gốc tại chỉ mục này)

// Hàm tìm gốc của một tập hợp với nén đường đi
int findSet(int i) {
    if (parent[i] == i)
        return i;
    return parent[i] = findSet(parent[i]);
}

// Hàm hợp nhất hai tập hợp
void uniteSets(int i, int j) {
    int rootI = findSet(i);
    int rootJ = findSet(j);

    if (rootI != rootJ) {
        // Hợp nhất rootJ vào rootI
        parent[rootJ] = rootI;
        groupTotalCost[rootI] += groupTotalCost[rootJ];
        groupTotalValue[rootI] += groupTotalValue[rootJ];
    }
}

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

    // Khởi tạo Union-Find: mỗi phần tử là một tập hợp riêng
    std::iota(parent.begin(), parent.end(), 0); 

    int numNodes, numRelations, budgetCapacity;
    std::cin >> numNodes >> numRelations >> budgetCapacity;

    // Đọc chi phí và giá trị ban đầu cho từng vật phẩm (từng nút)
    for (int i = 1; i <= numNodes; ++i) {
        std::cin >> groupTotalCost[i] >> groupTotalValue[i]; // Ban đầu, mỗi vật phẩm là một nhóm
    }

    // Xử lý các mối quan hệ để hình thành các nhóm
    for (int k = 0; k < numRelations; ++k) {
        int nodeU, nodeV;
        std::cin >> nodeU >> nodeV;
        uniteSets(nodeU, nodeV);
    }

    // Sau khi tất cả các phép hợp nhất hoàn tất, thu thập các "vật phẩm" đã tổng hợp (gốc của các thành phần liên thông)
    std::vector<int> finalItemCosts;
    std::vector<int> finalItemValues;

    for (int i = 1; i <= numNodes; ++i) {
        if (parent[i] == i) { // Nếu 'i' là gốc của một thành phần
            finalItemCosts.push_back(groupTotalCost[i]);
            finalItemValues.push_back(groupTotalValue[i]);
        }
    }

    // Áp dụng thuật toán Quy hoạch động cái túi 0/1 với mảng 1 chiều
    std::vector<int> dpKnapsack(budgetCapacity + 1, 0);

    for (size_t i = 0; i < finalItemCosts.size(); ++i) {
        int currentCost = finalItemCosts[i];
        int currentValue = finalItemValues[i];
        for (int j = budgetCapacity; j >= currentCost; --j) {
            dpKnapsack[j] = std::max(dpKnapsack[j], dpKnapsack[j - currentCost] + currentValue);
        }
    }

    std::cout << dpKnapsack[budgetCapacity] << '\n';

    return 0;
}