Đếm cặp đôi (HSG'20)
Xem PDF
Điểm:
1500 (p)
Thời gian:
1.0s
Bộ nhớ:
977M
Input:
bàn phím
Output:
màn hình
Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\) và \(n≤ 10^5\). Một cặp số được gọi là cặp tương đồng với \(x\), nếu cặp số này có tổng bằng số \(x\) cho trước nào đó.
Yêu cầu: Hãy đếm xem trong dãy số \(A\) có bao nhiêu cặp số (\(A_i;A_j\)) tương đồng với \(x\) (có nghĩa là \(A_i+ A_j=x\)) với \(i<j\).
Input
- Dòng đầu tiên chứa dãy số \(n,x\) (\(n≤10^5,x≤10^6\)).
- Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\) (\(A_i≤10^9\)).
Output
- Ghi ra một số nguyên là cặp đôi tương đồng của dãy số.
Example
Test 1
Input
7 6
1 2 4 3 4 5 3 Output
4
Bình luận
include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, k, x;
cin >> n >> k;
map <int, int> a;
int c = 0;
for (int i = 0; i < n; ++i) {
cin >> x;
c += a[k - x];
++a[x];
}
cout << c;
return 0;
}
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
n, x = map(int, input().split())
a = list(map(int, input().split()))
c = {}
ans = 0
for p in a:
tab q = x - p
tab if q in c:
tab ans += c[q]
tab if p in c:
2tab c[p] += 1
tap else:
2tab c[p] = 1
print(ans)
def count_pairs(n, x, A):
count = 0
frequency = {}
n, x = map(int, input().split())
A = list(map(int, input().split()))
result = count_pairs(n, x, A)
print(result)
n,x = list(map(int, input().split()))
a = list(map(int, input().split()))
c = {}
ans = 0
for p in a:
q = x-p
if q in c:
ans = ans+c[q]
if p in c:
c[p] = c[p]+1
else:
c[p] = 1
print(ans)
n, x = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for i in a:
if i in d:
d[i] += 1
else:
d[i] = 1
t = 0
for i in a:
kq = x - i
if kq in d:
t += d[kq]
t //= 2
print(t)
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Mọi người có thể tham khảo code :
include <bits/stdc++.h>
using namespace std;
map<int,int>mp;
define ll long long
int n,k,x;
ll res=0;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
int tam;
for(int i=1;i<=n;i++) {
cin>>x;
mp[x]++;
tam=k-x;
if(k-x!=x)
res+=mp[k-x];
}
Đây là cách giải của mình, bạn nào có thắc mắc hay câu hỏi nào thì có thể hỏi mình ạ
7 6
1 2 4 3 4 5 3
Các cặp số thỏa mãn tổng bằng 6 :
1-5
2-4
2-4
3-3
Ta sẽ dùng map để giải bài này : Đầu tiên ta sẽ đếm số lần xuất hiện của các phần tử , sau đó cộng số lần xuất hiện của phần tử thỏa mãn : tổng của phần tử đó cộng một phần tử khác bằng k.
Ở đây mình sẽ dùng biến đếm tên là res :
Thì số cặp sẽ thỏa mãn : res+=mp[k-x]; (với x lần lượt là các phần tử trong mảng) .
Ta có tính chất như sau : một số nào đó + với số x bằng k :
Thì số đó sẽ có giá trị là : k-x.
Như vậy ta chỉ cần đếm sự xuất hiện của số k-x nào đó trong mảng là sẽ đếm được số cặp có tổng là k
Lưu ý ta sẽ không cộng vào phần tử có giá trị là : k/2 vội , vì cộng như vậy ta sẽ bị cộng lặp kết quả trước đó .
Vì phần tử k/2 là trường hợp đặc biệt nên ta sẽ chia làm 2 trường hợp :
Nếu phần tử k/2 xuất hiện lớn hơn hoặc bằng 2 lần trong mảng thì ta
Sẽ có số cặp thỏa mãn là : tổng từ 1 đến k/2-1 số lần xuất hiện của phần tử k/2 đó
Vd : 4 4 4 4 và tổng cần tìm là 8
Thì ta sẽ có số cặp thỏa mãn là : 6 => tương đương tổng từ 1 đến 3 là 6
Ngược lại nếu không có giá trị nào bằng k/2 trong mảng thì ta không cần cộng vào :
Và kết quả cuối cùng là kết quả của : số cặp có giá trị là k/2 và res.
7 bình luận nữa