Hướng dẫn giải của Thao tác trên dãy số

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, tdq, tuongvi, dat12345

Hiểu bài toán

Bài toán yêu cầu tìm số bước thao tác tối thiểu để biến một dãy số nguyên cho trước thành dãy toàn số 1. Thao tác được phép là chọn hai phần tử liên tiếp và thay thế một trong hai bằng ước chung lớn nhất (UCLN) của chúng. Nếu không thể thực hiện được, in ra -1.

Phân tích:

  1. Điều kiện cần để có thể biến toàn bộ dãy thành 1: UCLN của tất cả các phần tử trong dãy phải bằng 1. Nếu UCLN của toàn dãy > 1, ta không bao giờ có thể tạo ra số 1, vì thao tác chỉ tạo ra bội của UCLN ban đầu.
  2. Nếu trong dãy đã t tồn tại số 1: Giả sử có k số 1. Ta chỉ cần dùng các số 1 này để 'lây' sang các phần tử kề bên. Mỗi phần tử không phải 1 cần 1 thao tác để biến thành 1 (nếu ở ngay cạnh số 1). Vậy số thao tác tối thiểu là (n - k).
  3. Nếu không có số 1 nào: Ta cần tạo ra một số 1 trước tiên. Để tạo ra 1, ta cần một đoạn con liên tiếp có UCLN bằng 1. Gọi độ dài đoạn con ngắn nhất có UCLN bằng 1 là L.
    • Quá trình tạo 1: Bắt đầu từ đoạn con dài L, ta cần (L - 1) thao tác để biến nó thành một dãy con toàn 1 (thường là 1 thao tác để tạo ra 1, sau đó lan truyền).
    • Quá trình lan truyền: Sau khi có ít nhất một số 1, ta cần thêm (n - 1) thao tác để biến n-1 phần tử còn lại thành 1.
    • Tổng số thao tác: (L - 1) + (n - 1) = L + n - 2.

Các cách tiếp cận

Cách Brute Force (Tìm kiếm đoạn con ngắn nhất)
#include <iostream>
#include <vector>
#include <algorithm>

int gcd(int a, int b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    bool hasOne = false;
    int overall_gcd = 0;

    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (a[i] == 1) hasOne = true;
        if (i == 0) overall_gcd = a[i];
        else overall_gcd = gcd(overall_gcd, a[i]);
    }

    // Kiểm tra điều kiện tiên quyết
    if (overall_gcd != 1) {
        std::cout << -1 << std::endl;
        return 0;
    }

    // Trường hợp đã có số 1
    if (hasOne) {
        int countOne = 0;
        for (int x : a) if (x == 1) countOne++;
        std::cout << n - countOne << std::endl;
        return 0;
    }

    // Trường hợp không có số 1: tìm đoạn con ngắn nhất có UCLN = 1
    int min_len = n;
    for (int i = 0; i < n; ++i) {
        int g = a[i];
        for (int j = i; j < n; ++j) {
            g = gcd(g, a[j]);
            if (g == 1) {
                min_len = std::min(min_len, j - i + 1);
                break; // Tìm thấy đoạn ngắn nhất bắt đầu tại i
            }
        }
    }

    std::cout << min_len + n - 2 << std::endl;
    return 0;
}
  • Time Complexity: O(N^2 * log(max(A)))
  • Space Complexity: O(N)

Đây là cách tiếp cận trực tiếp dựa trên phân tích logic của bài toán.

  1. Kiểm tra UCLN toàn dãy, nếu khác 1 thì in -1.
  2. Đếm số lượng phần tử bằng 1. Nếu có > 0, đáp án là n - số_lượng_1.
  3. Nếu không có số 1, duyệt qua tất cả các cặp chỉ số (i, j) để tìm độ dài đoạn con liên tiếp (từ i đến j) ngắn nhất có UCLN bằng 1. Độ phức tạp là O(N^2) cho vòng lặp kép, và O(log(max(A))) cho hàm gcd bên trong.
  4. Kết quả cuối cùng là độ_dài_đoạn_con_ngắn_nhất + n - 2.
Cách Optimized Search (Tối ưu hóa tìm kiếm)
#include <iostream>
#include <vector>
#include <algorithm>

int gcd(int a, int b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);

    int overall_gcd = 0;
    bool hasOne = false;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (i == 0) overall_gcd = a[i];
        else overall_gcd = gcd(overall_gcd, a[i]);
        if (a[i] == 1) hasOne = true;
    }

    if (overall_gcd != 1) {
        std::cout << -1 << std::endl;
        return 0;
    }

    if (hasOne) {
        int cnt = 0;
        for (int x : a) if (x == 1) cnt++;
        std::cout << n - cnt << std::endl;
        return 0;
    }

    int min_len = n;
    // Tối ưu hóa: Chỉ duyệt j từ i cho đến i + min_len
    // Nếu đoạn con dài hơn min_len tìm được hiện tại, ta không cần xét tiếp
    for (int i = 0; i < n; ++i) {
        int g = a[i];
        for (int j = i; j < n; ++j) {
            g = gcd(g, a[j]);
            if (g == 1) {
                int len = j - i + 1;
                if (len < min_len) min_len = len;
                break;
            }
            // Tối ưu hóa: nếu đoạn hiện tại đã dài bằng min_len mà vẫn chưa có UCLN=1
            // thì các đoạn dài hơn bắt đầu từ i chắc chắn không tối ưu hơn
            if (j - i + 1 >= min_len) break;
        }
    }

    std::cout << min_len + n - 2 << std::endl;
    return 0;
}
  • Time Complexity: O(N^2 * log(max(A))) (Trung bình tốt hơn)
  • Space Complexity: O(N)

