Hướng dẫn giải của Bedao Mini Contest 06 - YUGIOH
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ả:
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