A - Mã Trạng Thái

Trong bài toán này, chúng ta cần kiểm tra một mã trạng thái HTTP đã cho. Nếu mã trạng thái nằm trong khoảng từ 200 đến 299 (bao gồm cả hai giá trị biên), điều đó biểu thị một phản hồi thành công. Ngược lại, nó được coi là một lỗi hoặc trạng thái không thành công.

Cách tiếp cận

Bài toán yêu cầu mô phỏng trực tiếp điều kiện kiểm tra mã trạng thái. Chúng ta đọc một số nguyên và áp dụng một câu lệnh điều kiện đơn giản để xác định kết quả.

Mã nguồn C++

#include <iostream> // Để sử dụng cin, cout

void xuLyBaiToanA() {
    int maTrangThai;
    std::cin >> maTrangThai; // Đọc mã trạng thái từ đầu vào

    // Kiểm tra xem mã trạng thái có nằm trong khoảng thành công không
    if (maTrangThai >= 200 && maTrangThai <= 299) {
        std::cout << "Success" << std::endl; // Nếu thành công
    } else {
        std::cout << "Failure" << std::endl; // Nếu không thành công
    }
}

int main() {
    // Tối ưu hóa hiệu suất I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // Bài toán này chỉ chạy một trường hợp thử nghiệm
    xuLyBaiToanA(); 

    return 0;
}

B - Truy Cập Trái Phép

Bài toán này mô phỏng một hệ thống quản lý quyền truy cập cơ bản. Chúng ta được cung cấp một chuỗi các sự kiện bao gồm "login" (đăng nhập), "logout" (đăng xuất), "public" (công khai), và "private" (riêng tư). Nhiệm vụ là đếm số lần một hành động "private" được thực hiện khi người dùng chưa đăng nhập.

Cách tiếp cận

Chúng ta sử dụng một biến boolean để theo dõi trạng thái đăng nhập của người dùng. Ban đầu, người dùng chưa đăng nhập. Khi có sự kiện "login", trạng thái sẽ chuyển thành đã đăng nhập. Khi có sự kiện "logout", trạng thái sẽ chuyển thành chưa đăng nhập. Các sự kiện "public" không ảnh hưởng đến trạng thái hay số lần truy cập trái phép. Đối với sự kiện "private", chúng ta kiểm tra trạng thái đăng nhập hiện tại; nếu người dùng chưa đăng nhập, chúng ta tăng bộ đếm truy cập trái phép.

Mã nguồn C++

#include <iostream> // Để sử dụng cin, cout
#include <string>   // Để đọc chuỗi sự kiện

void xuLyBaiToanB() {
    int soLuongSuKien;
    std::cin >> soLuongSuKien; // Đọc số lượng sự kiện

    bool daDangNhap = false; // Trạng thái đăng nhập ban đầu là chưa đăng nhập
    int demTruyCapTraiPhep = 0; // Khởi tạo bộ đếm truy cập trái phép

    for (int i = 0; i < soLuongSuKien; ++i) {
        std::string loaiSuKien;
        std::cin >> loaiSuKien; // Đọc loại sự kiện

        if (loaiSuKien == "login") {
            daDangNhap = true; // Người dùng đăng nhập
        } else if (loaiSuKien == "logout") {
            daDangNhap = false; // Người dùng đăng xuất
        } else if (loaiSuKien == "private") {
            // Nếu sự kiện là "private" và người dùng chưa đăng nhập
            if (!daDangNhap) {
                demTruyCapTraiPhep++; // Tăng bộ đếm
            }
        }
        // Sự kiện "public" không cần xử lý đặc biệt vì không ảnh hưởng đến bộ đếm hay trạng thái
    }

    std::cout << demTruyCapTraiPhep << std::endl; // In ra tổng số lần truy cập trái phép
}

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

    xuLyBaiToanB();

    return 0;
}

C - K-bonacci

Bài toán yêu cầu tính số hạng thứ N của một dãy K-bonacci, lấy modulo 10^9. Dãy K-bonacci là một khái niệm tổng quát của dãy Fibonacci, trong đó mỗi số hạng sau K số hạng đầu tiên là tổng của K số hạng liền trước đó. Cụ thể:

• F(i) = 1 cho 0 ≤ i < K
• F(i) = F(i-1) + F(i-2) + ... + F(i-K) cho i ≥ K

Cách tiếp cận

Chúng ta có thể sử dụng phương pháp quy hoạch động để giải quyết bài toán này. Để tính F(i), chúng ta cần tổng của K số hạng trước đó. Thay vì tính lại tổng mỗi lần, chúng ta có thể duy trì một tổng động ("sliding window sum"). Khi tính F(i), chúng ta thêm F(i) vào tổng và trừ đi F(i-K) (số hạng đã "trượt" ra khỏi cửa sổ K phần tử). Tất cả các phép toán cần được thực hiện modulo 10^9.

