Hướng dẫn giải của Bedao Mini Contest 06 - YUGIOH


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.

Tác giả: bedao

Gọi hàm ~isGood(x)~ là hàm xác định phần tử ~a_i~ thỏa mãn đề bài, ~isGood(x) = 1~ khi ~0 < a_i \leq X~ và ~a_i~ là số nguyên tố, ngược lại ~isGood(x) = 0~.

Gọi ~p_i~ là số các số thỏa mãn ~isGood(x) = 0~ từ ~1~ đến ~i~.

Gọi ~cnt~ là số lượng số thỏa mãn ~isGood(x) = 1~.

Nhận xét: Ta cần nhét hết tất cả các số có ~isGood(x) = 1~ nằm cạnh nhau, giả sử ta đang xét ở phần tử thứ ~i~ thì để nhét đủ ta cần các số trong đoạn ~[i-cnt+1,i]~ thỏa mãn ~isGood(x) = 1~.

Vì các số thỏa mãn yêu cầu đề bài có thể nằm bất cứ đâu nhưng cách tối ưu để xếp cạnh nhau là đưa các số ~isGood(x) = 1~ ngoài đoạn ~[i-cnt+1,i]~ về vị trí các số ~isGood(x) = 0~ mà nằm cạnh các số ~isGood(x) = 1~ trong đoạn ~[i-cnt+1,i]~. Vậy đáp án bài toán chính là ~min(p_i-p_{i-cnt+1})~ với ~i-cnt+1 < i \leq n~.

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define _(x) (1LL<<(x))
#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define turn_all(x) (_(x)-1LL)
#define bitCnt(x) __builtin_popcountll(x)

#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

const int N = 1E6;
const int INF = 1E9;

int notPrime[N+9];
int n, x;
bool f[N+9];
int cntPrime = 0;

void sieve()
{
    f[1] = f[0] = 1;
    for (int i = 2;i <= trunc(sqrt(N)); ++i)
        if (f[i] == 0)
            for (int j = i + i;j <= N; j += i)
                f[j] = 1;
}

int main()
{
    fastIO

    cin>>n>>x;

    sieve();
    for (int i = 1;i <= n; ++i)
    {
        int T;
        cin>>T;
        cntPrime += (0 < T && T <= x && f[T] == 0);
        notPrime[i] = notPrime[i-1] + !(0 < T && T <= x && f[T] == 0);
    }

    int ans = INF;
    for (int i = cntPrime;i <= n; ++i)
    {
        int j = i - cntPrime + 1;
        int cnt0 = notPrime[i] - notPrime[j-1];
        ans = min(ans, cnt0);
    }

    cout<<ans;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


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