Số cặp

Xem PDF

Tất cả bài nộp

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

Tác giả:

admin

Dạng bài

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

Cho một mảng gồm \(n\) số nguyên dương \(a_1,\) \(a_2,\) \(a_3,\) \(...,\) \(a_n.\)

Yêu cầu : Hỏi có bao nhiêu cặp số bằng nhau ? \((\)Bao nhiêu cặp \(a_i\) \(=\) \(a_j\) với \(i\) \(\neq\) \(j,\) \((ai,\) \(aj)\) và \((aj,\) \(ai)\) chỉ được tính là \(1\) cặp\().\)

Input

Dòng thứ nhất là chiều dài \(n\) của mảng \((1\) \(\leq\) \(n\) \(\leq\) \(10^5).\)
Dòng thứ hai gồm \(n\) số nguyên \(a_1,\) \(a_2,\) \(a_3,\) \(...,\) \(a_n\) \((1\) \(\leq\) \(a_i\) \(\leq\) \(10^5),\) mỗi số cách nhau một khoảng trắng.

Output

Là số nguyên xác định số lượng các cặp bằng nhau.

Example

Test 1

Input

5
8 2 9 8 1

Output

Test 2

Input

7
6 2 4 2 4 3 4

Output

Bình luận

n = int(input())
a = list(map(int, input().split()))
dict = {}
s = 0
for i in a:
    if i in dict:
        s += dict[i]
        dict[i] += 1
    else:
        dict[i] = 1
print (s)

code python

Phản hồi

huythcshtm • 8:52 p.m. 21 Tháng 11, 2024 •

Code c++ nek

include<bits/stdc++.h>

using namespace std;

define ll long long

ll n, a[1000008], dd[1000008], d = -1, s = 0;
int main()
{
cin >> n;
for(ll i = 1; i <= n; ++i)
{
cin >> a[i];
dd[a[i]]++;
}
for(ll i = 1; i <= n; ++i)
if(dd[i] > 0) s += (dd[i] * (dd[i] - 1)) / 2;
cout << s;
}

2
Phản hồi Chia sẻ

thdquynhthu10i • 6:38 p.m. 29 Tháng 10, 2024 • ← đã chỉnh sửa →

.

1
Phản hồi Chia sẻ

Janeskylineschool • 12:17 p.m. 30 Tháng 9, 2024 •

from collections import Counter
n=int(input())
tổng_cặp=0
a=list(map(int,input().split()))
count=Counter(a)
for i in count.values():
if i>1:
tổng_cặp+=(i*(i-1))//2
print(tổng_cặp)

0
Phản hồi Chia sẻ

quylam24012011 • 3:31 p.m. 25 Tháng 7, 2024 •

ai ko làm được nhắn tôi nhé

1
Phản hồi Chia sẻ

BestFlo2k9 • 5:32 p.m. 20 Tháng 7, 2024 •

include <bits/stdc++.h>

define ll long long

using namespace std;
ll solve(ll n){
return n*(n - 1)/2;
}
ll a[1000005],n,dem = 0;
int main(){
cin >> n;
set<ll> ms;
multiset<ll> ls;
for (ll i = 1;i <= n;i++){
cin >> a[i];
ms.insert(a[i]);
ls.insert(a[i]);
}
for (auto x : ms){
if (ls.count(x) < 2){
continue;
}
else{
dem += solve(ls.count(x));
}
}
cout << dem;
}
code cho ai cần

-2
Phản hồi Chia sẻ

1 phản hồi

tqhuy09 • 10:33 a.m. 7 Tháng 7, 2024 •

đếm phân phối

0
Phản hồi Chia sẻ

1 phản hồi

lehongduc • 9:44 p.m. 19 Tháng 6, 2024 •

bài này có thể dùng map với độ phức tạp O(n)

code mẫu

include<bits/stdc++.h>
define ll long long
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll n;
cin>>n;
ll t=0,m;
map<ll,ll> a;
for(ll i=0;i<n;i++) { cin>>m;
a.insert(make_pair(m,1));
if(a.size()==t)
{
a[m]++;
}
else t++;
}
ll dem=0;
for(pair<ll,ll> i:a)
{
if(i.second!=1)
{
i.second--;
dem+=(i.second+1)*i.second/2;
}
}
cout<<dem;
}

0
Phản hồi Chia sẻ

pa_ldk • 4:47 p.m. 14 Tháng 5, 2024 •

include<bits/stdc++.h>

using namespace std;

define ll long long

ll n, i, ans, t;
ll a[100005], dem[100005];
int main() {
cin >> n;
for(i = 0; i < n; i ++) cin >> a[i], dem[a[i]]++;
sort(a, a + n);
for(i = 0; i < n; i += dem[a[i]]) {
t = dem[a[i]];
ans += t * (t - 1) / 2;
}
cout << ans;
return 0;
}
Code c++ cho nhung ai can
'

0
Phản hồi Chia sẻ

nob_Python69 • 9:50 a.m. 11 Tháng 5, 2024 •

code Python O(n) đơn giản ko dùng đệ quy:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
ans = 0
for i in cnt.values():
ans += (i-1)*i//2
print(ans)

0
Phản hồi Chia sẻ