Mã nguồn C++

#include <iostream> // Để sử dụng cin, cout
#include <vector>   // Để sử dụng std::vector

const int MODULO = 1e9; // Modulo là 10^9

void xuLyBaiToanC() {
    int N_idx, K_val;
    std::cin >> N_idx >> K_val; // Đọc N và K

    // N_idx là chỉ số của số hạng cần tìm (0-indexed).
    // Kích thước của vector là N_idx + 1 để chứa các số hạng từ F(0) đến F(N_idx).
    std::vector<long long> fib_k_seq(N_idx + 1); 

    // Các số hạng cơ sở: F(0) đến F(K-1) đều bằng 1
    for (int i = 0; i < K_val && i <= N_idx; ++i) {
        fib_k_seq[i] = 1;
    }

    // Nếu N_idx nhỏ hơn K_val (tức là ta cần tìm một số hạng cơ sở)
    if (N_idx < K_val) {
        std::cout << fib_k_seq[N_idx] << std::endl;
        return;
    }

    long long current_window_sum = K_val; // Tổng của K số hạng đầu tiên (F(0) đến F(K-1))

    // Tính các số hạng từ F(K) đến F(N_idx)
    for (int i = K_val; i <= N_idx; ++i) {
        fib_k_seq[i] = current_window_sum; // F(i) là tổng của K số hạng trước đó
        
        // Cập nhật tổng cửa sổ trượt:
        // Thêm F(i) vào tổng
        current_window_sum = (current_window_sum + fib_k_seq[i]) % MODULO;
        // Trừ đi F(i-K) (số hạng đã trượt ra khỏi cửa sổ)
        current_window_sum = (current_window_sum - fib_k_seq[i - K_val] + MODULO) % MODULO; 
        // Cộng MODULO để đảm bảo kết quả dương khi trừ
    }

    std::cout << fib_k_seq[N_idx] << std::endl; // In ra số hạng F(N_idx)
}

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

    xuLyBaiToanC();

    return 0;
}

D - Điền Giá Trị Hợp Lý

Chúng ta được cho một chuỗi S độ dài N chứa các ký tự 'o', '.', '?', và một số nguyên M. Chúng ta cần thay thế mỗi ký tự '?' bằng 'o' hoặc '.' sao cho chuỗi kết quả tuân thủ các quy tắc sau:

1. Nếu một ký tự là 'o', thì các ký tự liền kề (bên trái và bên phải) của nó phải là '.'.
2. Mục tiêu cuối cùng là tạo ra một chuỗi có số lượng ký tự 'o' nhất định, hoặc theo một tập hợp các quy tắc cụ thể dựa trên số lượng 'o' tiềm năng.

Các quy tắc xử lý cụ thể từ đề bài gốc và mã nguồn được cung cấp có thể được giải thích như sau:

1. Nếu số lượng 'o' ban đầu trong chuỗi S đã bằng M, thì tất cả các ký tự '?' còn lại sẽ được thay thế bằng '.' và in chuỗi.
2. Ngược lại, trước tiên chúng ta phải đảm bảo quy tắc "các ký tự liền kề của 'o' phải là '.'". Điều này có nghĩa là nếu S[i] == 'o', thì S[i-1] và S[i+1] (nếu tồn tại và là '?') sẽ được đặt thành '.'.
3. Sau khi áp dụng bước 2, chúng ta tính toán số lượng 'o' tối đa có thể đặt thêm vào các vị trí '?' còn lại. Việc này được thực hiện bằng cách xem xét từng đoạn ký tự '?' liên tục. Với một đoạn '?' có độ dài L, số lượng 'o' tối đa có thể đặt là (L+1)/2 (ví dụ: "o.o.o" cho L=5). Gọi tổng số lượng 'o' tối đa có thể đặt từ các dấu '?' này là max_potential_o_from_q.
4. Nếu max_potential_o_from_q lớn hơn M (tức là chúng ta có thể đặt quá nhiều 'o'), thì chuỗi S hiện tại (với các '?' chưa được điền và các '.' đã được cố định từ bước 2) sẽ được in ra.
5. Nếu max_potential_o_from_q nhỏ hơn hoặc bằng M, thì chúng ta sẽ điền các ký tự '?' một cách cụ thể: chỉ những đoạn '?' có độ dài lẻ mới được điền theo mẫu "o.o.o...". Các đoạn '?' có độ dài chẵn sẽ vẫn giữ nguyên là '?'. Sau đó, chuỗi S đã được cập nhật sẽ được in ra.

