Cho mảng A[] gồm N phần tử, bạn hãy tìm dãy con liên tiếp đều là số nguyên tố dài nhất. Nếu có nhiều dãy con có cùng độ dài thì in ra dãy con có tổng lớn nhất, và nếu có nhiều dãy con có cùng độ dài lớn nhất và có cùng tổng thì lấy dãy con đầu tiên. Trong trường hợp không tồn tại dãy con liên tiếp đều là số nguyên tố thì in ra NOT FOUND.
Gợi ý :
Bước 1. Sàng số nguyên tố để kiểm tra nhanh hơn
Bước 2. Duyệt qua mảng và dùng biến đếm, nếu A[i] là số nguyên tố => tăng đếm còn ko thì cập nhật đếm xem có lớn hơn kỷ lục đang có hay ko, nếu lớn hơn thì cập nhật, còn nếu chỉ bằng kỉ lục thì so sánh thêm tổng của dãy con. Reset biến đếm và tổng về 0 để xét lại dãy mới.
Đầu vào
Dòng 1 là N : số lượng phần tử trong mảng
Dòng 2 là N số trong mảng cách nhau 1 dấu cách
Giới hạn
1<=N<=10^6
0<=A[i]<=10^6
Đầu ra
Dòng 1 in độ dài dãy con
Dòng 2 in dãy con thỏa mãn
Ví dụ :
Input 01
10
3 1 1 11 7 13 5 0 10 5
Output 01
4
11 7 13 5
Bình luận
include <bits/stdc++.h>
using namespace std; int n,a[1000000],s[1000000],res=0,maxx=0; string N; int kiem(int doiso){ for(int i=2;i*i<=doiso;i++){ if(doiso%i==0) return 0; } return 1; } int main() { //freopen("codedao.inp","r",stdin); //freopen("codedao.out","w",stdout);
}
https://www.youtube.com/watch?v=dQw4w9WgXcQ :>
define ll long long
int prime[1000001]; void sang(){ for(int i = 0;i < 1000001;i++){ prime[i]=1; } prime[0] = prime[1] = 0; for(int i=2;i<=sqrt(1000000);i++){ if(prime[i]){ for(int j=i*i;j<=1000000;j+=i){ prime[j] = 0; } } } }
include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll snt[1000001];
void sang() { memset(snt, 1, sizeof(snt));
}
int main() { sang(); iosbase::syncwith_stdio(false); cin.tie(NULL); cout.tie(NULL);
}
include<bits/stdc++.h>
using namespace std; vector<bool> sieve(int maxnum) { vector<bool> isprime(maxnum + 1, true); isprime[0] = isprime[1] = false; for (int i = 2; i * i <= maxnum; ++i) { if (isprime[i]) { for (int j = i * i; j <= maxnum; j += i) { isprime[j] = false; } } } return isprime; } vector<int> tim(const vector<int>& A, const vector<bool>& isprime) { int maxlen = 0; int maxsum = 0; vector<int> a; int currlen = 0; int currsum = 0; vector<int> b; for (int num : A) { if (isprime[num]) { currlen++; currsum += num; b.pushback(num); } else { if (currlen > maxlen || (currlen == maxlen && currsum > maxsum)) { maxlen = currlen; maxsum = currsum; a = b; } currlen = 0; currsum = 0; b.clear(); } } if (currlen > maxlen || (currlen == maxlen && currsum > max_sum)) { a = b; }
} int main() { freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); int n; cin >> n; vector<int> A(n); for (int i = 0; i < n; i++) { cin >> A[i]; } int maxnum = *maxelement(A.begin(), A.end()); vector<bool> isprime = sieve(maxnum);
} Code tham khảo cho ai đang gặp kk nhé!
Anh đẹp trai nào ac rồi vào xem code giúp em với
mng ơi cái test thứ 5 là j v ạ, e sai test đấy ai AC r ghé qua code e với
Cho em hỏi test 4 với test 5 là gì v ạ??
ai AC rồi vào xem code em có thiếu sót gì ạ :))
Cái đoạn mà a[i] == 1 trong cái điều kiện anh thiếu trường hợp cnt < res phải cập nhật thg cnt = 0,cursum= 0 nx á,với đề nói nếu lấy tổng bằng nhau thì lấy dãy đầu tien nên cái đoạn kia a sửa lại thành cursum > max_sum là ok
À chắc bản best solve của mình là do mình spam thay dấu đấy, chứ đúng là > thôi :DD
Ôi vc cảm ơn bạn nhớ :33