Hướng dẫn cho Bài 4: Tìm phòng khách sạn (TS10 Ninh Bình thi thử - 2026)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho một dãy gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\). Yêu cầu tìm độ dài của dãy con liên tiếp dài nhất sao cho tất cả các phần tử trong dãy con đó cùng chia hết cho một số nguyên \(d > 1\). Nếu không tìm được dãy nào, in ra \(0\).

Phân tích

Điều kiện: Một dãy con liên tiếp \(a_i, a_{i+1}, \dots, a_j\) thỏa mãn yêu cầu khi và chỉ khi ước chung lớn nhất (ƯCLN) của tất cả các phần tử trong đoạn đó lớn hơn \(1\):

\[ \gcd(a_i, a_{i+1}, \dots, a_j) > 1 \]
Ràng buộc:
- Tổng \(n\) qua các bộ test không quá \(10^6\).
- Giá trị \(|a_i| \le 10^6\). Lưu ý rằng \(\gcd(x, y) = \gcd(|x|, |y|)\), nên ta có thể lấy giá trị tuyệt đối của các phần tử ngay từ đầu.
- Nếu \(a_i = 0\), nó chia hết cho mọi số \(d\). Tuy nhiên, trong bài toán thực tế về mức chuẩn phục vụ, ta thường xét các số nguyên dương hoặc xử lý \(\gcd(0, x) = |x|\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua tất cả các cặp \((i, j)\) đại diện cho đoạn con từ vị trí \(i\) đến \(j\). Với mỗi đoạn, ta tính \(\gcd\) của tất cả các phần tử. Nếu \(\gcd > 1\), ta cập nhật độ dài lớn nhất.

Độ phức tạp

Thời gian: \(O(T \times n^2 \times \log(\max A))\)
Đánh giá: Với \(n = 10^6\), cách này sẽ bị quá thời gian (TLE). Chỉ phù hợp với Subtask 1 (\(n \le 1000\)).

Code Brute Force

C++

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] = abs(a[i]);
    }
    int max_len = 0;
    for (int i = 0; i < n; i++) {
        int current_gcd = 0;
        for (int j = i; j < n; j++) {
            current_gcd = gcd(current_gcd, a[j]);
            if (current_gcd > 1) {
                max_len = max(max_len, j - i + 1);
            } else {
                break;
            }
        }
    }
    cout << max_len << endl;
}

