Question

code c++

Cho một dãy số nguyên gồm N phần tử: 𝑎1,𝑎2,…𝑎𝑛. Một đoạn con liên tiếp của dãy A có điểm đầu 𝐿, điểm cuối 𝑅 với (𝐿 ≤ 𝑅) là tập hợp tất cả các phần tử 𝑎𝑖 với (𝐿 ≤ 𝑖 ≤ 𝑅). Đếm số đoạn con có tổng tất cả các phần tử bằng 0.

Dữ liệu: Vào từ tệp SUMSEQ0.INP:

·        Dòng đầu là số tự nhiên n.

·        Dòng thứ 2 là n số nguyên 𝑎1,𝑎2,…𝑎n ( |𝑎𝑖| ≤ 109).

Kết quả: Ghi ra tệp SUMSEQ0.OUT số lượng đoạn con tìm được.

Ví dụ:

SUMSEQ0.INP	SUMSEQ0.OUT	Giải thích
5 2 1 -1 -2 0	4	Có 4 đoạn có tổng bằng 0 là: [2,3],[1,4],[1,5],[5,5]

Giới hạn:

·        Có 40% số test ứng với 40% số điểm của bài có n ≤ 100;

·        Có 60% số test ứng với 60% số điểm của bài có n≤ 10⁵.

Answer 1

Answer 2

using namespace std;

int main()  

ifstream infile("SUMSEQ0.INP"

int n;

infile >> n;

vector a(n);

for (int i = 0; i < n; ++i) { infile >> a[i];

unordered_map prefixSumCount;

long long sum = 0;

int count = 0;

prefixSumCount[0] = 1;

for (int i = 0; i < n; ++i) { sum += a[i];

if (prefixSumCount.find(sum) != prefixSumCount.end()) { count += prefixSumCount[sum];

prefixSumCount[sum]++; }

outfile << count << endl;

infile.close();

outfile.close();

return 0; }