2022_de1bai2:Tổng đoạn con - LCOJ: Luyện Code Online Judge

2022_DE1BAI2 - 2022_de1bai2:Tổng đoạn con

Điểm: 10,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: TDOAN.INP

Output: TDOAN.OUT

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, JavaScript, Kotlin, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Bình luận

Please read the guidelines before commenting.

include <iostream>

include <vector>

include <algorithm>

include <cstdio>

using namespace std;

int main() { iosbase::syncwith_stdio(false); cin.tie(NULL);

freopen("TDOAN.INP", "r", stdin);
freopen("TDOAN.OUT", "w", stdout);

int n;
long long k;
if (cin >> n >> k) {
    vector&lt;long long> t(n + 1, 0);
    vector&lt;long long> ds;
    ds.reserve(2 * n + 2);
    ds.push_back(0);
    ds.push_back(-k);

    for (int i = 1; i <= n; ++i) {
        long long a;
        cin >> a;
        t[i] = t[i - 1] + a;
        ds.push_back(t[i]);
        ds.push_back(t[i] - k);
    }

    sort(ds.begin(), ds.end());
    ds.erase(unique(ds.begin(), ds.end()), ds.end());

    vector<int> vt_t(n + 1);
    vector<int> vt_q(n + 1);

    for (int i = 0; i <= n; ++i) {
        vt_t[i] = lower_bound(ds.begin(), ds.end(), t[i]) - ds.begin();
        if (i > 0) {
            vt_q[i] = lower_bound(ds.begin(), ds.end(), t[i] - k) - ds.begin();
        }
    }

    vector<int> vt(ds.size(), -1);
    vt[vt_t[0]] = 0;

    int nn = n + 1;
    int vtd = -1;

    for (int i = 1; i <= n; ++i) {
        int q = vt_q[i];
        int j = vt[q];
        if (j != -1) {
            int len = i - j;
            if (len < nn) {
                nn = len;
                vtd = j + 1;
            }
        }
        vt[vt_t[i]] = i;
    }

    if (vtd == -1) {
        cout << 0 << "\n";
    } else {
        cout << vtd << " " << nn << "\n";
    }
}
return 0;

} Bài nè

1
vudinhlong đã bình luận lúc 29, Tháng 1, 2026, 14:33
Đề bài: cho mảng ~a~ gồm có ~n~ phần tử và một số nguyên ~k~. Hãy tìm đoạn con liên tiếp của ~a~ có tổng các phần tử đúng bằng ~k~. Nếu có nhiều đoạn thoả mãn, hãy chọn đoạn ngắn nhất, nếu vẫn có nhiều đoạn thoả mãn thì chọn đoạn con xuất hiện sớm nhất.

Input:

Dòng đầu tiên chứa ~2~ số nguyên ~n, k~ ~(1 \le n \le 10^6, -10^9 \le k \le 10^9)~.

Dòng tiếp theo chứa ~n~ số nguyên ~a_i~ ~(-10^9 \le a_i \le 10^9)~.

Output:

Nếu tìm thấy đoạn con thỏa mãn: In ra ~2~ số nguyên là chỉ số bắt đầu (tính từ ~1~) và độ dài của đoạn con đó.

Nếu không tìm thấy đoạn con nào có tổng bằng ~k~: In ra số ~0~.

-1

dangkhoi1239876 đã bình luận lúc 28, Tháng 1, 2026, 8:25

include<bits/stdc++.h>

using namespace std;

int main(){ iosbase::syncwithstdio(false);cin.tie(nullptr);cout.tie(nullptr); freopen("TDOAN.INP","r",stdin); freopen("TDOAN.OUT","w",stdout); int n, k, x; cin >> n >> k; unorderedmap<long long, int> c; long long pref = 0; int dl = INT_MAX, vt = -1; c[0] = 0; for (int i = 1; i <= n; i++) { cin >> x; pref += x; if(c.count(pref - k)) { int l = c[pref - k]; if (i - l < dl) { dl = i - l; vt = l; } } c[pref] = i; } if(vt == -1) cout << 0; else cout << vt + 1 << " " << dl; return 0; }

-1

chep di ae

#include<bits/stdc++.h>
using namespace std;

int main(){
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
freopen("TDOAN.INP","r",stdin);
freopen("TDOAN.OUT","w",stdout);
int n, k, x;
cin >> n >> k;
unordered_map&lt;long long, int> c;
long long pref = 0;
int dl = INT_MAX, vt = -1;
c[0] = 0;
for (int i = 1; i <= n;  i++)
{
    cin >> x;
    pref += x;
    if(c.count(pref - k))
    {
        int l = c[pref - k];
        if (i - l < dl)
        {
            dl = i - l;
            vt = l;
        }
    }
    c[pref] = i;
}
if(vt == -1) cout << 0;
else cout << vt + 1 << " " << dl;
return 0;

}

-1
maxkhanhminh đã bình luận lúc 26, Tháng 1, 2026, 10:14
Chep di ae:

#include<bits/stdc++.h>

using namespace std; int main(){ iosbase::syncwithstdio(false);cin.tie(nullptr);cout.tie(nullptr); freopen("TDOAN.INP","r",stdin); freopen("TDOAN.OUT","w",stdout); int n, k, x; cin >> n >> k; unorderedmap<long long, int> c; long long pref = 0; int dl = INT_MAX, vt = -1; c[0] = 0; for (int i = 1; i <= n; i++) { cin >> x; pref += x; if(c.count(pref - k)) { int l = c[pref - k]; if (i - l < dl) { dl = i - l; vt = l; } } c[pref] = i; } if(vt == -1) cout << 0; else cout << vt + 1 << " " << dl; return 0; }

-1

maxkhanhminh đã bình luận lúc 26, Tháng 1, 2026, 10:13

a

4

-2

maxkhanhminh đã bình luận lúc 26, Tháng 1, 2026, 10:00

De dau ae

-2

maxkhanhminh đã bình luận lúc 24, Tháng 1, 2026, 13:13

không đề làm kiểu gì

-1
leminhkhoi4g0newton5 đã bình luận lúc 23, Tháng 1, 2026, 10:29
uia

VT13

-2
leminhkhoi4g0newton5 đã bình luận lúc 23, Tháng 1, 2026, 10:25
ad hãy copy cái này rồi đọc infinity lần:

đề đâu

-2

if k&lt;m&lt;=n:

    for i in range(1,n+1):

        if i % m == k:

            uia=i

1

tinhocqs2024 đã bình luận lúc 8, Tháng 1, 2026, 8:19

đề đâu vậy ad