A. Diverse Game

Bài toán yêu cầu hoán đổi các phần tử trong ma trận sao cho không có phần tử nào giữ nguyên vị trí cũ. Một cách tiếp cận đơn giản là dịch chuyển các giá trị theo một vòng tuần hoàn. Với mỗi phần tử tại vị trí (i, j) trong ma trận n x m, ta gán giá trị mới bằng (a[i][j] % (n * m)) + 1. Phép toán này đảm bảo mọi giá trị đều được thay đổi.

B. Fun Game

Để xác định xem chuỗi nhị phân s có thể biến đổi thành chuỗi t hay không, ta cần tìm vị trí của bit '1' đầu tiên trong cả hai chuỗi. Gọi pos_s và pos_t lần lượt là chỉ số của bit '1' xuất hiện sớm nhất. Nếu pos_s <= pos_t, ta luôn có thể thực hiện phép biến đổi. Điều này dựa trên tính chất: bit '1' đầu tiên có khả năng "lan truyền" giá trị '1' sang các vị trí phía sau thông qua các thao tác trên đoạn con.

C. Hungry Games

Sử dụng phương pháp quy hoạch động kết hợp với tiền tố tổng. Gọi dp[i] là số lượng các đoạn con không hợp lệ bắt đầu tại chỉ số i. Với mỗi điểm bắt đầu i, ta sử dụng tìm kiếm nhị phân trên mảng tiền tố tổng để tìm chỉ số j sao cho tổng đoạn [i, j] vượt ngưỡng x. Công thức chuyển trạng thái được thiết lập như sau:

long long count_valid(vector<long long>& arr, int n, int limit) {
    vector<long long> prefix_sum(n + 1, 0);
    for (int i = 0; i < n; ++i) prefix_sum[i + 1] = prefix_sum[i] + arr[i];
    
    vector<long long> dp(n + 2, 0);
    long long total_subarrays = (long long)n * (n + 1) / 2;
    long long invalid_count = 0;
    
    for (int i = n; i >= 1; --i) {
        int target = upper_bound(prefix_sum.begin() + i, prefix_sum.end(), prefix_sum[i - 1] + limit) - prefix_sum.begin();
        if (target <= n) {
            dp[i] = 1 + dp[target + 1];
        }
        invalid_count += dp[i];
    }
    return total_subarrays - invalid_count;
}

D. Funny Game

Bài toán yêu cầu kết nối các đỉnh trong đồ thị dựa trên điều kiện modulo. Vì số lượng cạnh cần thiết là n-1, ta có thể duyệt ngược từ n-1 về 1. Tại mỗi bước k, ta tìm hai đỉnh thuộc hai tập hợp khác nhau trong cấu trúc Disjoint Set Union (DSU) sao cho giá trị của chúng đồng dư theo modulo k. Theo nguyên lý Dirichlet, trong k+1 phần tử, chắc chắn tồn tại ít nhất một cặp thỏa mãn điều kiện này.

E. Wooden Game

Kết quả tối ưu cho bài toán này không phụ thuộc vào cấu trúc hình học của cây mà chỉ phụ thuộc vào kích thước của chúng. Ta có thể đạt được giá trị OR lớn nhất bằng cách duyệt qua các bit từ cao xuống thấp. Với mỗi bit i, nếu có thể tạo ra được giá trị 1 tại vị trí đó bằng cách kết hợp các kích thước cây, ta ưu tiên thực hiện phép OR. Nếu đã có 1 ở bit hiện tại, các bit thấp hơn sau đó đều có thể được tối ưu hóa thành 1.

long long solve_bitwise(vector<int>& sizes) {
    sort(sizes.rbegin(), sizes.rend());
    long long current_or = 0;
    for (int val : sizes) {
        for (int bit = 25; bit >= 0; --bit) {
            if (!(val & (1 << bit))) continue;
            if (!(current_or & (1 << bit))) {
                current_or |= (1 << bit);
            } else {
                current_or |= ((1 << bit) - 1);
                break;
            }
        }
    }
    return current_or;
}