Phân tích và giải các bài toán CF1000

A. Đếm số lượng "khoảng tốt" tối tiểu

Một khoảng [x, x+1] luôn là "khoảng tốt" vì hai số liên tiếp luôn nguyên tố cùng nhau. Hơn nữa, đây cũng là khoảng tốt tối tiểu, do các khoảng đơn phần tử như [x,x] không thể là khoảng tốt (vì gcd(x,x) = x ≠ 1 nếu x > 1).

Với mọi khoảng có độ dài lớn hơn 2, nó sẽ chứa ít nhất một khoảng con độ dài 2 — do đó không thể là tối tiểu. Vậy chỉ cần đếm số khoảng độ dài đúng bằng 2 trong đoạn [l, r].

Tuy nhiên, có một ngoại lệ: khoảng [1,2] chứa khoảng [1,1] — mà [1,1] lại là khoảng tốt (do gcd(1,1)=1). Do đó, [1,2] không phải là khoảng tốt tối tiểu.

Nhưng khi tính tổng số khoảng tốt tối tiểu trong [l, r], việc loại [1,2] và giữ [1,1] hay ngược lại đều cho cùng kết quả — trừ trường hợp duy nhất: l = r = 1. Khi đó, chỉ có một khoảng [1,1], và nó là hợp lệ.

Giải pháp 
#include <bits/stdc++.h>
using namespace std;

void solve() {
    long long l, r;
    cin >> l >> r;
    if (l == 1 && r == 1) cout << 1 << '\n';
    else cout << r - l << '\n';
}

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

B. Tối ưu hóa tổng sau một phép đảo đoạn

Cho mảng a và đoạn [l, r] có độ dài w = r - l + 1. Mục tiêu là chọn một đoạn con để đảo sao cho tổng w phần tử nhỏ nhất trong toàn mảng nằm trong đoạn [l, r] sau thao tác.

Vì chỉ được thực hiện một phép đảo, ta chỉ có hai lựa chọn khả thi:

  • Đảo đoạn từ đầu đến r để đưa w số nhỏ nhất trong [1, r] vào đoạn [l, r].
  • Đảo đoạn từ l đến cuối để đưa w số nhỏ nhất trong [l, n] vào đoạn [l, r].

Ta tính tổng của w số nhỏ nhất trong hai trường hợp trên và chọn giá trị nhỏ hơn.

Giải pháp 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int n, l, r;
    cin >> n >> l >> r;
    vector<ll> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = a[i];
    }

    sort(a.begin() + 1, a.begin() + r + 1);
    sort(b.begin() + l, b.end());

    ll sum1 = 0, sum2 = 0;
    int w = r - l + 1;
    for (int i = 1; i <= w; ++i) {
        sum1 += a[i];
        sum2 += b[l + i - 1];
    }

    cout << min(sum1, sum2) << '\n';
}

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

C. Xóa hai đỉnh để tối đa hóa số thành phần liên thông

Khi xóa một đỉnh có bậc d, đồ thị tách thành d thành phần liên thông. Với hai đỉnh, nếu chúng không kề nhau, tổng số thành phần là d₁ + d₂. Nếu chúng kề nhau, cạnh nối giữa chúng bị tính hai lần nên phải trừ 1: d₁ + d₂ - 1.

Chiến lược:

  1. Tìm bậc lớn nhất max_deg.
  2. Xác định tập S gồm các đỉnh có bậc bằng max_deg (gọi là "đỉnh tối ưu").
  3. Với mỗi đỉnh v, đếm số đỉnh trong S kề với v (kể cả chính v nếu v ∈ S).
  4. Với mỗi đỉnh v (trừ trường hợp đặc biệt khi |S| = 1 và v là đỉnh duy nhất trong S), tính:
    • Nếu v kề với tất cả đỉnh trong S: kết quả ứng viên là max_deg + deg[v] - 1.
    • Ngược lại: max_deg + deg[v].

Kết quả cuối cùng là giá trị lớn nhất tìm được, trừ 1 (do đề yêu cầu in ra sum - 1 theo logic đã phân tích).