int main() {
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

Python

import math

def solve():
    try:
        line1 = input().split()
        if not line1: return
        n = int(line1[0])
        a = list(map(int, input().split()))
    except EOFError:
        return

    a = [abs(x) for x in a]
    max_len = 0
    for i in range(n):
        current_gcd = 0
        for j in range(i, n):
            current_gcd = math.gcd(current_gcd, a[j])
            if current_gcd > 1:
                max_len = max(max_len, j - i + 1)
            else:
                break
    print(max_len)

t_str = input()
if t_str:
    t = int(t_str)
    for _ in range(t):
        solve()

Hướng giải quyết (Tối ưu)

Nhận xét

Một dãy con có \(\gcd > 1\) khi và chỉ khi tất cả các phần tử trong dãy đó cùng chia hết cho ít nhất một số nguyên tố \(p\).
Thay vì duyệt mọi đoạn con, ta có thể duyệt qua từng số nguyên tố \(p\) và tìm đoạn con liên tiếp dài nhất mà mọi phần tử đều chia hết cho \(p\).
Các số nguyên tố cần xét chỉ nằm trong khoảng từ \(2\) đến \(\max|a_i| = 10^6\).

Thuật toán

Sử dụng sàng Eratosthenes để tiền xử lý: Với mỗi số \(x \in [2, 10^6]\), tìm các ước nguyên tố của nó. Để tối ưu, ta chỉ cần lưu ước nguyên tố nhỏ nhất min_prime[x].
Với mỗi số \(a_i\) trong mảng:
- Phân tích \(a_i\) thành các thừa số nguyên tố khác nhau.
- Với mỗi thừa số nguyên tố \(p\), ta biết \(a_i\) có thể đóng góp vào một dãy chia hết cho \(p\).
Sử dụng một mảng (hoặc map) pos[p] để lưu độ dài của dãy con liên tiếp chia hết cho \(p\) kết thúc tại vị trí hiện tại.
- Khi xét đến \(a_i\), với mỗi ước nguyên tố \(p\) của \(a_i\):
  - Nếu \(a_{i-1}\) cũng chia hết cho \(p\), thì current_len[p] = current_len[p] + 1.
  - Nếu không, current_len[p] = 1.
- Cập nhật kết quả cực đại từ current_len[p].
- Lưu ý quan trọng: Để tránh việc reset mảng current_len cho mỗi bộ test (gây TLE), ta có thể dùng một mảng đánh dấu hoặc chỉ reset những vị trí đã sử dụng.

Độ phức tạp

Tiền xử lý: \(O(M \log \log M)\) với \(M = 10^6\).
Xử lý mỗi test: \(O(n \times \omega(a_i))\), trong đó \(\omega(a_i)\) là số lượng ước nguyên tố khác nhau của \(a_i\) (rất nhỏ, tối đa 7 vì \(2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 > 10^6\)).
Tổng thời gian: \(O(M \log \log M + \sum n \cdot \omega(a_i))\), hoàn toàn đáp ứng thời gian 1-2s.

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

const int MAXA = 1000001;
int min_prime[MAXA];
int current_len[MAXA];
int last_idx[MAXA]; // Lưu vị trí cuối cùng mà số nguyên tố p xuất hiện

void sieve() {
    for (int i = 2; i * i < MAXA; ++i) {
        if (min_prime[i] == 0) {
            for (int j = i * i; j < MAXA; j += i)
                if (min_prime[j] == 0) min_prime[j] = i;
        }
    }
    for (int i = 2; i < MAXA; ++i) {
        if (min_prime[i] == 0) min_prime[i] = i;
    }
}

void solve(int test_id) {
    int n; cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        x = abs(x);

        // Phân tích thừa số nguyên tố của x
        while (x > 1) {
            int p = min_prime[x];
            if (last_idx[p] == i - 1) {
                current_len[p]++;
            } else {
                current_len[p] = 1;
            }
            last_idx[p] = i;
            ans = max(ans, current_len[p]);

            // Loại bỏ các thừa số p trùng nhau
            while (x % p == 0) x /= p;
        }
    }
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieve();
    int t; cin >> t;
    for (int i = 1; i <= t; i++) {
        solve(i);
    }
    return 0;
}

Python

import sys

# Tăng giới hạn đệ quy và đọc dữ liệu nhanh
input = sys.stdin.read

def solve():
    data = input().split()
    if not data:
        return

    T = int(data[0])
    idx = 1

    MAXA = 1000001
    min_prime = [0] * MAXA
    for i in range(2, int(MAXA**0.5) + 1):
        if min_prime[i] == 0:
            for j in range(i*i, MAXA, i):
                if min_prime[j] == 0:
                    min_prime[j] = i
    for i in range(2, MAXA):
        if min_prime[i] == 0:
            min_prime[i] = i

    current_len = [0] * MAXA
    last_idx = [-1] * MAXA

    results = []
    for t in range(T):
        n = int(data[idx])
        idx += 1
        a = data[idx:idx+n]
        idx += n

        ans = 0
        for i in range(n):
            x = abs(int(a[i]))

            while x > 1:
                p = min_prime[x]
                if last_idx[p] == i - 1:
                    current_len[p] += 1
                else:
                    current_len[p] = 1

                last_idx[p] = i
                if current_len[p] > ans:
                    ans = current_len[p]

                while x % p == 0:
                    x //= p
        results.append(str(ans))

    sys.stdout.write("\n".join(results) + "\n")

if __name__ == "__main__":
    solve()

Bình luận

Tải bình luận...

Không có bình luận nào.