Đếm cặp có tổng bằng 0

Xem PDF

Tất cả bài nộp

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

Tác giả:

nvatuan

Dạng bài

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

Cho dãy số \(A\) có \(N\) số nguyên. Hãy đếm số cặp \((i,j)\) sao cho \(A_i + A_j = 0\), với \(i < j\).

Input

Dòng đầu tiên chứa một số nguyên dương \(N\) \((1 \leq N \leq 2*10^5)\)
Dòng thứ hai chứa dãy số \(A\) gồm \(N\) số nguyên cách nhau bởi một ký tự khoảng trống. \((|A_i| \leq 10^9)\)

Output

In ra một số nguyên duy nhất, là số cặp phần tử trong dãy \(A\) mà có tổng là 0.

Scoring

Subtask \(1\) (\(25\%\) số điểm): \(N \leq 10^4\), \(|A_i| \leq 10^6\).
Subtask \(2\) (\(60\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^6\).
Subtask \(3\) (\(100\%\) số điểm): \(N \leq 2*10^5\), \(|A_i| \leq 10^9\).

Example

Test 1

Input

3
-2 0 2

Output

Note

Chỉ tồn tại một cặp phần tử \((1, 3)\) tương ứng với \(A_1 + A_3 = -2 + 2 = 0\).

Test 2

Input

6
-2 -1 0 0 1 2

Output

Bình luận

0

giahantvd2015 3:39 p.m. 15 Tháng 7, 2024

có một dòng hoy '-'

summary

code khi bí idea

#include <bits/stdc++.h>
using namespace std;
int main()
{
     ios_base::sync_with_stdio(0);
     cin.tie(0); cout.tie(0); 
     int n,x; long long cnt=0;
     cin>>n;
     map <long long,int> m;
     while (n--) 
         cin>>x,
         cnt+=m[-x],
         ++m[x];
     cout<<cnt;
     return 0;
}

1

nob_Python69 7:38 p.m. 30 Tháng 5, 2024

sao mình làm tknp mà bị sai nhỉ?

0

trantrikien69 11:42 a.m. 16 Tháng 5, 2022

Đếm phân phối như này đúng không ạ, toàn bị segmentation fault

|| Code
var n,i:longint; ans:qword;
f,t:array [-2000000..2000000] of longint;
begin
readln(n);
for i:=1 to n do
begin
read(f[i]);
if t[-f[i]] > 0 then
begin
inc(ans,t[-f[i]]);
end;
inc(t[f[i]]);
end;
writeln(ans);
end.
||

2 phản hồi

1

trieunguyen_a1 10:11 p.m. 30 Tháng 10, 2021

dạ nó sai chỗ nào mà bị segmentation fault ạ ? Em biết mình code nhìn ngu

Delphi

var x,l,r,m,n,i,j,k,temp:longint;
a:array [1..100000000] of longint;
function tknp(x:longint):longint;
begin
l:=1;r:=n;
while l <= r do
begin
    m:=(l+r) div 2;
    if a[m] = x then exit(m);
    if a[m] > x then r:=m-1 else l:=m+1;
    if l >r then exit(0);
end;
exit(0);
end;
begin
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n-1 do
    for j:=i+1 to n do
    if a[i] > a[j] then
    begin
    temp:=a[i];
    a[i]:=a[j];
    a[j]:=temp;
    end;
    for i:=1 to n do if tknp(-a[i]) <> 0 then inc(k);
    write(k div 2);
end.

4 phản hồi