Bài toán A: Minimal Coprime

Một đoạn $[l', r']$ được gọi là đoạn nguyên tố cùng nhau nếu $\gcd(l', r') = 1$. Nó được coi là tối tiểu nếu không chứa bất kỳ đoạn nguyên tố cùng nhau nào khác bên trong. Cho một khoảng $[l, r]$, nhiệm vụ là đếm số lượng các đoạn nguyên tố cùng nhau tối tiểu nằm trong khoảng này.

Phân tích:

Nhận xét quan trọng là hai số nguyên liên tiếp $x$ và $x+1$ luôn nguyên tố cùng nhau. Do đó, mọi cặp số $(x, x+1)$ đều tạo thành một đoạn nguyên tố cùng nhau tối tiểu. Số lượng các cặp như vậy trong đoạn $[l, r]$ đơn giản là $r - l$. Tuy nhiên, cần lưu ý trường hợp đặc biệt khi $l = r$. Nếu $l = r = 1$, kết quả là 1 vì $[1, 1]$ thỏa mãn $\gcd(1, 1) = 1$. Nếu $l = r > 1$, kết quả là 0.

#include <iostream>

using namespace std;

void solve_a() {
    long long left, right;
    cin >> left >> right;
    if (left == right) {
        cout << (left == 1 ? 1 : 0) << endl;
    } else {
        cout << right - left << endl;
    }
}

int main() {
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        solve_a();
    }
    return 0;
}

Bài toán B: Subsequence Update

Cho một dãy số nguyên $a$ và một đoạn $[l, r]$. Bạn có thể chọn bất kỳ dãy con nào và sắp xếp lại chúng. Mục tiêu là làm cho tổng các phần tử trong phạm vi từ chỉ số $l$ đến $r$ đạt giá trị nhỏ nhất có thể.

Phân tích:

Để tối thiểu hóa tổng trong đoạn $[l, r]$, chúng ta cần thay thế các số lớn trong đoạn này bằng các số nhỏ hơn từ bên ngoài. Có hai chiến lược khả thi:

1. Sử dụng các số trong đoạn $[1, r]$ và chọn ra $r - l + 1$ số nhỏ nhất.
2. Sử dụng các số trong đoạn $[l, n]$ và chọn ra $r - l + 1$ số nhỏ nhất.

Kết quả cuối cùng sẽ là giá trị nhỏ nhất thu được từ một trong hai chiến lược này.

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

using namespace std;

long long get_min_sum(vector<int> nums, int k) {
    sort(nums.begin(), nums.end());
    long long total = 0;
    for (int i = 0; i < k; ++i) {
        total += nums[i];
    }
    return total;
}

void solve_b() {
    int n, l, r;
    cin >> n >> l >> r;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int range_size = r - l + 1;
    vector<int> prefix_candidates, suffix_candidates;

    for (int i = 0; i < r; ++i) prefix_candidates.push_back(a[i]);
    for (int i = l - 1; i < n; ++i) suffix_candidates.push_back(a[i]);

    long long res1 = get_min_sum(prefix_candidates, range_size);
    long long res2 = get_min_sum(suffix_candidates, range_size);

    cout << min(res1, res2) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) solve_b();
    return 0;
}

Bài toán C: Remove Exactly Two

Cho một cấu trúc cây. Bạn cần chọn đúng hai đỉnh để xóa bỏ cùng với tất cả các cạnh kết nối với chúng. Mục tiêu là cực đại hóa số lượng thành phần liên thông (các cây con) còn lại trong rừng.

Phân tích:

Gọi $deg(u)$ là bậc của đỉnh $u$.

• Nếu chúng ta xóa một đỉnh $u$, số lượng thành phần liên thông sẽ tăng thêm $deg(u) - 1$.
• Khi xóa hai đỉnh $u$ và $v$:
  • Nếu $u$ và $v$ không kề nhau, tổng số thành phần liên thông sẽ là $deg(u) + deg(v) - 1$.
  • Nếu $u$ và $v$ kề nhau, một cạnh nối giữa chúng bị mất đi khi xóa đỉnh đầu tiên, do đó tổng số thành phần là $deg(u) + deg(v) - 2$.

Để giải quyết bài toán hiệu quả, chúng ta duyệt qua từng đỉnh $u$, tạm thời loại bỏ $u$ và các đỉnh kề của nó khỏi một cấu trúc dữ liệu (như multiset) để tìm đỉnh $v$ không kề có bậc lớn nhất.

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

using namespace std;

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

    multiset<int> deg_set;
    for (int i = 1; i <= n; ++i) {
        deg_set.insert(degree[i]);
    }

    int max_components = 0;
    for (int u = 1; u <= n; ++u) {
        // Xử lý các đỉnh kề
        for (int v : adj[u]) {
            max_components = max(max_components, degree[u] + degree[v] - 2);
            deg_set.erase(deg_set.find(degree[v]));
        }
        
        // Tạm thời xóa u để tìm v không kề
        deg_set.erase(deg_set.find(degree[u]));
        
        if (!deg_set.empty()) {
            max_components = max(max_components, degree[u] + *deg_set.rbegin() - 1);
        }

        // Khôi phục lại trạng thái cho lần duyệt sau
        for (int v : adj[u]) {
            deg_set.insert(degree[v]);
        }
        deg_set.insert(degree[u]);
    }

    cout << max_components << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) solve_c();
    return 0;
}