Tổng bằng 0

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

PhanDinhKhoi

Dạng bài

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

Bạn được cho một dãy số \(a\) gồm \(n\) số nguyên. Nhiệm vụ của bạn là tìm số cặp số \((i,j) \ 1 \leq i \leq j \leq n\) sao cho \(a_i + a_{i+1} + ... + a_j = 0\)

Input

Dòng đầu tiên chứa số nguyên dương \(n \ (1 \leq n \leq 10^5)\) - là số phần tử của mảng.
Dòng thứ hai chứa \(n\) số nguyên, số thứ \(i\) là \(a_i\) \(( \mid a_i\mid \leq 10^9)\)

Output

Số lượng cặp số \((i,j)\) thõa mãn điều kiện trên

Example

Test 1

Input

4
-3 3 -4 4

Output

Bình luận

Sì poi lơ át lét

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

    int main()
    {
        int n, cnt = 0, ans = 0; cin >> n; ll temp,t[n+1];
        t[0] = 0;
        map<ll,int> mp;
        for (int i=1; i<=n; i++) 
        {
            cin >> temp; 
            t[i]=t[i-1]+temp; 
            mp[t[i]]++;
        }
        for (auto i:mp)
        {
            if (i.first == 0) ans += (i.second*(i.second+1))/2;
            else ans += (i.second*(i.second-1))/2;
        }
        cout << ans;
    }

C++

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

    int main()
    {
        int n, cnt = 0, ans = 0; cin >> n; ll temp,t[n+1];
        t[0] = 0;
        map<ll,int> mp;
        for (int i=1; i<=n; i++) 
        {
            cin >> temp; 
            t[i]=t[i-1]+temp; 
            mp[t[i]]++;
        }
        for (auto i:mp)
        {
            if (i.first == 0) ans += (i.second*(i.second+1))/2;
            else ans += (i.second*(i.second-1))/2;
        }
        cout << ans;
    }

0

thanhkhoa123 7:24 a.m. 5 Tháng 11, 2024

Python thì sao ạ

2 bình luận nữa