Số cặp
Xem PDF
Đ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 1Output
1Test 2
Input
7
6 2 4 2 4 3 4Output
4
Bình luận
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;
}
.
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)
ai ko làm được nhắn tôi nhé
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
đếm phân phối
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;
}
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
'
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)
code python:def chap(k, n):
if k == 0 or k == n:
return 1
elif k == 1:
return n
else:
return chap(k - 1, n - 1) + chap(k, n - 1)
def main():
import sys
input = sys.stdin.read
data = input().split()
if name == "main":
main()
2 bình luận nữa