Giải pháp 
#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    vector<int> deg(n + 1, 0);

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

    int max_deg = *max_element(deg.begin() + 1, deg.end());
    vector<int> cnt(n + 1, 0);
    int total_opt = 0;

    for (int v = 1; v <= n; ++v) {
        if (deg[v] == max_deg) {
            total_opt++;
            cnt[v]++;
            for (int u : g[v]) cnt[u]++;
        }
    }

    int best = 0;
    for (int v = 1; v <= n; ++v) {
        if (total_opt == 1 && deg[v] == max_deg) continue;
        if (cnt[v] == total_opt)
            best = max(best, max_deg + deg[v] - 1);
        else
            best = max(best, max_deg + deg[v]);
    }

    cout << best - 1 << '\n';
}

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

D. Cấu trúc tam giác từ hai dãy điểm

Có hai hàng điểm: hàng trên có n điểm, hàng dưới có m điểm (n ≤ m). Mỗi tam giác cần 3 điểm: hoặc 2 trên + 1 dưới, hoặc 1 trên + 2 dưới.

Số tam giác tối đa có thể tạo là:

k = min(n, (n + m) / 3)

Để tối ưu tổng diện tích (tỷ lệ với hiệu tọa độ), ta nên chọn các cặp điểm ở hai đầu mút (giá trị lớn nhất và nhỏ nhất) để tạo chênh lệch lớn.

Thuật toán:

  1. Sắp xếp cả hai dãy.
  2. Tính trước hiệu c[i] = a[n-i+1] - a[i] (cho các cặp trên), và d[j] = b[m-j+1] - b[j] (cho các cặp dưới).
  3. Dùng tham lam: tại mỗi bước, chọn giữa lấy một cặp trên hoặc một cặp dưới, dựa trên giá trị hiệu lớn hơn — đồng thời đảm bảo không vượt quá giới hạn số điểm còn lại ở mỗi hàng.
Giải pháp 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll read() {
    ll x = 0, s = 1;
    char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') s = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); }
    return x * s;
}

void solve() {
    ll n = read(), m = read();
    bool swapped = false;
    if (n > m) {
        swap(n, m);
        swapped = true;
    }

    vector<ll> top(n + 1), bot(m + 1);
    if (swapped) {
        for (int i = 1; i <= m; ++i) bot[i] = read();
        for (int i = 1; i <= n; ++i) top[i] = read();
    } else {
        for (int i = 1; i <= n; ++i) top[i] = read();
        for (int i = 1; i <= m; ++i) bot[i] = read();
    }

    sort(top.begin() + 1, top.end());
    sort(bot.begin() + 1, bot.end());

    ll k = (2 * n <= m) ? n : (n + m) / 3;
    cout << k << '\n';

    vector<ll> diff_top((n / 2) + 1, 0), diff_bot((m / 2) + 1, 0);
    for (int i = 1; 2 * i <= n; ++i)
        diff_top[i] = top[n - i + 1] - top[i];
    for (int i = 1; 2 * i <= m; ++i)
        diff_bot[i] = bot[m - i + 1] - bot[i];

    ll used_top_pairs = 0, used_bot_pairs = 0, current = 0;
    vector<ll> res(k + 1);

    for (ll step = 1; step <= k; ++step) {
        // Kiểm tra nếu dùng thêm cặp trên sẽ vượt quá giới hạn trên
        bool can_use_top = (2 * (used_top_pairs + 1) + used_bot_pairs <= n);
        // Kiểm tra nếu dùng thêm cặp dưới sẽ vượt quá giới hạn dưới
        bool can_use_bot = (2 * (used_bot_pairs + 1) + used_top_pairs <= m);

        if (!can_use_top) {
            current += diff_bot[++used_bot_pairs];
        } else if (!can_use_bot) {
            current += diff_top[++used_top_pairs];
        } else {
            if (diff_top[used_top_pairs + 1] >= diff_bot[used_bot_pairs + 1]) {
                current += diff_top[++used_top_pairs];
            } else {
                current += diff_bot[++used_bot_pairs];
            }
        }
        res[step] = current;
    }

    for (ll i = 1; i <= k; ++i) cout << res[i] << " ";
    cout << '\n';
}

int main() {
    int t = read();
    while (t--) solve();
    return 0;
}

Thẻ: Codeforces greedy graph-theory Combinatorics implementation

Đăng vào ngày 27 tháng 6 lúc 06:29

Thẻ Phổ Biến

©2026 Thành phố Cuồng loạn