Đếm cặp đôi (HSG'20)

View as PDF




Author:
Problem types
Points: 1500 (p) Time limit: 1.0s Memory limit: 977M Input: stdin Output: stdout

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

Comments


  • 0
    TK22NguyenPhat    10:18 p.m. 23 may, 2024 edited
    
    

    • -1
      PY1CLeDongQuan    11:52 a.m. 29 apr, 2024

      bài khó quá


      • 0
        thinhec12012007    9:51 p.m. 24 apr, 2024

        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];

        }
        ll gan=mp[k/2];
        if(gan>=2) gan--;
        else gan=0;
        
        cout<<res+(gan*(gan+1)/2);
        return 0;
        

        }


        • 0
          thinhec12012007    9:51 p.m. 24 apr, 2024

          Đâ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
            blinh    8:36 p.m. 31 mar, 2024

            This comment is hidden due to too much negative feedback. Click here to view it.


            • 0
              Green    4:32 p.m. 25 nov, 2023 edited
              hint

              bài này có 2 cách:
              -Cách 1 dành cho ai làm trâu ta sẽ duyệt mảng như bình thường và xét trường hợp nếu như biến ta cứ cho là n mà bằng với tổng mảng a[i]+a[j] thì ta sẽ đăng biến đếm lên cách này thì sẽ dẫn đến bị tle
              -Cách 2 thì dùng hàm chặt có sẵn là ac


              • -1
                dinhthangnee    12:30 a.m. 19 nov, 2023

                Spoiler Alert

                1. Do dữ liệu cho \(10^5\) nên ta sắp xếp lại mảng rồi duyệt từng phần tử Ai, với mỗi phần tử ta tìm xem có bao nhiêu phần tử x - Ai. Kết quả nhớ chia đôi nếu duyệt cả mảng
                  Lưu ý trường hợp 2 * Ai = x :>
                2. Do \(0 < x \leqslant 10^6\) nên đếm phân phối bằng mảng oke, tội là phần tử nào lớn hơn thì vứt. :>. Ai muốn đếm bằng unordered_map cũng ổn nhe

                • -4
                  Sang522008    11:20 p.m. 3 feb, 2023

                  a ơi pas e chạy dc mà nộp bị lỗi phân khúc do sao ạ

                  1 reply

                  • 0
                    minhtuanitk20    12:35 p.m. 13 oct, 2021

                    hint 1 là nhanh nhất r

                    1 reply

                    • -3
                      vanlatuiday    9:57 p.m. 18 aug, 2021 edited

                      hmm

                      • 1 more comment