Bài dễ (DHBB 2021)

Tác giả:

Dạng bài

Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong một kỳ thi, việc sáng tạo bài dễ nhất trong đề thi nhiều khi cũng mất không ít thời gian. Trong đề thi Duyên Hải năm 2021, Ban giám khảo muốn tạo một bài dễ thao tác trên dãy số cho các học sinh khối 10. Bài toán dưới đây đã được sáng tạo và chọn vào đề thi, bài toán này có thể giải được bằng nhiều thuật toán khác nhau.

Cho dãy số nguyên \(a_1, a_2, ..., a_n\), một đoạn \(a_L, a_{L+1},..., a_R (1 \le L \le R \le N)\) được gọi là đoạn đẹp nếu \(L, R\) đều là số nguyên tố. Hãy tìm đoạn đẹp có tổng lớn nhất.

Input

Vào từ thiết bị vào chuẩn theo khuôn dạng:

Dòng đầu chứa số nguyên dương \(n (n \ge 2)\);
Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n (|a_i| \le 10^6)\)

Output

Ghi ra thiết bị ra chuẩn một số nguyên là tổng lớn nhất của đoạn đẹp tìm được.

Scoring

Subtask \(1\) (\(40\%\) số điểm): \(n \le 100\);
Subtask \(2\) (\(30\%\) số điểm): \(n \le 3000\);
Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^6\);

Example

Test 1

Input

6
9 5 -2 6 -1 1

Output

Bình luận

bopisreal_24110 • 11:33 p.m. 29 Tháng 12, 2024 •

ơ theo đề bài thì có mỗi 5 là số nguyên tố, vậy thì in ra 5 thôi chứ 8 đâu ra vậy?
nếu giải thích là dãy l,r nguyên tố là 5 -2 6 -1 thì ai cho tôi biết sao có mỗi 5 ngto mà bảo dãy đấy là dãy ngto hay v. Dãy kco nổi 2 ptu ngto

0
Phản hồi Chia sẻ

1 phản hồi

tuan8cnc • 10:25 p.m. 16 Tháng 12, 2024 •
C++
0
Phản hồi Chia sẻ

nhatnam3004 • 9:48 p.m. 14 Tháng 11, 2024 •

ye bài tên là bài dễ nhưng nó ko hề dễ đối với python

0
Phản hồi Chia sẻ

scratch_huykhanh • 9:45 a.m. 12 Tháng 10, 2024 • ← đã chỉnh sửa →

Bài này xét -1 là số nguyên tố ạ?
Update: tôi nhận ra yêu cầu là l r chứ ko phải a[l], a[r]🙃

-1
Phản hồi Chia sẻ

MinkMC_Gaming • 5:44 p.m. 28 Tháng 9, 2024 •

Sol:
Sub 1 (O (n^3)): các bạn có thể dùng 3 for, 2 for chạy i j và nếu i và j là số nguyên tố thì thêm 1 for k từ i đến j xong cộng a[k] và lấy max là được.
Sub 2 (O (n^2)): để cải tiến từ 3 for -> 2 for ta sử dụng prefix sum để giảm độ phức tạp, dễ thấy nếu i và j là số nguyên tố thì lấy max của s[j] - s[i - 1].
Sub 3 (O (n)): ta cần nhận xét và kết hợp prefix sum, do đề bài yêu cầu tổng lớn nhất nên giá trị lớn nhất sẽ là max (s[j]) - min (s[i - 1]), do i đã cố định nên ta chỉ quan tâm đến j có phải là số nguyên tố hay không, nếu có cập nhật max là được.

2
Phản hồi Chia sẻ

1 phản hồi

PHAMTHUYTRANG • 8:50 p.m. 3 Tháng 9, 2024 •

0
Phản hồi Chia sẻ

1 phản hồi

xthabao1 • 10:31 p.m. 1 Tháng 5, 2024 •

có ai có hint hay bài tương tự không

0
Phản hồi Chia sẻ

PY2GTranNguyenAnhKhoi • 4:45 p.m. 14 Tháng 2, 2024 •

sao t time limit, máy vẫn có kết quả đúng mà sao lại time nhỉ?

-4
Phản hồi Chia sẻ

HoaBanMaTuy • 2:51 p.m. 28 Tháng 11, 2023 •

Bài dễ vãi loz

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

-20
Phản hồi Chia sẻ

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

const int N = 10000000;
bool prime[N + 1];

void sieve()
{
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;

    for (int i = 2; i * i <= N; ++i)
    {
        if (prime[i])
        {
            for (int j = i * i; j <= N; j += i)
            {
                prime[j] = false;
            }
        }
    }
}

int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    sieve();
    int n; cin >> n;

    long long a, prefix_sum = 0;
    long long min_val = LLONG_MAX, ans = LLONG_MIN;

    for (int i = 0; i < n; ++i) 
    {
        cin >> a; prefix_sum += a;
        if (prime[i + 1]) ans = max(ans, prefix_sum - min_val);
        if (prime[i + 2]) min_val = min(min_val, prefix_sum);
    }

    cout << ans << endl;

    return 0;
}

-3

Phản hồi

2 bình luận nữa