Phương pháp này giống Approach 1 về mặt logic, nhưng có thêm một chút tối ưu hóa trong vòng lặp.

  • Biến min_len được cập nhật liên tục.
  • Trong vòng lặp trong (biến j), nếu độ dài đoạn con hiện tại j - i + 1 đã lớn hơn hoặc bằng min_len mà vẫn chưa tìm thấy UCLN bằng 1, ta có thể break ngay lập tức. Vì nếu đoạn dài hơn chắc chắn không tối ưu hơn.
  • Điều này giúp giảm đáng kể thời gian chạy trong trường hợp đoạn con ngắn nhất có độ dài nhỏ.
Cách Dynamic Programming (Quy hoạch động)
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

int gcd(int a, int b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);

    int overall_gcd = 0;
    bool hasOne = false;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        if (i == 0) overall_gcd = a[i];
        else overall_gcd = gcd(overall_gcd, a[i]);
        if (a[i] == 1) hasOne = true;
    }

    if (overall_gcd != 1) {
        std::cout << -1 << std::endl;
        return 0;
    }

    if (hasOne) {
        int cnt = 0;
        for (int x : a) if (x == 1) cnt++;
        std::cout << n - cnt << std::endl;
        return 0;
    }

    int min_len = n;
    // Sử dụng map để lưu các UCLN của đoạn con kết thúc tại j
    // GCDs: map<gcd_value, length>
    std::map<int, int> current_gcds;

    for (int i = 0; i < n; ++i) {
        std::map<int, int> next_gcds;
        // Thêm phần tử hiện tại
        next_gcds[a[i]] = 1;

        // Kết hợp với các đoạn con trước đó
        for (auto const& [g, len] : current_gcds) {
            int new_g = gcd(g, a[i]);
            // Nếu UCLN mới đã t tồn tại, ta chỉ cần giữ độ dài ngắn nhất
            if (next_gcds.find(new_g) == next_gcds.end()) {
                next_gcds[new_g] = len + 1;
            } else {
                next_gcds[new_g] = std::min(next_gcds[new_g], len + 1);
            }
        }

        // Kiểm tra có UCLN bằng 1 không
        if (next_gcds.count(1)) {
            min_len = std::min(min_len, next_gcds[1]);
        }

        current_gcds = next_gcds;
    }

    std::cout << min_len + n - 2 << std::endl;
    return 0;
}
  • Time Complexity: O(N * D * log(max(A)))
  • Space Complexity: O(D)

Đây là cách tiếp cận cao cấp hơn, sử dụng ý tưởng quy hoạch động hoặc Sliding Window với số học.

  • Ta duyệt qua mảng từ trái sang phải.
  • Tại mỗi vị trí, ta duy trì một danh sách các cặp (UCLN, độ dài) của các đoạn con kết thúc tại vị trí đó.
  • Khi thêm một phần tử mới, ta cập nhật tất cả các UCLN cũ bằng cách tính UCLN với phần tử mới.
  • Số lượng UCLN khác nhau (D) có thể có giới hạn (thường nhỏ).
  • Nếu tại một thời điểm nào đó, UCLN bằng 1 xuất hiện, ta cập nhật min_len.
  • Độ phức tạp: O(N * D). Trong thực tế, D rất nhỏ (nhỏ hơn nhiều so với N).
  • Phương pháp này mạnh mẽ hơn khi cần xử lý các bài toán tương tự phức tạp hơn (ví dụ: đếm số đoạn con có UCLN bằng 1).

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(N^2 * log(max(A))) O(N) Brute Force (Tìm kiếm đoạn con ngắn nhất)
2 O(N^2 * log(max(A))) (Trung bình tốt hơn) O(N) Optimized Search (Tối ưu hóa tìm kiếm)
3 O(N * D * log(max(A))) O(D) Dynamic Programming (Quy hoạch động)

Bài học kinh nghiệm

  • UCLN của toàn dãy phải bằng 1 thì mới có thể tạo ra số 1.
  • Nếu dãy đã có số 1, đáp án đơn giản là n - số_lượng_1.
  • Nếu không có số 1, ta phải tạo ra nó trước. Số thao tác để tạo 1 từ đoạn con dài L là L - 1, và cần thêm n - 1 thao tác để lan truyền. Công thức tổng: L + n - 2.
  • Bài toán quy về tìm đoạn con liên tiếp ngắn nhất có UCLN bằng 1.

Lỗi thường gặp

  • Quên kiểm tra điều kiện toàn dãy có UCLN bằng 1 trước khi xử lý.
  • Sai công thức tính toán số thao tác khi đã có số 1 (cần n - sốlượng1, không phải n - 1).
  • Bỏ qua trường hợp đoạn con dài 1 (tức là phần tử đó đã là 1).
  • Trong giải pháp DP, cần đảm bảo lưu độ dài ngắn nhất cho mỗi UCLN nếu có nhiều cách tạo ra cùng UCLN.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.