Cách tiếp cận

Chúng ta sẽ tạo một bản sao của chuỗi để thực hiện các thay đổi. Đầu tiên, xử lý trường hợp cơ sở nếu số 'o' ban đầu đã đạt M. Sau đó, quét chuỗi để đặt các dấu '.' bắt buộc xung quanh các 'o' hiện có. Tiếp theo, tính toán số 'o' tối đa có thể thêm từ các vị trí '?'. Dựa trên so sánh này với M, chúng ta sẽ quyết định cách điền các dấu '?'.

Mã nguồn C++

#include <iostream>
#include <string>
#include <vector>
#include <numeric> // For std::count

void xuLyBaiToanD() {
    int N_len, M_target;
    std::cin >> N_len >> M_target;
    std::string current_str;
    std::cin >> current_str;

    // Bước 1: Nếu số lượng 'o' ban đầu đã bằng M_target, điền tất cả '?' bằng '.'
    int initial_o_count = std::count(current_str.begin(), current_str.end(), 'o');
    if (initial_o_count == M_target) {
        for (char &ch : current_str) {
            if (ch == '?') {
                ch = '.';
            }
        }
        std::cout << current_str << std::endl;
        return;
    }

    // Bước 2: Đặt các dấu '.' bắt buộc xung quanh các 'o' hiện có
    // Dùng một chuỗi tạm thời để không ảnh hưởng đến việc quét
    std::string temp_str = current_str;
    for (int i = 0; i < N_len; ++i) {
        if (temp_str[i] == 'o') {
            if (i > 0 && current_str[i - 1] == '?') { // Chỉ thay đổi '?' thành '.'
                current_str[i - 1] = '.';
            }
            if (i < N_len - 1 && current_str[i + 1] == '?') { // Chỉ thay đổi '?' thành '.'
                current_str[i + 1] = '.';
            }
        }
    }

    // Bước 3: Tính toán số lượng 'o' tối đa có thể đặt thêm vào các vị trí '?' còn lại
    // sau khi đã cố định các dấu '.' bắt buộc.
    int max_potential_o_from_q = 0;
    for (int i = 0; i < N_len; ++i) {
        if (current_str[i] == '?') {
            int j = i;
            while (j < N_len && current_str[j] == '?') {
                j++;
            }
            int segment_length = j - i;
            max_potential_o_from_q += (segment_length + 1) / 2; // Số 'o' tối đa trong đoạn '?'
            i = j - 1; // Di chuyển con trỏ i đến cuối đoạn '?'
        }
    }

    // Bước 4: Nếu max_potential_o_from_q > M_target, in chuỗi hiện tại (với '?' chưa điền)
    // Đây là một quy tắc đặc biệt của bài toán này.
    if (max_potential_o_from_q > M_target) {
        std::cout << current_str << std::endl;
        return;
    }

    // Bước 5: Nếu max_potential_o_from_q <= M_target, điền các đoạn '?' có độ dài lẻ
    // theo mẫu "o.o.o...", các đoạn chẵn vẫn là '?' (trong mã gốc, không điền gì).
    for (int i = 0; i < N_len; ++i) {
        if (current_str[i] == '?') {
            int j = i;
            while (j < N_len && current_str[j] == '?') {
                j++;
            }
            int segment_length = j - i;

            if (segment_length % 2 == 1) { // Chỉ điền các đoạn có độ dài lẻ
                for (int k = i; k < j; ++k) {
                    // Để đặt 'o' tại k theo mẫu o.o.o..., chúng ta đặt 'o' tại vị trí chẵn (0-indexed tương đối).
                    if ((k - i) % 2 == 0) { 
                        current_str[k] = 'o';
                    } else {
                        current_str[k] = '.';
                    }
                }
            }
            // Các đoạn chẵn sẽ không được điền trong vòng lặp này, giữ nguyên '?'

            i = j - 1; // Di chuyển con trỏ i đến cuối đoạn '?'
        }
    }

    std::cout << current_str << std::endl; // In chuỗi kết quả cuối cùng
}

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

    xuLyBaiToanD();

    return 0;
}

E - Tập Hợp Các Nút Có Thể Đạt Tới

Bài toán này yêu cầu chúng ta xử lý một đồ thị với N nút và M cạnh. Đối với mỗi giá trị k từ 0 đến N-1, chúng ta cần tìm kích thước của một tập hợp các nút j sao cho j > k và j có thể đạt được từ k. Điều kiện bổ sung là tất cả các nút từ 0 đến k phải tạo thành một thành phần liên thông duy nhất. Nếu điều kiện thành phần liên thông không được thỏa mãn, chúng ta in -1.

Cách tiếp cận

