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 
1

Test 2

Input 
7
6 2 4 2 4 3 4
Output 
4

Bình luận


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

    .


    • 0
      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)


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

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


        • -2
          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

          1 phản hồi

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

            đếm phân phối

            1 phản hồi

            • 0
              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
                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
                  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
                    thuannguyen1972dn    7:14 p.m. 2 Tháng 5, 2024

                    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()

                    n = int(data[0])  # Đọc giá trị của n
a = list(map(int, data[1:n+1]))  # Đọc dãy a

# Sử dụng dictionary để đếm số lần xuất hiện của từng phần tử trong a
mp = {}
for num in a:
    if num in mp:
        mp[num] += 1
    else:
        mp[num] = 1

ans = 0
# Duyệt qua từng cặp (key, value) trong dictionary mp
for key, value in mp.items():
    if value == 2:
        ans += 1
    elif value > 2:
        ans += chap(2, value)

print(ans)

                    if name == "main":
                    main()


                    • 0
                      khaidadao    11:10 p.m. 10 Tháng 4, 2024

                      Để tối ưu hóa bài này thì nên sài đệ quy về : chập (2, số lượng phần tử) ; )
                      Code mẫu ac : https://www.ideone.com/gngGZL

                        • 1 bình luận nữa