Bài A: Xoay vòng dãy số

Bài toán yêu cầu chúng ta thực hiện một phép biến đổi trên dãy số nguyên. Cụ thể, cần đưa k phần tử cuối cùng của dãy lên đầu tiên, giữ nguyên thứ tự tương đối, sau đó nối tiếp bởi các phần tử còn lại.

Hướng tiếp cận

Đây là một bài toán thao tác cơ bản trên mảng. Chúng ta không cần thực hiện việc xoay vòng thực sự trên bộ nhớ mà chỉ cần thay đổi thứ tự khi in kết quả. Đầu tiên, duyệt và in các phần tử từ vị trí n - k + 1 đến n, sau đó in tiếp các phần tử từ vị trí 1 đến n - k.

Mã nguồn tham khảo

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // Tối ưu hóa tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;

    vector<int> data(n);
    for (int i = 0; i < n; ++i) {
        cin >> data[i];
    }

    // In k phần tử cuối trước
    for (int i = n - k; i < n; ++i) {
        cout << data[i] << " ";
    }

    // In các phần tử còn lại
    for (int i = 0; i < n - k; ++i) {
        cout << data[i] << " ";
    }

    cout << endl;
    return 0;
}

Bài B: Giảm giá trị hai phần tử lớn nhất

Chúng ta có một dãy số nguyên dương. Trong mỗi bước, chọn hai phần tử lớn nhất hiện có và giảm mỗi phần tử đi 1 đơn vị. Quá trình dừng lại khi số lượng phần tử dương còn lại nhỏ hơn hoặc bằng 1. Yêu cầu tính tổng số bước thực hiện.

Hướng tiếp cận

Phương pháp mô phỏng trực tiếp là phù hợp nhất. Tại mỗi vòng lặp, đếm số lượng phần tử dương. Nếu lớn hơn 1, sắp xếp lại dãy để tìm hai phần tử lớn nhất, giảm giá trị của chúng và tăng biến đếm bước lên. Lặp lại cho đến khi điều kiện dừng được thỏa mãn.

Mã nguồn tham khảo

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

using namespace std;

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

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    int operations = 0;
    while (true) {
        int positive_count = 0;
        for (int val : arr) {
            if (val > 0) positive_count++;
        }

        if (positive_count <= 1) break;

        operations++;
        // Sắp xếp giảm dần để lấy 2 phần tử lớn nhất ở đầu
        sort(arr.begin(), arr.end(), greater<int>());
        
        arr[0]--;
        arr[1]--;
    }

    cout << operations << endl;
    return 0;
}

Bài C: Đòn tấn công bộ ba

Nhân vật thực hiện tấn công theo chu kỳ 3 lượt: lượt 1 gây 1 sát thương, lượt 2 gây 1 sát thương, lượt 3 gây 3 sát thương. Tổng sát thương mỗi chu kỳ là 5. Cần tính tổng lượt đánh để tiêu diệt hết các quái vật với máu cho trước.

Hướng tiếp cận

Thay vì mô phỏng từng lượt đánh cho mỗi quái vật (dễ gây超时), ta nhận thấy quy luật sát thương lặp lại mỗi 3 lượt. Với mỗi quái vật, ta tính số chu kỳ trọn vẹn (mỗi chu kỳ 5 máu tốn 3 lượt) và xử lý phần máu dư riêng biệt. Cần lưu trữ trạng thái lượt đánh hiện tại để chuyển tiếp giữa các quái vật.

Mã nguồn tham khảo

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

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

    int n;
    cin >> n;

    vector<ll> hp(n);
    for (int i = 0; i < n; ++i) {
        cin >> hp[i];
    }

    ll total_turns = 0;
    int current_state = 1; // 1, 2, hoặc 3 tương ứng lượt trong chu kỳ

    for (int i = 0; i < n; ++i) {
        ll health = hp[i];

        // Xử lý phần chuyển tiếp trạng thái từ quái vật trước
        if (current_state == 2) {
            health -= 1;
            total_turns++;
            current_state = 3;
            if (health <= 0) continue;
        } else if (current_state == 3) {
            health -= 3;
            total_turns++;
            current_state = 1;
            if (health <= 0) continue;
        }

        // Xử lý các chu kỳ trọn vẹn (5 máu = 3 lượt)
        ll cycles = health / 5;
        total_turns += cycles * 3;
        health %= 5;

        // Xử lý phần máu còn lại
        if (health == 1) {
            total_turns += 1;
            current_state = 2;
        } else if (health == 2) {
            total_turns += 2;
            current_state = 3;
        } else if (health >= 3) {
            total_turns += 3;
            current_state = 1;
        }
    }

    cout << total_turns << endl;
    return 0;
}

Bài D: Cây con tối thiểu chứa các đỉnh đặc biệt

Cho một cây và một tập hợp các đỉnh đặc biệt. Cần tìm số lượng đỉnh ít nhất thuộc cây con sao cho tất cả các đỉnh đặc biệt đều được kết nối với nhau trong cây con đó.

Hướng tiếp cận

Bài toán có thể giải quyết bằng DFS. Chọn một đỉnh đặc biệt làm gốc. Duyệt cây từ gốc xuống, tại mỗi nút, kiểm tra xem cây con rooted tại nút đó có chứa đỉnh đặc biệt nào không. Nếu có, đánh dấu nút hiện tại là thuộc cây con cần tìm. Kết quả là tổng số nút được đánh dấu.

Mã nguồn tham khảo

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 200005;
vector<int> adjacency[MAXN];
bool has_special[MAXN];
int n, k;

void dfs(int u, int parent) {
    for (int v : adjacency[u]) {
        if (v == parent) continue;
        dfs(v, u);
        // Nếu cây con chứa đỉnh đặc biệt, nút hiện tại cũng được giữ lại
        has_special[u] = has_special[u] || has_special[v];
    }
}

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

    cin >> n >> k;

    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adjacency[u].push_back(v);
        adjacency[v].push_back(u);
    }

    int root = 0;
    for (int i = 0; i < k; ++i) {
        int node;
        cin >> node;
        has_special[node] = true;
        if (root == 0) root = node; // Chọn đỉnh đặc biệt đầu tiên làm gốc
    }

    dfs(root, 0);

    int count = 0;
    for (int i = 1; i <= n; ++i) {
        if (has_special[i]) count++;
    }

    cout << count << endl;
    return 0;
}