Hướng dẫn cho Dãy con

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.

Authors: mrdinh

Hướng dẫn giải

Subtask 1: \(N \le 10^3, a_i \le 10^3\)

  • Lần lượt duyệt qua tất cả các đoạn con, với mỗi phần tử, kiểm tra xem phần tử đó có phải số nguyên tố không trong \(O(\sqrt{a_i})\). Nếu đoạn con hiện tại thỏa mãn có ít nhất hai số nguyên tố, cập nhật đáp án nếu độ dài đoạn có đó đến hiện tại là nhỏ nhất.
  • Độ phức tạp: \(O(N^2* \sqrt{max⁡(a_i)} )\)

Subtask 2: \(N \le 10^6, a_i \le 10^3\)

  • Nhận xét: Nếu tồn tại đoạn con thỏa mãn ngắn nhất, nó chỉ gồm hai số nguyên tố ở hai đầu đoạn. (vì nếu 2 đầu đoạn không phải số nguyên tố thì ta có thể bỏ 2 đầu để tạo ra đoạn con ngắn hơn)
  • Từ đó, duyệt qua các phần tử của dãy, duy trì biến \(p\) là số nguyên tố gần nhất trong dãy khi đang xét đến vị trí \(i\). Nếu \(a_i\) là số nguyên tố, cập nhật đáp án nếu \(i-p+1\) là độ dài ngắn nhất tính tới hiện tại và cập nhật \(p=i\).
  • Độ phức tạp: \(O(N * \sqrt{max(a_i)} )\)

Subtask 3: \(N \le 10^6, a_i \le 10^6\)

  • Cải tiến từ Subtask 2 bằng sàng nguyên tố Eratosthenes.
  • Độ phức tạp: \(O(N+max⁡(a_i)* log(max(a_i)))\)

Code tham khảo

C++
/*
Tag: 
*/
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())

using namespace std;
const int maxn = 1e6 + 5;
bool prime[maxn];

void sieve(){
    fill(prime + 2, prime + maxn, true);
    for (int i = 2; i < maxn; i++){
        if (!prime[i]) continue;
        for (int j = i * i; j < maxn; j += i){
            prime[j] = 0;
        }
    }
}

int n, a[maxn];

void PROGRAM(int _){
    sieve();
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    int p = -1;
    int ans = 1e18;

    for (int i = 1; i <= n; i++){
        if (p != -1 && prime[a[i]]){
            ans = min(ans, i - p + 1);
        }

        if (prime[a[i]]) p = i;
    }
    if (ans == 1e18) ans = -1;
    cout << ans;
}

signed main(){
    freopen("daycon.inp", "r", stdin);
    freopen("daycon.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int test = 1;

    for (int _ = 1; _ <= test; _++){
        PROGRAM(_);
    }

    return 0;
}

Bình luận

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