Chúng ta sẽ sử dụng cấu trúc dữ liệu Disjoint Set Union (DSU) để theo dõi các thành phần liên thông của các nút từ 0 đến k. Chúng ta sẽ lặp qua k từ 0 đến N-1.

1. Khi xử lý nút k, nó ban đầu được coi là một thành phần liên thông mới.
2. Chúng ta xem xét tất cả các cạnh nối với k.
3. Nếu một cạnh nối k với nút j mà j < k, chúng ta cố gắng hợp nhất (union) các thành phần chứa j và k. Nếu việc hợp nhất thành công, số lượng thành phần liên thông trong dải [0, k] giảm đi một.
4. Nếu một cạnh nối k với nút j mà j > k, nút j này được đưa vào một tập hợp (std::set) các nút tiềm năng có thể đạt được từ [0, k] nhưng nằm ngoài dải hiện tại.
5. Sau khi xử lý tất cả các cạnh của k, chúng ta loại bỏ khỏi tập hợp các nút tiềm năng tất cả các nút có chỉ số nhỏ hơn hoặc bằng k (vì chúng giờ đã nằm trong dải [0, k] và được xử lý).
6. Cuối cùng, nếu tất cả các nút từ 0 đến k tạo thành một thành phần liên thông duy nhất (tức là số lượng thành phần liên thông bằng 1), thì kích thước của tập hợp các nút j > k còn lại chính là câu trả lời. Ngược lại, in -1.

Mã nguồn C++

#include <iostream>     // Để sử dụng cin, cout
#include <vector>       // Để sử dụng std::vector
#include <numeric>      // Để sử dụng std::iota
#include <set>          // Để sử dụng std::set

// Lớp Disjoint Set Union (DSU)
class DisjointSetUnion {
public:
    std::vector<int> parent; // Mảng lưu trữ nút cha của mỗi phần tử
    
    // Khởi tạo DSU với 'n' phần tử, mỗi phần tử là một tập hợp riêng biệt
    DisjointSetUnion(int n) {
        parent.resize(n);
        std::iota(parent.begin(), parent.end(), 0); // parent[i] = i ban đầu
    }

    // Tìm nút cha gốc của một phần tử, sử dụng tối ưu nén đường dẫn
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }

    // Hợp nhất hai tập hợp chứa phần tử 'i' và 'j'
    // Trả về true nếu hai tập hợp được hợp nhất thành công, false nếu đã cùng tập hợp
    bool unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_j] = root_i; // Gắn gốc của j vào gốc của i
            return true;
        }
        return false;
    }
};

void xuLyBaiToanE() {
    int N_nodes, M_edges;
    std::cin >> N_nodes >> M_edges; // Đọc số nút và số cạnh

    // Danh sách kề để lưu trữ các cạnh của đồ thị
    std::vector<std::vector<int>> adj_list(N_nodes);
    for (int i = 0; i < M_edges; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u; --v; // Chuyển sang chỉ số 0-indexed
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }

    DisjointSetUnion dsu(N_nodes); // Khởi tạo DSU
    std::set<int> nodes_beyond_k;   // Tập hợp các nút j > k liền kề với [0, k]
    int current_components = 0;     // Số lượng thành phần liên thông trong dải [0, k]

    // Lặp qua k từ 0 đến N-1
    for (int k = 0; k < N_nodes; ++k) {
        current_components++; // Thêm nút k, nó bắt đầu như một thành phần mới

        // Xử lý tất cả các cạnh của nút k
        for (int neighbor : adj_list[k]) {
            if (neighbor > k) {
                // Nếu nút liền kề lớn hơn k, thêm nó vào tập hợp các nút "ngoài phạm vi"
                nodes_beyond_k.insert(neighbor);
            } else {
                // Nếu nút liền kề nhỏ hơn hoặc bằng k, cố gắng hợp nhất
                if (dsu.unite(k, neighbor)) {
                    current_components--; // Nếu hợp nhất thành công, số thành phần giảm
                }
            }
        }
        
        // Loại bỏ các nút <= k khỏi nodes_beyond_k vì chúng giờ đã nằm trong phạm vi xét
        while (!nodes_beyond_k.empty() && *nodes_beyond_k.begin() <= k) {
            nodes_beyond_k.erase(nodes_beyond_k.begin());
        }

        // Kiểm tra điều kiện: tất cả các nút từ 0 đến k phải tạo thành một thành phần liên thông duy nhất
        if (current_components == 1) {
            // Nếu đúng, in kích thước của tập hợp nodes_beyond_k
            std::cout << nodes_beyond_k.size() << std::endl;
        } else {
            // Nếu không, in -1
            std::cout << -1 << std::endl;
        }
    }
}

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

    xuLyBaiToanE();

    return 0;
}